An efficient General Variable Neighborhood Search for large Travelling Salesman Problem with Time Windows
DOI:
https://doi.org/10.2298/YJOR120530015MKeywords:
Travelling Salesman Problem, Time windows, Variable Neighborhood SearchAbstract
General Variable Neighborhood Search (GVNS) is shown to be a powerful and robust methodology for solving travelling salesman and vehicle routing problems. However, its efficient implementation may play a significant role in solving large size instances. In this paper we suggest new GVNS heuristic for solving Travelling salesman problem with time windows. It uses different set of neighborhoods, new feasibility checking procedure and a more efficient data structure than the recent GVNS method that can be considered as a state-of-the-art heuristic. As a result, our GVNS is much faster and more effective than the previous GVNS. It is able to improve 14 out of 25 best known solutions for large test instances from the literature.References
Ascheuer, N., Fischetti, M., and Grötschel, M., “Solving asymmetric travelling salesman problem with time windows by branch-and-cut”, Mathematical Programming, 90 (2001) 475-506.
Calvo, R.W., “A new heuristic for the travelling salesman problem with time windows”, Transportation Science, 34 (2000) 113-124.
Carlton, W.B., and Barnes, J.W., “Solving the travelling salesman problem with time windows using tabu search”, IEEE Transactions, 28 (1996) 617-629.
Cvetković, D., Cangalović, M., and Kovacevic-Vujcić, V., “Semidefinite relaxations of the traveling salesman problem”, Yugoslav Journal of Operations Research, 9 (1999) 158-167.
Da Silva, R.F., and Urrutia, S., “A General VNS heuristic for the travelling salesman problem with time windows”, Discrete Optimization, 7 (2010) 203-211.
Dumas, Y., Desrosiers, J., Gelinas, E., and Solomon, M., “An optimal algorithm for the travelling salesman problem with time windows”, Operations Research, 43 (1995) 367-371.
Gendreau, M., Hertz, A., and Laporte, G., “New insertion and postoptimization procedures for the travelling salesman problem”, Operations Research, 40 (1992) 1086-1094.
Gendreau, M., Hertz, A., Laporte, G., and Stan, M., “A generalized insertion heuristic for the travelling salesman problem with time windows”, Operation Research, 46 (1998) 330-335.
Hansen, P., Mladenović, N., and Moreno-Pérez, J.A., “Variable neighbourhood search: methods and applications (invited survey)”, 4OR, 6 (2008) 319-360.
Hansen, P., Mladenović, N., and Moreno-Pérez, J.A., “Variable neighbourhood search: methods and applications (invited survey)”, Annals of Operation Research, 175 (2010) 367-407.
Langevin, A., Desrochers, M., Desrosiers, J., Gélinas, S., and Soumis, F., “A two-commodity flow formulation for the travelling salesman and makespan problems with time windows”, Networks, 23 (1993) 631-640.
Lopez-Ibanez, M., and Blum, C., “Beam-ACO for the travelling salesman problem with time windows”, Computers and Operations Research, 37 (2010) 1570-1583.
Mladenović, N., and Hansen, P., “Variable neighborhood search”, Computers and Operations Research, 24 (1997) 1097-1100.
Monnot, J., “Approximation results toward nearest neighbor heuristic”, Yugoslav Journal of Operations Research, 12 (2002) 11-16.
Ohlmann, J.W., and Thomas, B.W., “A compressed-annealing heuristic for the travelling salesman problem with time windows”, INFORMS Journal on Computing, 19 (2007) 80-90.
Pesant, G., Gendreau, M., Potvin, J.Y., and Rousseau, J.M., “An exact constraint logic programming algorithm for the travelling salesman problem with time windows”, Transportation Science, 32 (1998) 12-29.
Pop, P., and Popistar, C., “A new efficient transformation of the generalized vehicle routing problem into the classical vehicle routing problem”, Yugoslav Journal of Operations Research, 21 (2011) 187-198.
Potvin, J.Y., and Bengio, S., “The vehicle routing problem with time windows part II: genetic search”, INFORMS Journal on Computing, 8 (1996) 165-172.
Downloads
Published
Issue
Section
License
Copyright (c) 2013 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
