x

¿Aún no está registrado?

Cree su cuenta. Regístrese en Elsevier y obtendrá: información relevante, máxima actualización y promociones exclusivas.

Registrarme ahora
Ayuda - - Regístrese - Teléfono 902 888 740
Buscar en

FI 2016

0,500
© Thomson Reuters, Journal Citation Reports, 2016

Indexada en:

SCIE /JCR, Scopus, ScienceDirect

Métricas

  • Factor de Impacto: 0,500(2016)
  • 5-años Factor de Impacto: 0,344
  • SCImago Journal Rank (SJR):0,212
  • Source Normalized Impact per Paper (SNIP):0,308

© Thomson Reuters, Journal Citation Reports, 2016

Revista Iberoamericana de Automática e Informática industrial 2017;14:288-98 - DOI: 10.1016/j.riai.2017.05.002
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
Ricardo Pérez-Rodrígueza,, , 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
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.

Palabras clave
Algoritmo de estimación de distribuciones, distribución de Mallows, problema de ruteo de vehículos, problema de ruteo de autobuses escolares
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), http://dx.doi.org/10.1007/s11590-015-0878-3
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), http://dx.doi.org/10.1007/s10878-014-9767-4
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 http://dx.doi.org/10.1111/apa.13961
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 http://dx.doi.org/10.1111/apa.13961
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
Autor para correspondencia. (Ricardo Pérez-Rodríguez ricardo.perez@cimat.mx)
Copyright © 2017