×

zbMATH — the first resource for mathematics

Expanding neighborhood GRASP for the traveling salesman problem. (English) Zbl 1125.90042
Summary: In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.

MSC:
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
GRASP; LKH; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Aarts and J.K. Lenstra, Local Search in Combinatorial Optimization, Wiley and Sons, 1997. · Zbl 0869.00019
[2] D. Applegate, R. Bixby, V. Chvatal, and W. Cook, ”On the solution of traveling salesman problem,” Documenta Mathematica: Proc. Int. Cogr. Mathematica, vol. 3, pp. 645–656, 1998. · Zbl 0904.90165
[3] D. Applegate, R. Bixby, V. Chvatal, and W. Cook, ”Chained Lin-Kernighan for large traveling salesman problems,” Informs Journal on Computing, (to appear).
[4] R. Baralia, J.I. Hildago, and R. Perego, ”A hybrid heuristic for the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, pp. 1–41, 2001. · Zbl 05451905 · doi:10.1109/TEVC.2001.910460
[5] J.L. Bentley, ”Fast algorithms for geometric traveling salesman problems,” ORSA J. Computing, vol. 4, pp. 387–411, 1992. · Zbl 0758.90071
[6] G. Clarke and J.W. Wright, ”Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, vol. 12, pp. 568–581, 1964. · doi:10.1287/opre.12.4.568
[7] T.A. Feo and M.G.C. Resende, ”Greedy randomized adaptive search procedure,” Journal of Global Optimization, vol. 6, pp. 109–133, 1995. · Zbl 0822.90110 · doi:10.1007/BF01096763
[8] P. Festa and M.G.C. Resende, ”GRASP: An annotated bibliography,” in Essays and Surveys on Metaheuristics, C.C. Ribeiro and P. Hansen (Eds.), Kluwer Academic Publishers: Norwell, MA, 2001. · Zbl 1153.90553
[9] R. Garfinkel and G. Nemhauser, Integer Programming, Wiley and Sons, 1972.
[10] M. Gendreau, A. Hertz, and G. Laporte, ”New insertion and postoptimization procedures for the traveling salesman problem,” Operations Research, vol. 40, pp. 1086–1094, 1992. · Zbl 0767.90087 · doi:10.1287/opre.40.6.1086
[11] B.L. Golden and W.R. Stewart, ”Empirical analysis of heuristics,” in the Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, E.L. Lawer, J.K. Lenstra, A.H.G. Rinnoy Kan and D.B. Shmoys (Eds.), Wiley and Sons, 1985, pp. 207–249.
[12] G. Gutin and A. Punnen, The Traveling Salesman Problem and Its Variations, Kluwer Academic Publishers Dordrecht, 2002. · Zbl 0996.00026
[13] P. Hansen and N. Mladenovic, ”Variable neighborhood search: Principles and applications,” European Journal of Operational Research, vol. 130, pp. 449–467, 2001. · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[14] K. Helsgaun, ”An effective implementation of the lin-Kernighan traveling salesman heuristic,” European Journal of Operational Research, vol. 126, pp. 106–130, 2000. · Zbl 0969.90073 · doi:10.1016/S0377-2217(99)00284-2
[15] K. Holmqvist, A. Migdalas, and P.M. Pardalos, ”Parallel continuous non-convex optimization,” in Parallel Computing in Optimization, A. Migdalas, P.M. Pardalos, and S. Storøy (Eds.), Kluwer Academic Publishers, 1997, pp. 471–528. · Zbl 0903.90150
[16] K. Holmqvist, A. Migdalas, and P.M. Pardalos, ”Parallelized heuristics for combinatorial search,” in Parallel Computing in Optimization, A. Migdalas, P.M. Pardalos, and S. Storøy (Eds.), Kluwer Academic Publishers, 1997, pp. 269–294. · Zbl 0896.90158
[17] D.S. Johnson and L.A. McGeoch, ”The traveling salesman problem: A case study,” in Local Search in Combinatorial Optimization, E. Aarts and J.K. Lenstra (Eds.), Wiley and Sons, 1997, pp. 215–310. · Zbl 0947.90612
[18] D.S. Johnson and L.A. McGeoch, ”Experimental Analysis of the STSP,” in the Traveling Salesman Problem and Its Variations, G. Gutin and A. Punnen (Eds.), Kluwer Academic Publishers Dordrecht, 2002, pp. 369– 444. · Zbl 1113.90356
[19] D.S. Johnson and C.H. Papadimitriou, ”Computational complexity,” in the Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, E.L. Lawer, J.K. Lenstra, A.H.D. Rinnoy Kan and D.B. Shmoys (Eds.), Wiley and Sons, 1985, pp. 37–85.
[20] M. Junger, G. Reinhelt, and G. Rinaldi, ”The traveling salesman problem,” in Networks Models, Handbooks in OR and MS, M. Ball et al. (Eds.), Elsevier Science B.V, 1995, vol. 7, pp. 225–330.
[21] G. Laporte, ”The traveling salesman problem: An overview of exact and approximate algorithms,” European Journal of Operational Research, vol. 59, pp. 231–247, 1992. · Zbl 0760.90089 · doi:10.1016/0377-2217(92)90138-Y
[22] E.L. Lawer, J.K. Lenstra, A.H.G. Rinnoy Kan, and D.B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley and Sons, 1985. · Zbl 0562.00014
[23] S. Lin, ”Computer solutions of the traveling salesman problem,” Bell System Technical Journal, vol. 44, pp. 2245–2269, 1965. · Zbl 0136.14705
[24] S. Lin and B.W. Kernighan, ”An effective heuristic algorithm for the traveling salesman problem,” Operation Research, vol. 21, pp. 498–516, 1973. · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[25] Y. Marinakis and A. Migdalas, ”Heuristic solutions of vehicle routing problems in supply chain management,” in Combinatorial and Global Optimization, P.M. Pardalos, A. Migdalas, and R. Burkard (Eds.), World Scientific Publishing Co, 2002, pp. 205–236. · Zbl 1022.90002
[26] A. Modares, S. Somhom, and T. Enwaka, ”A self - organizing neural network approach for multiple traveling salesman and vehicle routing problems,” International Transactions in Operational Research, vol. 6, 1999, pp. 591–606. · doi:10.1111/j.1475-3995.1999.tb00175.x
[27] D. Neto, ”Efficient cluster compensation for Lin–Kernighan heuristics,” PhD Thesis, Computer Science University of Toronto, 1999.
[28] P.M. Pardalos, L. Pitsoulis, and M.G.C. Resende, ”A parallel GRASP implementation for the quadratic assignment problem,” in Solving Irregular Problems in Parallel—State of the Art, A. Ferreira and J. Rolim (Eds.), Kluwer Academic Publishers Dordrecht, 1995. · Zbl 0854.65039
[29] P.M. Pardalos, L. Pitsoulis, T. Mavridou, and M.G.C. Resende, ”Parallel search for combinatorial optimization: Genetic algorithms, simulated annealing, tabu search and GRASP,” in Solving Irregular Problems in Parallel - State of the Art, A. Ferreira and J. Rolim (Eds.), Kluwer Academic Publishers Dordrecht, 1995, pp. 317–331.
[30] G. Reinhelt, The Traveling Salesman Problem, Computational solutions for TSP Applications, Springer-Verlag, 1994.
[31] C. Rego and F. Glover, ”Local search and metaheuristics,” in the Traveling Salesman Problem and Its Variations, G. Gutin and A. Punnen (Eds.), Kluwer Academic Publishers Dordrecht, 2002, pp. 309–367. · Zbl 1113.90370
[32] M.G.C. Resende and C.C. Ribeiro, ”Greedy randomized adaptive search procedures,” in Handbooks of Metaheuristics, F. Glover and G.A. Kochenberger (Eds.), Kluwer Academic Publishers Dordrecht, 2003, pp. 219–249. · Zbl 1102.90384
[33] R. Tarjan, ”Data structures and network algorithms,” Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1983. · Zbl 0584.68077
[34] C. Walshaw, ”A multilevel approach to the traveling salesman problem,” Operations Research, (to appear). · Zbl 1163.90777
[35] M. Zachariasen and M. Dam, ”Tabu search on the geometric traveling salesman problem,” in Meta-heuristics: Theory and Applications, I.H. Osman and J.P. Kelly (Eds.), Kluwer Academic Publishers: Boston, 1996, pp. 571–587. · Zbl 0877.90071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.