Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://www.revistas.ucr.ac.cr/index.php/matematica/oai
Matheurísticas para resolver el problema de ruteo de vehículos con ventanas de tiempo
PDF
PS
DVI

Palabras clave

heuristics
optimization
hybrid algorithms
logistic
heurísticas
optimización
algoritmos híbridos
logística

Cómo citar

Montes-Orozco, E., Mora-Gutiérrez, R. A., Obregón-Quintana, B., De-Los-Cobos-Silva, S. G., Rincón-García, E. A., Gutiérrez-Andrade, M. A., & Lara-Velázquez, P. (2020). Matheurísticas para resolver el problema de ruteo de vehículos con ventanas de tiempo. Revista De Matemática: Teoría Y Aplicaciones, 27(2), 305–332. https://doi.org/10.15517/rmta.v27i2.37889

Resumen

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.

https://doi.org/10.15517/rmta.v27i2.37889
PDF
PS
DVI

Citas

M. Alzaqebah, S. Abdullah, S. Jawarneh, Modified artificial bee colony for the vehicle routing problems with time windows, SpringerPlus 5(2016), 1298. Doi: 10.1186/s40064-016-2940-8

M. Batsyn, I. Bychkov, L. Komosko, A. Nikolaev, Tabu search for fleet size and mix vehicle routing problem with hard and soft time windows, in: V.A. Kalyagin, P.M. Pardalos, O. Prokopyev, I. Utkina (Eds.) Computational Aspects and Applications in Large-Scale Networks, Springer Proceedings in Mathematics & Statistics 247, Springer, Cham, 2018. Doi: 10.1007/978-3-319-96247-4_1

M.A. Boschetti, V. Maniezzo, M. Roffilli, A. Bolufé Röhler, Matheuristics: Optimization, simulation and control, in: M.J. Blesa, C. Blum, L. Di Gaspero, A. Roli, M. Sampels, A. Schaerf (Eds.) Hybrid Metaheuristics, Lecture Notes in Computer Science 5818, Springer, Berlin Heidelberg, 2009, pp. 171–177. Doi: 10.1007/978-3-642-04918-7_13

I. Bychkov, M. Batsyn, A hybrid approach for the capacitated vehicle routing problem with time windows, in: Optimization Problems and their Applications, Omsk, Russia, 2018, pp. 66–81. http://ceur-ws.org/Vol 2098/paper6.pdf

M. Caserta, S. Voß, Metaheuristics: Intelligent problem solving, in: V. Maniezzo, T. Stützle, S. Voß (Eds.) Matheuristics. Hybridizing Metaheuristics and Mathematical Programming, Annals of Information Systems, Vol. 10, Springer, 2009, pp. 1–38. Doi: 10.1007/978-1-4419-1306-7_1

B. Chen, R. Qu, R. Bai, H. Ishibuchi, A variable neighbourhood search algorithm with compound neighbourhoods for VRPTW, Proceedings of 5th the International Conference on Operations Research and Enterprise Systems, Vol. 1, Rome, Italy, 2016, pp. 25–35. Doi: 10.5220/0005661800250035

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. 1–38 http://www.bernabe.dorronsoro.es/vrp/data/articles/VRPTW.pdf

J.F. Cordeau, G. Laporte, The dial-a-ride problem: models and algorithms, Annals of Operations Research 153(2007), no. 1, 29–46. Doi: 10.1007/s10479-007-0170-8

G.B. Dantzig, Linear Programming and Extensions, Princeton University Press, The Rand Corporation, Princeton NJ, 1963. Doi: 10.7249/R366

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 and Related Systems, AM-38, Princeton University Press, Princeton NJ, 1956, pp. 171–181.

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 seven hybrid methods based on collective intelligence for solving nonlinear constrained optimization problems, Artificial Intelligence Review 49(2018), no. 2, 245–279. Doi: 10.1007/s10462-016-9524-4

M. Dorigo, V. Maniezzo, A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 26(1996), no. 1, 29–41. Doi: 10.1109/3477.484436

M.X. Goemans, D.P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, in: D.S. Hochbaum (Ed.) Approximation Algorithms for NPhard Problems, PWS Publishing, New Orleans, 1996: 144–191.Doi: 10.5555/241938.241942

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

D. Karaboga, B. Basturk, Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems, in: P. Melin, O. Castillo, L.T. Aguilar, J. Kacptrzyk, W. Pedrycz (Eds.), Lecture Notes in Artificial Intelligence 4529 Springer, Berlin, 2007. pp. 789–798. Doi: 10.1007/978-3-540-72950-1_77

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

T.Y. Ma, A cross entropy multiagent learning algorithm for solving vehicle routing problems with time windows, in: J.W. Böse, H. Hu, C. Jahn, X. Shi, R. Stahlbock & S. Voß (Eds) Computational Logistics, Lecture Notes in Computer Science 6971, Springer, Berlin, 2011, pp. 59–73. Doi: 10.1007/978-3-642-24264-9_5

E. Montes-Orozco, Metaheurísticas para el problema de ruteo de vehículos con ventanas de tiempo (VRP TW), Master’s thesis, Universidad Autónoma Metropolitana Unidad Azcapotzalco, México, 2017.

R.A. Mora-Gutiérrez, J. Ramírez-Rodríguez, E.A. Rincón-García, An optimization algorithm inspired by musical composition, Artificial Intelligence Review 41(2014), no. 3, 301–315. Doi: 10.1007/s10462-011-9309-8

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 method for solving constrained optimization problems, Soft Computing 18(2014), no. 10, 1931–1948. Doi:10.1007/s00500-013-1177-5

C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, New York, 1998

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: 10.1093/comjnl/10.1.10

A.K. Qin, P.N. Suganthan, Self-adaptive differential evolution algorithm for numerical optimization, in: Evolutionary Computation, The 2005 IEEE Congress on Evolutionary Computation, Edinburgh, Scotland, 2005, pp. 1785–1791. Doi: 10.1109/CEC.2005.1554904

P.P. Repoussis, C.D. Tarantilis, G. Ioannou, Arc-guided evolutionary algorithm for the vehicle routing problem with time windows, IEEE Transactions on Evolutionary Computation, 13(2009), no. 3, 624–647. Doi: 10.1109/TEVC.2008.2011740

D.M. Ryan, C. Hjorring, F. Glover, Extensions of the petal method for vehicle routing, Journal of the Operational Research Society 44(1993), no. 3, 289–296. http://www2.imm.dtu.dk/courses/02735/hjorring.pdf

T. Saeheaw, N. Charoenchai, Comparison of meta-heuristic algorithms for vehicle routing problem with time windows, in: H.A Sulaiman et al. (Eds) Advanced Computer and Communication Engineering Technology, Lecture Notes in Electrical Engineering 362, Springer Switzerland, 2016, pp. 1263–1273. Doi: 10.1007/978-3-319-24584 3_108

M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 35(1987), no. 2, 254–265. Doi: 10.1287/opre.35.2.254

P. Toth, D. Vigo, The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia, 2002. Doi: 10.1137/1.9780898718515

Comentarios

Descargas

Los datos de descargas todavía no están disponibles.