Resolviendo el problema de ruteo de vehículos de capacidad con demandas estocásticas aplicando el algoritmo de recocido simulado

Autores/as

  • Ernesto Liñán García Facultad de Sistemas. Universidad Autónoma de Coahuila. Carretera 57, km. 13, Arteaga, Coahuila, México.
  • Linda Crystal Cruz Villegas Sistemas. Universidad Autónoma de Coahuila. Carretera 57, km. 13, Arteaga, Coahuila, México.
  • David Salvador González González Facultad de Sistemas. Universidad Autónoma de Coahuila. Carretera 57, km. 13, Arteaga, Coahuila, México.

DOI:

https://doi.org/10.30973/progmat/2014.6.2/5

Palabras clave:

algoritmo de recocido simulado, algoritmo de ahorro, problema de ruteo de vehículos, metaheurísticas

Resumen

Se propone un nuevo algoritmo híbrido para resolver el problema de ruteo de vehículos de capacidad (CVRP en inglés) con demanda estocástica. Este nuevo enfoque combina los algoritmos de recocido simulado (RS) y de ahorro y es implementado para obtener resultados de varias instancias Solomon del CVRP. El RS es una metaheúristica bioinspirada, una simulación del proceso de calentamiento y enfriamiento de los sólidos para resolver problemas de optimización. Por otro lado, el algoritmo de ahorro es una heurística determinística para resolver el CVRP. Con el objeto de generar soluciones de alta calidad del CVRP, este enfoque aplica el algoritmo de ahorro dentro del ciclo de metrópolis del recocido simulado; la solución inicial del algoritmo también es generada por el algoritmo de ahorro. Este simple cambio ha permitido incrementar la calidad de la solución del CVRP con respecto al recocido simulado clásico y al algoritmo de ahorro.

Biografía del autor/a

Ernesto Liñán García, Facultad de Sistemas. Universidad Autónoma de Coahuila. Carretera 57, km. 13, Arteaga, Coahuila, México.

Ernesto Liñán García has a PhD in Computer Science, MSC in Computer Systems, and Electronic Systems Enginner degree from Instituto Tecnológico y de Estudios Superiores de Monterrey. He is a full Research-Professor in Computer Science at University of Coahuila, Mexico. His research area is metaheuristics applied to NP-hard problems, protein folding problems, DNA alignment sequences, and vehicle routing problems.

Linda Crystal Cruz Villegas, Sistemas. Universidad Autónoma de Coahuila. Carretera 57, km. 13, Arteaga, Coahuila, México.

Linda Crystal Cruz Villegas was born in Monclova, Coahuila, Mexico. She has a Computational Systems Engineer degree from the Faculty of Mechanical and Electrical Engineering of Autonomous University of Coahuila (2007). Currently, she is studying a Master on Applied Engineering with accent on Integral Manufacturing at the Faculty of Systems of the Autonomous University of Coahuila in Saltillo, Coahuila, Mexico. Her interest areas are optimization, metaheuristics, logistics and supply chain.

David Salvador González González, Facultad de Sistemas. Universidad Autónoma de Coahuila. Carretera 57, km. 13, Arteaga, Coahuila, México.

David Salvador González González has a PhD in Science and technology in Industrial and Manufacturing Engineering, a Master in Science and Technology in Industrial Engineering and is an Industrial and systems engineer. He specializes in the development of statistical tools for industrial applications and troubleshooting. Research development in reliability, experimental designs, probabilistic models and application of hybrid models and soft-computing for the solution of industrial problems. Interested in modeling and optimization of industrial processes. Fulltime research professor at University of Coahuila, Mexico.

Citas

Dantzig, G., Fulkerson, R., Johnson, S. Solution of a large-scale traveling-salesman problems. Operations Research. 1954, 2 (4), 393-410. https://doi.org/10.1287/opre.2.4.393

Dantzig, G., Ramser, J. The truck dispatching problem. Management Science. 1959, 6 (1), 80-91. https://doi.org/10.1287/mnsc.6.1.80

Chiang, W. Ch., Russell, R. Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research. 1996, 63 (1), 3-27. https://doi.org/10.1007/BF02601637

Bräysy, O., Dullaert, W., Gendreau, M. Evolutionary algorithms for the vehicle routing problem with time windows. Journal of Heuristics. 2004, 10 (6), 587-611. https://doi.org/10.1007/s10732-005-5431-6

Nagy, G., Salhi, S. Location-routing: Issues, models and methods. European Journal of Operational Research. 2007, 177 (2), 649-672. https://doi.org/10.1016/j.ejor.2006.04.004

Flatberg, T. Dynamic and stochastic aspects in vehicle routing: A literature survey. SINTEF report. Oslo: SINTEF ICT, 2005. ISBN 8214028430.

Bräysy, O., Gendreau, M. Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Science. 2005, 39 (1), 104-118. https://doi.org/10.1287/trsc.1030.0056

Laporte, G., Nobert, Y. Exact algorithms for the vehicle routing problem. Surveys in Combinatorial Optimization. 1987, 31, 147-184. https://doi.org/10.1016/S0304-0208(08)73235-3

Laporte, G. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research. 1992, 59 (3), 345- 358. https://doi.org/10.1016/0377-2217(92)90192-C

Bell, J. E., McMullen, P. R. Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics. 2004, 18 (1), 41-48. https://doi.org/10.1016/j.aei.2004.07.001

Osman, IH. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research. 1993, 41 (1-4), 421- 451. https://doi.org/10.1007/BF02023004

Czech, Z. J., Czarnas, P. Parallel simulated annealing for the vehicle routing problem with time windows. In: 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing. Canary Islands-Spain, 2002, 376-383. https://doi.org/10.1109/EMPDP.2002.994313

Thangiah, S. R. Vehicle routing with time windows using genetic algorithms. In: Chambers, L. (Ed.). The Practical Handbook of Genetic Algorithms: New Frontiers, Volume II. Florida: CRC Press, 1995, 253- 277.

Homberger, J. H. G. A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research. 2005, 162 (1), 220-238. https://doi.org/10.1016/j.ejor.2004.01.027

Garcia, B. L., Potvin, J. Y., Rousseau, J. M. A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints. Computers and Operations Research. 1994, 21 (9), 1025-1033. https://doi.org/10.1016/0305-0548(94)90073-6

Tas, D., Dellaert, N., Van Woensel, T., De Kok, T. Vehicle routing problem with stochastic travel times including soft time windows and service costs. Computers and Operations Research. 2013, 40 (1), 214-224. https://doi.org/10.1016/j.cor.2012.06.008

Kirkpatrick, S., Gelatt, C., Vecchi, M. Optimization by simulated annealing. Science. 1983, 4598, 671-680. https://doi.org/10.1126/science.220.4598.671

Cerny, V. Thermodynamical approach to the traveling salesman problem: An eficient simulation algorithm. Journal of Optimization Theory and Applications. 1985, 45, 41-51. https://doi.org/10.1007/BF00940812

Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E. Equation of state calculations by fast computing machines. The Journal of Chemical Physics. 1953, 21 (6), 1087-1092. https://doi.org/10.1063/1.1699114

Aarts, E., Korst, J. Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial optimization and neural computing. New York: John Wiley and Sons, 1989.

Ingber, L. Simulated annealing: Practice versus theory. Mathematical and Computer Modelling. 1993, 18 (11), 29-57. https://doi.org/10.1016/0895-7177(93)90204-C

Kjaerulff, U. Optimal decomposition of probabilistic networks by simulated annealing. Statistics and Computing. 1992, 2, 7-17. Optimal decomposition of probabilistic networks by simulated annealing

Van Laarhoven, P. J., Aarts, E. H. L. Simulated annealing: Theory and applications. Dordrecht: Kluwer Academic Publishers, 1987. https://doi.org/10.1007/978-94-015-7744-1_2

Clarke, G., Wright, J. W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research. 1964, 12 (4), 568-581. https://doi.org/10.1287/opre.12.4.568

Kao, Y., Chen, M. H., Huang, Y. T. A hybrid algorithm based on ACO and PSO for capacitated vehicle routing problems. Mathematical Problems in Engineering. 2012. Available from: https://doi.org/10.1155/2012/726564

Pichpibul, T., Kawtummachai, R. An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem. Science Asia. 2012, 38, 307- 318.

Mendoza, J. E., Villegas, J. G. A multi-space sampling heuristic for the vehicle routing problem with stochastic demands. Optimization Letters. 2013, 7, 1503-1516. https://doi.org/10.1007/s11590-012-0555-8

Descargas

Publicado

30-06-2014

Cómo citar

Liñán García, E., Cruz Villegas, L. C., & González González, D. S. (2014). Resolviendo el problema de ruteo de vehículos de capacidad con demandas estocásticas aplicando el algoritmo de recocido simulado. Programación matemática Y Software, 6(2), 36–45. https://doi.org/10.30973/progmat/2014.6.2/5

Número

Vol. 6 Núm. 2 (2014): Junio de 2014

Sección

Artículos

Licencia

Derechos de autor 2014 Programación Matemática y Software

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.