Ir al contenido

Documat

Matheurísticas para resolver el problema de ruteo de vehículos con ventanas de tiempo

  • Autores: Edwin Montes Orozco, Román Anselmo Mora Gutiérrez, Bibiana Obregón Quintana, Sergio Gerardo de los Cobos Silva, Eric Alfredo Rincón García, Miguel Ángel Gutiérrez Andrade, Pedro Lara Velázquez
  • Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 27, Nº. 2, 2020, págs. 305-332
  • Idioma: español
  • DOI: 10.15517/RMTA.V27I2.37889
  • Títulos paralelos:
    • heuristics; optimization; hybrid algorithms; logistic.
  • Enlaces
  • Resumen
    • español

      En este trabajo, se presentan dos técnicas matheurísticas basadas en dos técnicas heurísticas: Sistema de hormigas (AS), método de composición musical (MMC) y dos métodos exactos: Algoritmo primal-dual (PDA) y algoritmo simplex dual (DSA). Estas técnicas se denotan como DS-ASPDA y DS-MMC-AS y se caracterizan por aprovechar la información de la estructura y características del modelo matemático para el problema de ruteo de vehículos con ventanas de tiempo (VRP-TW). Con el objetivo de caracterizar el comportamiento de las técnicas propuestas en este trabajo, se utilizaron 29 instancias de prueba para el VRP-TW. Los resultados numéricos, muestran que DS-AS-PDA y DS-MMC-AS presentan un comportamiento robusto y son capaces de generar las mejores soluciones reportadas en la literatura con un número menor de llamadas a la función objetivo para diversos tamaños de instancias.

    • English

      In this work, we present two matheuristic techniques based on twoheuristic techniques: Ant system (AS), method of musical composition(MMC) and two exact methods: Primal-dual algorithm (PDA) and dualsimplex algorithm (DSA). These techniques are denoted as DS-AS-PDAand DS-MMC-AS and are characterized by taking advantage of the in-formation of the structure and characteristics of the mathematical modelfor the vehicle routing problem with time windows (VRP-TW). In orderto characterize the behavior of the techniques proposed in this work, weuse 29 test instances for the VRP-TW. The numerical results show thatDS-AS-PDA and DS-MMC-AS exhibit robust behavior and are capableof generating the best solutions reported in the literature with a smallernumber of calls to the objective function.

  • Referencias bibliográficas
    • [1] M. Alzaqebah, S. Abdullah, S. Jawarneh, Modified artificial bee colony for the vehicle routing problems with time windows, SpringerPlus...
    • [2] M. Batsyn, I. Bychkov, L. Komosko, A. Nikolaev, Tabu search for fleet size and mix vehicle routing problem with hard and soft time windows,...
    • [3] M.A. Boschetti, V. Maniezzo, M. Roffilli, A. Bolufé Röhler, Matheuristics: Optimization, simulation and control, in: M.J. Blesa, C. Blum,...
    • [4] I. Bychkov, M. Batsyn, A hybrid approach for the capacitated vehicle routing problem with time windows, in: Optimization Problems and...
    • [5] M. Caserta, S. Voß, Metaheuristics: Intelligent problem solving, in: V. Maniezzo, T. Stützle, S. Voß (Eds.) Matheuristics. Hybridizing...
    • [6] B. Chen, R. Qu, R. Bai, H. Ishibuchi, A variable neighbourhood search algorithm with compound neighbourhoods for VRPTW, Proceedings of...
    • [7] J.F. Cordeau, G. Desaulniers, J. Desrosiers, M.M. Solomon, F. Soumis, The VRP with time windows, Les Cahiers du GERAD, G99-13, 2000, pp....
    • [8] J.F. Cordeau, G. Laporte, The dial-a-ride problem: models and algorithms, Annals of Operations Research 153(2007), no. 1, 29–46. Doi:...
    • [9] G.B. Dantzig, Linear Programming and Extensions, Princeton University Press, The Rand Corporation, Princeton NJ, 1963. Doi: 10.7249/R366
    • [10] G.B. Dantzig, L.R. Ford, D.R. Fulkerson, A primal-dual algorithm for linear programs, in: H.W. Kuhn & A.W. Tucker (Eds.) Linear Inequalities...
    • [11] S.G. De-Los-Cobos-Silva, R.A. Mora-Gutiérrez, M.A. GutiérrezAndrade, E.A. Rincón-García, A. Ponsich, P. Lara Velázquez, Development of...
    • [12] M. Dorigo, V. Maniezzo, A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and...
    • [13] M.X. Goemans, D.P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, in:...
    • [14] Gurobi Optimizer Inc., Gurobi optimizer reference manual, G. Optimization, Inc., 2019. https://www.gurobi. com/wp-content/plugins/hd_documentations/documentation/9.0/refman.pdf
    • [15] D. Karaboga, B. Basturk, Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems, in: P. Melin,...
    • [16] J.K. Lenstra, A.H.G. Rinooy Kan, Complexity of vehicle routing and scheduling problems, Networks 11(1981), no. 2, 221–227. Doi: 10.1002/net.3230110211
    • [17] T.Y. Ma, A cross entropy multiagent learning algorithm for solving vehicle routing problems with time windows, in: J.W. Böse, H. Hu,...
    • [18] E. Montes-Orozco, Metaheurísticas para el problema de ruteo de vehículos con ventanas de tiempo (VRP TW), Master’s thesis, Universidad...
    • [19] R.A. Mora-Gutiérrez, J. Ramírez-Rodríguez, E.A. Rincón-García, An optimization algorithm inspired by musical composition, Artificial...
    • [20] R.A. Mora-Gutiérrez, J. Ramírez-Rodríguez, E.A. RincónGarcía, A. Ponsich, O. Herrera, P. Lara-Velázquez, Adaptation of the musical composition...
    • [21] C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, New York, 1998
    • [22] H.G.M. Pullen, M.H.J. Webb, A computer application to a transport scheduling problem, The Computer Journal 10(1967), no. 1, 10–13. Doi:...
    • [23] A.K. Qin, P.N. Suganthan, Self-adaptive differential evolution algorithm for numerical optimization, in: Evolutionary Computation, The...
    • [24] P.P. Repoussis, C.D. Tarantilis, G. Ioannou, Arc-guided evolutionary algorithm for the vehicle routing problem with time windows, IEEE...
    • [25] D.M. Ryan, C. Hjorring, F. Glover, Extensions of the petal method for vehicle routing, Journal of the Operational Research Society 44(1993),...
    • [26] T. Saeheaw, N. Charoenchai, Comparison of meta-heuristic algorithms for vehicle routing problem with time windows, in: H.A Sulaiman et...
    • [27] M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 35(1987),...
    • [28] P. Toth, D. Vigo, The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia, 2002. Doi: 10.1137/1.9780898718515
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno