[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Expanding Neighborhood GRASP for the Traveling Salesman Problem

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E. Aarts and J.K. Lenstra, Local Search in Combinatorial Optimization, Wiley and Sons, 1997.

  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.

    Google Scholar 

  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.

    Article  Google Scholar 

  5. J.L. Bentley, “Fast algorithms for geometric traveling salesman problems,” ORSA J. Computing, vol. 4, pp. 387–411, 1992.

    Google Scholar 

  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.

    Google Scholar 

  7. T.A. Feo and M.G.C. Resende, “Greedy randomized adaptive search procedure,” Journal of Global Optimization, vol. 6, pp. 109–133, 1995.

    Article  MathSciNet  Google Scholar 

  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.

    Google Scholar 

  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.

    MathSciNet  Google Scholar 

  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.

  13. P. Hansen and N. Mladenovic, “Variable neighborhood search: Principles and applications,” European Journal of Operational Research, vol. 130, pp. 449–467, 2001.

    Article  MathSciNet  Google Scholar 

  14. K. Helsgaun, “An effective implementation of the lin-Kernighan traveling salesman heuristic,” European Journal of Operational Research, vol. 126, pp. 106–130, 2000.

    Article  MathSciNet  Google Scholar 

  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.

  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.

  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.

  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.

  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.

    Article  Google Scholar 

  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.

  23. S. Lin, “Computer solutions of the traveling salesman problem,” Bell System Technical Journal, vol. 44, pp. 2245–2269, 1965.

    Google Scholar 

  24. S. Lin and B.W. Kernighan, “An effective heuristic algorithm for the traveling salesman problem,” Operation Research, vol. 21, pp. 498–516, 1973.

    Google Scholar 

  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.

  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.

    Article  MathSciNet  Google Scholar 

  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.

  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.

  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.

  33. R. Tarjan, “Data structures and network algorithms,” Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1983.

  34. C. Walshaw, “A multilevel approach to the traveling salesman problem,” Operations Research, (to appear).

  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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Decision Support Systems Laboratory, Department of Production Engineering and Management, Technical University of Crete, 73100, Chania, Greece

    Yannis Marinakis & Athanasios Migdalas

  2. Department of Industrial and Systems Engineering, University of Florida, USA

    Panos M. Pardalos

Authors
  1. Yannis Marinakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Athanasios Migdalas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yannis Marinakis.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Marinakis, Y., Migdalas, A. & Pardalos, P.M. Expanding Neighborhood GRASP for the Traveling Salesman Problem. Comput Optim Applic 32, 231–257 (2005). https://doi.org/10.1007/s10589-005-4798-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-005-4798-5

Keywords

Search

Navigation