Skip to main content
SpringerLink
Log in

Expanding neighborhood search–GRASP for the probabilistic traveling salesman problem

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

The Probabilistic Traveling Salesman Problem is a variation of the classic traveling salesman problem and one of the most significant stochastic routing problems. In probabilistic traveling salesman problem only a subset of potential customers need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable. In this paper, a variant of the well-known Greedy Randomized Adaptive Search Procedure (GRASP), the Expanding Neighborhood Search–GRASP, is proposed for the solution of the probabilistic traveling salesman problem. expanding neighborhood search–GRASP has been proved to be a very efficient algorithm for the solution of the traveling salesman problem. The proposed algorithm is tested on a numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in six out of ten cases the proposed algorithm gives a new best solution.

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

Access this article

Log in via an institution

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. Bertsimas, D. J.: Probabilistic Combinatorial Optimization Problems. Ph.D. thesis, MIT, Cambridge (1988)

  2. Bertsimas D., Howell L. (1993). Further results on the probabilistic traveling salesman problem. Eur. J. Oper. Res. 65(1): 68–95

    Article  MATH  Google Scholar 

  3. Bertsimas D., Chervi P., Peterson M. (1995). Computational approaches to stochastic vehicle routingproblems. Transp. Sci. 29(4): 342–352

    MATH  Google Scholar 

  4. Bianchi, L.: Ant Colony Optimization and Local Search for the Probabilistic Traveling Salesman Problem: A Case Study in Stochastic Combinatorial Optimization. Ph.D. Thesis, Universite Libre de Bruxelles, Belgium (2006)

  5. Bianchi L., Knowles J., Bowler N. (2005). Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms. Eur. J. Oper. Res. 162(1): 206–219

    Article  MATH  MathSciNet  Google Scholar 

  6. Bianchi, L., Gambardella, L.M., Dorigo, M.: An ant colony optimization approach to the probabilistic traveling salesman problem. In: Merelo Guervòs, J.J., Adamidis, P., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) Proceedings of the Seventh Parallel Problem Solving from Nature (PPSN VII), Lecture Notes in Computer Science, vol. 2439, pp. 883–892. Springer, Berlin (2002)

  7. Bianchi, L., Gambardella, L.M., Dorigo, M.: Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic. In: Dorigo, M., DiCaro, G., Sampels, M. (eds.) Proceedings of Third International Workshop ANTS 2002, Lecture Notes in Computer Science, vol. 2463, pp. 176–187. Springer, Berlin (2002)

  8. Bowler, N.E., Fink, T.M.A., Ball, R.C.: Characterization of the probabilistic traveling salesmanproblem. Phys. Rev. E 68 (2003)

  9. Branke J., Guntsch M. (2004). Solving the probabilistic TSP with ant colony optimization. J. Math. Model. Algorithms 3(4): 403–425

    Article  MATH  MathSciNet  Google Scholar 

  10. Campbell A.M. (2006). Aggregation for the probabilistic travelling salesman problem. Comput. Oper. Res. 33: 2703–2724

    Article  MATH  MathSciNet  Google Scholar 

  11. Choi J., Lee J.H., Realff M.J. (2004). An algorithmic framework for improving heuristic solutions: Part II. A new version of the stochastic traveling salesman problem. Comput. Chem. Eng. 28(8): 1297–1307

    Google Scholar 

  12. Feo T.A., Resende M.G.C. (1995). Greedy randomized adaptive search procedure. J. Glob. Optim. 6: 109–133

    Article  MATH  MathSciNet  Google Scholar 

  13. Garfinkel R., Nemhauser G. (1972). Integer Programming. Wiley, New York

    MATH  Google Scholar 

  14. Glover F. (1989). Tabu search I. ORSA J. Comput. 1(3): 190–206

    MATH  Google Scholar 

  15. Glover F. (1990). Tabu search II. ORSA J. Comput. 2(1): 4–32

    MATH  Google Scholar 

  16. Hansen P., Mladenovic N. (2001). Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130: 449–467

    Article  MATH  MathSciNet  Google Scholar 

  17. Jaillet, P.: Probabilistic traveling salesman problems. PhD Thesis, MIT, Cambridge (1985)

  18. Jaillet P., Odoni A.R. (1988). The probabilistic vehicle routing problem. In: Golden, B.L., Assad, A.A. (eds) Vehicle Routing: Methods and Studies, pp 293–318. Elsevier, North Holland, Amsterdam

    Google Scholar 

  19. Jaillet P. (1988). A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res. 36(6): 929–936

    MATH  MathSciNet  Google Scholar 

  20. Laporte G., Louveaux E., Mercure H. (1994). A priori optimization of the probabilistic traveling salesman problem. Oper. Res. 42: 543–549

    Article  MATH  MathSciNet  Google Scholar 

  21. Lin S. (1965). Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44: 2245–2269

    MATH  Google Scholar 

  22. Liu, Y.H.: A hybrid scatter search for the probabilistic traveling salesman problem. Comput. Oper. Res (available on line) (2007)

  23. Liu, Y.-H., Jou, R.-C., Wang, C.-J.: Genetic algorithms for the probabilistic traveling salesman problem. In: Proceedings of the conference on E-logistics. Taoyuan, Taiwan, pp. 77–82 (2004)

  24. Marinakis, Y.: Vehicle routing in distribution problems. Ph.D. Thesis, Technical University of Crete, Department of Production Engineering and Management, Chania, Greece (2005)

  25. Marinakis Y., Migdalas A., Pardalos P.M. (2005). Expanding neighborhood GRASP for the traveling salesman problem. Comput. Optim. Appl. 32: 231–257

    Article  MATH  MathSciNet  Google Scholar 

  26. Powell W.B., Jaillet P., Odoni A. (1995). Stochastic and dynamic networks and routing. In: Ball, M.O., Magnanti, T.L., Momma, C.L., and Nemhauser, G.L. (eds) Network Routing, Handbooks in Operations Research and Management Science, vol. 8, pp 141–295. Elsevier, Amsterdam

    Google Scholar 

  27. Psaraftis H.N. (1988). Dynamic vehicle routing problems. In: Golden, B.L., Assad, A.A. (eds) Vehicle Routing: Methods and Studies, pp 223–248. Elsevier, North Holland, Amsterdam

    Google Scholar 

  28. Resende M.G.C., Ribeiro C.C. (2003). Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G.A. (eds) Handbook of Metaheuristics, pp 219–249. Kluwer, Boston

    Chapter  Google Scholar 

  29. Rossi F.A., Gavioli I. (1987). Aspects of heuristics methods in the probabilistic traveling salesman problem. In: Andreatta, G., Mason, F., Serafini, P. (eds) Advanced School on Stochastics in Combinatorial Optimization, pp 214–227. World Scientific Press, Singapore

    Google Scholar 

  30. Tang H., Miller-Hooks E. (2004). Approximate procedures for the probabilistic traveling salesperson problem. Transp. Res. Rec. 1882: 27–36

    Article  Google Scholar 

  31. Tarjan R. (1983). Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia

    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, Center of Applied Optimization, University of Florida, Gainesville, 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 search–GRASP for the probabilistic traveling salesman problem. Optimization Letters 2, 351–361 (2008). https://doi.org/10.1007/s11590-007-0064-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-007-0064-3

Keywords

Search

Navigation