×

Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem. (English) Zbl 1137.90686

Summary: 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 D. J. Bertsimas, L. Howell [Eur. J. Oper. Res. 65, No. 1, 68–95 (1993; Zbl 0776.90082)]. 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(n^{2})\) time, the same as for the homogeneous case, instead of \(O(n^{3})\) as first reported in the literature.

MSC:

90C35 Programming involving graphs or networks
90C15 Stochastic programming

Citations:

Zbl 0776.90082
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berman, O.; Simchi-Levi, D., Finding the optimal a priori tour and location of a traveling salesman with nonhomogeneous customers, Transportation Science, 22, 2, 148-154 (1988) · Zbl 0653.90082
[2] Bertsimas, D. J.; Chervi, P.; Peterson, M., Computational approaches to stochastic vehicle routing problems, Transportation Science, 29, 4, 342-352 (1995) · Zbl 0853.90037
[3] Bertsimas, D. J.; Howell, L., Further results on the probabilistic traveling salesman problem, European Journal of Operational Research, 65, 1, 68-95 (1993) · Zbl 0776.90082
[4] Bianchi, L.; Gambardella, L. M.; Dorigo, M., Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic, (Proceedings of ANTS 2002. Proceedings of ANTS 2002, Lecture Notes in Computer Science, vol. 2463 (2002), Springer-Verlag: Springer-Verlag Berlin, Germany), 176-187
[5] Bianchi, L.; Knowles, J.; Bowler, N., Local search for the probabilistic traveling salesman problem: Correction to the 2-p-opt and 1-shift algorithms, European Journal of Operational Research, 162, 1, 206-219 (2005) · Zbl 1132.90364
[6] Branke, J.; Guntsch, M., Solving the probabilistic TSP with ant colony optimization, Journal of Mathematical Modelling and Algorithms, 3, 4, 403-425 (2004) · Zbl 1079.90169
[7] P. Chervi, A computational approach to probabilistic vehicle routing problems, Master’s thesis, MIT, Cambridge, MA, 1988.; P. Chervi, A computational approach to probabilistic vehicle routing problems, Master’s thesis, MIT, Cambridge, MA, 1988.
[8] Gutjahr, W. J., S-ACO: An ant-based approach to combinatorial optimization under uncertainty, (Proceedings of ANTS 2004—Ant Colony Optimization and Swarm Intelligence. Proceedings of ANTS 2004—Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, vol. 3172 (2004), Springer-Verlag: Springer-Verlag Heidelberg, Germany), 238-249
[9] P. Jaillet, Probabilistic traveling salesman problems, Ph.D. thesis, MIT, Cambridge, MA, 1985.; P. Jaillet, Probabilistic traveling salesman problems, Ph.D. thesis, MIT, Cambridge, MA, 1985.
[10] Jaillet, P., A priori solution of a travelling salesman problem in which a random subset of the customers are visited, Operations Research, 36, 6, 929-936 (1988) · Zbl 0665.90096
[11] Laporte, G.; Louveaux, F.; Mercure, H., An exact solution for the a priori optimization of the probabilistic traveling salesman problem, Operations Research, 42, 3, 543-549 (1994) · Zbl 0810.90124
[12] Lin, S., Computer solution of the traveling salesman problem, Bell System Technical Journal, 44, 2245-2269 (1965) · Zbl 0136.14705
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.