Buscar en
Revista Iberoamericana de Automática e Informática Industrial RIAI
Toda la web
Inicio Revista Iberoamericana de Automática e Informática Industrial RIAI Un Algoritmo de Estimación de Distribuciones copulado con la Distribución Gene...
Información de la revista
Vol. 14. Núm. 3.
Páginas 288-298 (Julio - Septiembre 2017)
Compartir
Compartir
Descargar PDF
Más opciones de artículo
Visitas
1859
Vol. 14. Núm. 3.
Páginas 288-298 (Julio - Septiembre 2017)
Open Access
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
An estimation of distribution algorithm coupled with the generalized Mallows distribution for a school bus routing problem with bus stop selection
Visitas
1859
Ricardo Pérez-Rodrígueza,
Autor para correspondencia
ricardo.perez@cimat.mx

Autor para correspondencia.
, Arturo Hernández-Aguirreb
a CONACYT - Centro de Investigación en Matemáticas CIMAT, A.C. Fray Bartolomé de las Casas 314, Barrio la Estación, C.P. 20259, Aguascalientes, Ags, México
b Centro de Investigación en Matemáticas CIMAT, A.C. Callejón de Jalisco s/n, Mineral de Valenciana, C.P. 36240, Guanajuato, Gto, México
Este artículo ha recibido

Under a Creative Commons license
Información del artículo
Resumen
Texto completo
Bibliografía
Descargar PDF
Estadísticas
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.

Palabras clave:
Algoritmo de estimación de distribuciones
distribución de Mallows
problema de ruteo de vehículos
problema de ruteo de autobuses escolares
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.

Keywords:
Estimation of distribution algorithm
Mallows distribution
vehicle routing problem
school bus routing problem
Referencias
[Afifi et al., 2015]
S. Afifi, D.-C. Dang, A. Moukrim.
Heuristic solutions for the vehicle routing problem with time windows and synchronized visits.
Optimization Letters, (2015),
[Aquino-Santos et al., 2009]
R. Aquino-Santos, A. González-Potes, L.A. Villaseñor-González, A. Crespo, J. Sánchez, J.R. Gallardo.
Simulación de Algoritmos para regular el Flujo Vehicular y la Comunicación entre Vehículos Móviles Autónomos utilizando Redes Ad Hoc.
RIAI, 6 (2009), pp. 75-83
[Barbucha, 2014]
D. Barbucha.
Team of A-Teams Approach for Vehicle Routing Problem with Time Windows.
pp. 273-286
[Berghida y Boukra, 2015]
M. Berghida, A. Boukra.
EBBO: an enhanced biogeography-based optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows.
The International Journal of Advanced Manufacturing Technology, 77 (2015), pp. 1711-1725
[Borda, 1784]
J. Borda.
Memoire sur les elections au scrutin.
Histoire de l’Academie Royale des Science, (1784),
[Ceberio et al., 2014]
J. Ceberio, E. Irurozki, A. Mendiburu, J. Lozano.
A distance-based ranking model estimation of distribution algorithm for the flowshop scheduling problem.
IEEE Transaction on evolutionary computation, 18 (2014), pp. 286-300
[Ceberio et al., 2011]
J. Ceberio, A. Mendiburu, J. Lozano.
Introducing the Mallows Model on Estimation of Distribution Algorithms.
Neural Information Processing. 18th International Conference ICONIP 2011, pp. 461-470
[Chakraborty y Dastidar, 1993]
U.K. Chakraborty, D.G. Dastidar.
Using reliability analysis to estimate the number of generations to convergence in genetic algorithms.
Information Processing Letters, 46 (1993), pp. 199-209
[Cruz-Ramírez y Martínez-Morales, 1997]
N. Cruz-Ramírez, M. Martínez-Morales.
Un algoritmo para generar redes Bayesianas a partir de datos estadísticos.
Primer Encuentro Nacional de Computación, ENC 97, (1997),
[de Armas y Melián-Batista, 2015]
de Armas J., Melián-Batista B., 2015. Constrained dynamic vehicle routing problems with time windows. Soft Computing, DOI 10.1007/s00500-014-1574-4.
[Díaz-Parra et al., 2013]
O. Díaz-Parra, J. Ruiz-Vanoye, M. Buenabad-Arias, A. Canepa-Saenz.
Vertical Transfer Algorithm for the School Bus Routing Problem.
pp. 211-229
[Euchi y Mraihi, 2012]
J. Euchi, R. Mraihi.
The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm.
Swarm and Evolutionary Computation, 2 (2012), pp. 15-24
[Fligner y Verducci, 1986]
M. Fligner, J. Verducci.
Distance based ranking models.
J. Royal Stat. Soc., 48 (1986), pp. 359-369
[Fligner y Verducci, 1988]
M. Fligner, J. Verducci.
Multistage ranking models.
J. Amer. Stat. Assoc., 83 (1988), pp. 892-901
[Gan et al., 2014]
X. Gan, J. Kuang, B. Niu.
Multi-type Vehicle Routing Problem with Time Windows.
pp. 808-815
[Gintner et al., 2008]
V. Gintner, N. Kliewer, L. Suhl.
A Crew Scheduling Approach for Public Transit Enhanced with Aspects from Vehicle Scheduling.
pp. 25-42
[Kliewer et al., 2006]
N. Kliewer, T. Mellouli, L. Suhl.
A time–space network based exact optimization model for multi-depot bus scheduling.
European Journal of Operational Research, 175 (2006), pp. 1616-1627
[Kwan et al., 1999]
A. Kwan, R. Kwan, A. Wren.
Driver Scheduling Using Genetic Algorithms with Embedded Combinatorial Traits.
pp. 81-102
[Larrañaga y Lozano, 2002]
P. Larrañaga, J. Lozano.
Estimation of distribution algorithms: a new tool for evolutionary computation.
Kluwer Academic Publishers, (2002),
[Li et al., 2014]
J. Li, Y. Li, P. Pardalos.
Multi-depot vehicle routing problem with time windows under shared depot resources.
Journal of Combinatorial Optimization, (2014),
[Mallows, 1957]
C. Mallows.
Nonnull ranking models.
Biometrika, 44 (1957), pp. 114-130
[Meila et al., 2007]
Meila M., Phadnis K., Patterson A., Bilmes J., 2007. Consensus ranking under the exponential model. Proc. 22nd Conf. Uncertainty Artif. Intell., Vancouver, pp. 285-294.
[Minocha y Tripathi, 2014]
B. Minocha, S. Tripathi.
Solving School Bus Routing Problem Using Hybrid Genetic Algorithm: A Case Study.
pp. 93-103
[Nalepa y Blocho, 2015]
J. Nalepa, M. Blocho.
Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows.
[Niu, 2013]
H. Niu.
Application of Genetic Algorithm to Optimize Transit Schedule under Time-Dependent Demand.
pp. 71-88
[Pacheco et al., 2013]
J. Pacheco, R. Caballero, M. Laguna, J. Molina.
Bi-Objective Bus Routing: An Application to School Buses in Rural Areas.
Transportation Science, 47 (2013), pp. 397-411
[Park y Kim, 2010]
J. Park, B. Kim.
The school bus routing problem: A review.
European Journal of Operational Research, 202 (2010), pp. 311-319
[Pérez-Rodríguez y Hernández-Aguirre, 2016]
R. Pérez-Rodríguez, A. Hernández-Aguirre.
Probability model to solve the school bus routing problem with stops selection.
International Journal of Combinatorial Optimization Problems and Informatics, 7 (2016), pp. 30-39
[Prins, 2004]
C. Prins.
A simple and effective evolutionary algorithm for the vehicle routing problem.
Computers & Operations Research, 31 (2004), pp. 1985-2002
[Riera-Ledesma y Salazar-González, 2012]
J. Riera-Ledesma, J. Salazar-González.
Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach.
Computers & Operations Research, 39 (2012), pp. 391-404
[Schittekat et al., 2013]
P. Schittekat, J. Kinable, K. Sörensen, M. Sevaux, F. Spieksma, J. Springael.
A metaheuristic for the school bus routing problem with bus stop selection.
European Journal of Operational Research, 229 (2013), pp. 518-528
[Schwarze y Voß, 2015]
S. Schwarze, S. Voß.
A Bicriteria Skill Vehicle Routing Problem with Time Windows and an Application to Pushback Operations at Airports.
Logistics Management (Vols. Products, Actors, Technology - Proceedings of the German Academic Association for Business Research, Bremen, 2013), pp. 289-300
[Soonpracha et al., 2015]
K. Soonpracha, A. Mungwattana, T. Manisri.
A Re-constructed Meta-Heuristic Algorithm for Robust Fleet Size and Mix Vehicle Routing Problem with Time Windows under Uncertain Demands.
pp. 347-361
[Suiter y Cooley, 2001]
J. Suiter, D. Cooley.
Optimal Municipal Bus Routing Using a Genetic Algorithm.
Artificial Neural Nets and Genetic Algorithms, pp. 312-315
[Thangiah et al., 2008]
S. Thangiah, A. Fergany, B. Wilson, A. Pitluga, W. Mennell.
School Bus Routing in Rural School Districts.
pp. 209-232
[Toth, 2001]
The Vehicle Routing Problem.,
[Widuch, 2012]
J. Widuch.
A label correcting algorithm for the bus routing problem.
Fundamenta Informaticae, 118 (2012), pp. 305-326
[Widuch, 2013]
J. Widuch.
A label correcting algorithm with storing partial solutions to solving the bus routing problem.
Informatica, 24 (2013), pp. 461-484
[Yang et al., 2015]
C. Yang, Z.-x. Guo, L.-y. Liu.
Comparison Study on Algorithms for Vehicle Routing Problem with Time Windows.
Proceedings of the 21st International Conference on Industrial Engineering and Engineering Management 2014, pp. 257-260
[Yoshihara, 2003]
I. Yoshihara.
Scheduling of Bus Drivers’ Service by a Genetic Algorithm.
Advances in Evolutionary Computing, pp. 799-817
Able, B., 1945. Nombre del artículo. Nombre de la revista 35, 123–126. DOI: 10.3923/ijbc.2010.190.202
Opciones de artículo
Herramientas