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

Ricardo Pérez-Rodríguez, Arturo Hernández-Aguirre

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

Texto completo:

PDF

Referencias

Afifi S., Dang D.-C., Moukrim, A., 2015. Heuristic solutions for the vehicle routing problem with time windows and synchronized visits. Optimization Letters, DOI 10.1007/s11590-015-0878-3.

Aquino-Santos R., González-Potes A., Villaseñor-González L.A., Crespo A., Sánchez J., Gallardo J.R., 2009. 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(1), 75-83.

Barbucha D., 2014. Team of A-Teams Approach for Vehicle Routing Problem with Time Windows. In Terrazas G., Otero F., Masegosa A., (Eds.), Nature Inspired Cooperative Strategies for Optimization (NICSO 2013), Springer International Publishing, Vol. 512, pp. 273-286.

Berghida M., Boukra A., 2015. 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(9-12), 1711-1725.

Borda J., 1784. Memoire sur les elections au scrutin. Histoire de l'Academie Royale des Science.

Ceberio J., Irurozki E., Mendiburu A., Lozano J., 2014. A distance-based ranking model estimation of distribution algorithm for the flowshop scheduling problem. IEEE Transaction on evolutionary computation 18(2), 286-300.

Ceberio J., Mendiburu A., Lozano J., 2011. Introducing the Mallows Model on Estimation of Distribution Algorithms. In Bao-Liang L., Liqing Z., Kwok J., (Eds.), Neural Information Processing. 18th International Conference ICONIP 2011, Shanghai China, Berlin: Springer Berlin Heidelberg, pp. 461-470.

Chakraborty, U.K., Dastidar, D.G., 1993. Using reliability analysis to estimate the number of generations to convergence in genetic algorithms. Information Processing Letters. 46, 199-209.

Cruz-Ramírez N., Martínez-Morales M., 1997. Un algoritmo para generar redes Bayesianas a partir de datos estadísticos. Primer Encuentro Nacional de Computación, ENC 97. Querétaro, México.

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 O., Ruiz-Vanoye J., Buenabad-Arias M., Canepa-Saenz A., 2013. Vertical Transfer Algorithm for the School Bus Routing Problem. In Gavrilova M., Tan C., Abraham A., (Eds.), Transactions on Computational Science XXI, Springer Berlin Heidelberg, Vol. 8160, pp. 211-229.

Euchi J., Mraihi R., 2012. The urban bus routing problem in the Tunisian case by the hybrid artificial ant colony algorithm. Swarm and Evolutionary Computation 2, 15-24.

Fligner M., Verducci J., 1986. Distance based ranking models. J. Royal Stat. Soc. 48(3), 359-369.

Fligner M., Verducci J., 1988. Multistage ranking models. J. Amer. Stat. Assoc. 83(403), 892-901.

Gan X., Kuang J., Niu B., 2014. Multi-type Vehicle Routing Problem with Time Windows. In Huang D.-S., Jo K.-H., Wang L., (Eds.), Intelligent Computing Methodologies, Springer International Publishing, Vol. 8589, pp. 808-815.

Gintner V., Kliewer N., Suhl L., 2008. A Crew Scheduling Approach for Public Transit Enhanced with Aspects from Vehicle Scheduling. In Hickman M., Mirchandani P., Voß S., (Eds.), Computer-aided Systems in Public Transport, Springer Berlin Heidelberg, Vol. 600, pp. 25-42.

Kliewer N., Mellouli T., Suhl L., 2006. A time–space network based exact optimization model for multi-depot bus scheduling. European Journal of Operational Research 175(3), 1616-1627.

Kwan A., Kwan R., Wren A., 1999. Driver Scheduling Using Genetic Algorithms with Embedded Combinatorial Traits. In Wilson N., (Ed.), Computer-Aided Transit Scheduling, Springer Berlin Heidelberg, Vol. 471, pp. 81-102.

Larrañaga P., Lozano J., 2002. Estimation of distribution algorithms: a new tool for evolutionary computation. Kluwer Academic Publishers.

Li J., Li Y., Pardalos P., 2014. Multi-depot vehicle routing problem with time windows under shared depot resources. Journal of Combinatorial Optimization, DOI 10.1007/s10878-014-9767-4.

Mallows C., 1957. Nonnull ranking models. Biometrika 44(1-2), 114-130.

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 B., Tripathi S., 2014. Solving School Bus Routing Problem Using Hybrid Genetic Algorithm: A Case Study. In Babu B., Nagar A., Deep K., Pant M., Bansal J., Ray K., Gupta U., (Eds.), Proceedings of the Second International Conference on Soft Computing for Problem Solving SocProS 2012, Springer India, Vol. 236, pp. 93-103.

Nalepa J., Blocho M., 2015. Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows. Soft Computing, DOI 10.1007/s00500-015-1642-4.

Niu H., 2013. Application of Genetic Algorithm to Optimize Transit Schedule under Time-Dependent Demand. In Wang W., Wets G., (Eds.), Computational Intelligence for Traffic and Mobility, Atlantis Press, Vol. 8, pp. 71-88.

Pacheco J., Caballero R., Laguna M., Molina J., 2013. Bi-Objective Bus Routing: An Application to School Buses in Rural Areas. Transportation Science 47(3), 397-411.

Park J., Kim B., 2010. The school bus routing problem: A review. European Journal of Operational Research 202(2), 311-319.

Pérez-Rodríguez R., Hernández-Aguirre A., 2016. Probability model to solve the school bus routing problem with stops selection. International Journal of Combinatorial Optimization Problems and Informatics 7(1), 30-39.

Prins C., 2004. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research 31(12), 1985-2002.

Riera-Ledesma J., Salazar-González J., 2012. Solving school bus routing using the multiple vehicle traveling purchaser problem: A branch-and-cut approach. Computers & Operations Research 39(2), 391-404.

Schittekat P., Kinable J., Sörensen K., Sevaux M., Spieksma F., Springael J., 2013. A metaheuristic for the school bus routing problem with bus stop selection. European Journal of Operational Research 229(2), 518-528.

Schwarze S., Voß S., 2015. A Bicriteria Skill Vehicle Routing Problem with Time Windows and an Application to Pushback Operations at Airports. In Dethloff J., Haasis H.-D., Kopfer H., Kotzab H., Schönberger J., (Eds.), Logistics Management (Vols. Products, Actors, Technology - Proceedings of the German Academic Association for Business Research, Bremen, 2013), Springer International Publishing, pp. 289-300.

Soonpracha K., Mungwattana A., Manisri T., 2015. A Re-constructed MetaHeuristic Algorithm for Robust Fleet Size and Mix Vehicle Routing Problem with Time Windows under Uncertain Demands. In Handa H., Ishibuchi H., Ong Y.-S., Tan K.-C., (Eds.), Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems, Springer International Publishing, Vol. 2, pp. 347-361.

Suiter J., Cooley D., 2001. Optimal Municipal Bus Routing Using a Genetic Algorithm. In Kůrková V., Neruda R., Kárný M., Steele N., (Eds.), Artificial Neural Nets and Genetic Algorithms, Springer Vienna, pp. 312- 315.

Thangiah S., Fergany A., Wilson B., Pitluga A., Mennell W., 2008. School Bus Routing in Rural School Districts. In Hickman M., Mirchandani P., Voß S., (Eds.), Computer-aided Systems in Public Transport, Springer Berlin Heidelberg, Vol. 600, pp. 209-232.

Toth P., Vigo D., (Eds.), 2001. The Vehicle Routing Problem. Philadelphia, PA, USA: SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics.

Widuch J., 2012. A label correcting algorithm for the bus routing problem. Fundamenta Informaticae 118(3), 305-326.

Widuch J. 2013. A label correcting algorithm with storing partial solutions to solving the bus routing problem. Informatica 24(3), 461-484.

Yang C., Guo Z.-x., Liu, L.-y., 2015. Comparison Study on Algorithms for Vehicle Routing Problem with Time Windows. In Qi E., Shen J., Dou R., Proceedings of the 21st International Conference on Industrial Engineering and Engineering Management 2014, Atlantis Press, pp. 257-260.

Yoshihara I., 2003. Scheduling of Bus Drivers’ Service by a Genetic Algorithm. In Ghosh A., Tsutsui S., (Eds.), Advances in Evolutionary Computing, Springer Berlin Heidelberg, pp. 799-817.Able, B., 1945. Nombre del artículo. Nombre de la revista 35, 123–126. DOI: 10.3923/ijbc.2010.190.202

Abstract Views

779
Metrics Loading ...

Metrics powered by PLOS ALM


 

Citado por (artículos incluidos en Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Algorithm 989
Ekhine Irurozki, Josu Ceberio, Josean Santamaria, Roberto Santana, Alexander Mendiburu
ACM Transactions on Mathematical Software  vol: 44  num.: 4  primera página: 1  año: 2018  
doi: 10.1145/3206429



Creative Commons License

Esta revista se publica bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)

Universitat Politècnica de València     https://doi.org/10.4995/riai

e-ISSN: 1697-7920     ISSN: 1697-7912