Un Algoritmo de Estimación de Distribuciones copulado con la Distribución Generalizada de Mallows para el Problema de Ruteo de Autobuses Escolares con Selección de Paradas

Resumen

Aunque los algoritmos de estimación de distribuciones fueron originalmente diseñados para resolver problemas con dominio de valores reales o enteros, en esta contribución se utilizan para la resolución de un problema basado en permutaciones. El ruteo de autobuses escolares con selección de paradas es resuelto utilizando la distribución generalizada de Mallows como un intento para describir y obtener una distribución de probabilidad explicita sobre un conjunto de rutas de autobuses escolares. Además, un operador de mutación es considerado para mejorar la estimación de la permutación central, un parámetro de la distribución de Mallows. Diferentes y diversas instancias sirvieron como parámetro de entrada y prueba para mostrar que problemas basados en permutaciones tales como el ruteo de autobuses escolares con selección de paradas pueden ser resueltos por medio de un modelo de probabilidad, y mejorar la estimación de la permutación central ayuda al desempeño del algoritmo.

Abstract

Although the estimation of distribution algorithms were originally designed for solving integer or real-valued domains, this contribution applies the algorithms mentioned to deal with a permutation-based problem, called school bus routing problem with bus stop selection, using the generalized Mallows distribution as an attempt to describe and obtain an explicit probability distribution over a set of school bus routes. In addition, a mutation operator is considered for improving the estimation of the central permutation, a parameter of the Mallows distribution. Different and diverse instances served as input and test parameters in order to show that permutation-based optimization problems such as the school bus routing problem with bus stop selection can be solved by means of a probability model, and improving the estimation of the central permutation helps the performance of the algorithm.

Referencias no citadas

Afifi et al., 2015, Aquino-Santos et al., 2009, Barbucha, 2014, Berghida y Boukra, 2015, Borda, 1784, Ceberio et al., 2014, Ceberio et al., 2011, Chakraborty y Dastidar, 1993, Cruz-Ramírez y Martínez-Morales, 1997, de Armas y Melián-Batista, 2015, Díaz-Parra et al., 2013, Euchi y Mraihi, 2012, Fligner y Verducci, 1986, Fligner y Verducci, 1988, Gan et al., 2014, Gintner et al., 2008, Kliewer et al., 2006, Kwan et al., 1999, Larrañaga y Lozano, 2002, Li et al., 2014, Mallows, 1957, Meila et al., 2007, Minocha y Tripathi, 2014, Nalepa y Blocho, 2015, Niu, 2013, Pacheco et al., 2013, Park y Kim, 2010, Pérez-Rodríguez y Hernández-Aguirre, 2016, Prins, 2004, Riera-Ledesma y Salazar-González, 2012, Schittekat et al., 2013, Schwarze y Voß, 2015, Soonpracha et al., 2015, Suiter y Cooley, 2001, Thangiah et al., 2008, Toth, 2001, Widuch, 2012, Widuch, 2013, Yang et al., 2015 and Yoshihara, 2003.