Keywords
optimization
hybrid algorithms
logistic
heurísticas
optimización
algoritmos híbridos
logística
How to Cite
Abstract
In this work, we present two matheuristic techniques based on two heuristic techniques: Ant system (AS), method of musical composition (MMC) and two exact methods: Primal-dual algorithm (PDA) and dual
simplex algorithm (DSA). These techniques are denoted as DS-AS-PDA and DS-MMC-AS and are characterized by taking advantage of the information of the structure and characteristics of the mathematical model for the vehicle routing problem with time windows (VRP-TW). In order to characterize the behavior of the techniques proposed in this work, we use 29 test instances for the VRP-TW. The numerical results show that DS-AS-PDA and DS-MMC-AS exhibit robust behavior and are capable of generating the best solutions reported in the literature with a smaller number of calls to the objective function.
References
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