Article ID: | iaor20084740 |
Country: | Netherlands |
Volume: | 176 |
Issue: | 1 |
Start Page Number: | 131 |
End Page Number: | 144 |
Publication Date: | Jan 2007 |
Journal: | European Journal of Operational Research |
Authors: | Campbell Ann Melissa, Bianchi Leonora |
Keywords: | heuristics, programming: probabilistic |
The probabilistic traveling salesman problem is a well known problem that is quite challenging to solve. It involves finding the tour with the lowest expected cost for customers that will require a visit with a given probability. There are several proposed algorithms for the homogeneous version of the problem, where all customers have identical probability of being realized. From the literature, the most successful approaches involve local search procedures, with the most famous being the 2-p-opt and 1-shift procedures proposed by Bertsimas. Recently, however, evidence has emerged that indicates the equations offered for these procedures are not correct, and even when corrected, the translation to the heterogeneous version of the problem is not simple. In this paper we extend the analysis and correction to the heterogeneous case. We derive new expressions for computing the cost of 2-p-opt and 1-shift local search moves, and we show that the neighborhood of a solution may be explored in O(