Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem

Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics, programming: probabilistic
Abstract:

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(n2) time, the same as for the homogeneous case, instead of O(n3) as first reported in the literature.

Reviews

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