Article ID: | iaor20091418 |
Country: | Germany |
Volume: | 2 |
Issue: | 3 |
Start Page Number: | 351 |
End Page Number: | 361 |
Publication Date: | May 2008 |
Journal: | Optimization Letters |
Authors: | Pardalos Panos M., Migdalas Athanasios, Marinakis Yannis |
Keywords: | heuristics: local search |
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.