A hybrid scatter search for the probabilistic traveling salesman problem

A hybrid scatter search for the probabilistic traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20083446
Country: United Kingdom
Volume: 34
Issue: 10
Start Page Number: 2949
End Page Number: 2963
Publication Date: Oct 2007
Journal: Computers and Operations Research
Authors:
Keywords: heuristics
Abstract:

The probabilistic traveling salesman problem (PTSP) is an important theoretical and practical topic in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper focuses on developing the hybrid scatter search (HSS) by incorporating the nearest neighbor rule, threshold accepting and edge recombination crossover into a scatter search conceptual framework to solve the PTSP. A set of numerical experiments were conducted to test the validity of the HSS based on the test problems from Tang and Miller–Hooks' study. The numerical results showed that the HSS can effectively solve the PTSP in most of the tested cases in terms of objective function value. Moreover, the results also indicated that incorporating threshold accepting into the scatter search framework can further increase the computation efficiency while maintaining solution quality. These findings show the potential of the proposed HSS in solving the large-scale PTSP.

Reviews

Required fields are marked *. Your email address will not be published.