Palabras clave
optimization
hybrid algorithms
logistic
heurísticas
optimización
algoritmos híbridos
logística
Cómo citar
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.
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