Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms.

*(English)*Zbl 1132.90364Summary: The probabilistic traveling salesman problem concerns the best way to visit a set of customers located in some metric space, where each customer requires a visit only with some known probability. A solution to this problem is an a priori tour which visits all customers, and the objective is to minimize the expected length of the a priori tour over all customer subsets, assuming that customers in any given subset must be visited in the same order as they appear in the a priori tour. This problem belongs to the class of stochastic vehicle routing problems, a class which has received increasing attention in recent years, and which is of major importance in real world applications.

Several heuristics have been proposed and tested for the probabilistic traveling salesman problem, many of which are a straightforward adaptation of heuristics for the classical traveling salesman problem. In particular, two local search algorithms (2-p-opt and 1-shift) were introduced by Bertsimas.

In a previous report we have shown that the expressions for the cost evaluation of 2-p-opt and 1-shift moves, as proposed by Bertsimas, are not correct. In this paper we derive the correct versions of these expressions, and we show that the local search algorithms based on these expressions perform significantly better than those exploiting the incorrect expressions.

Several heuristics have been proposed and tested for the probabilistic traveling salesman problem, many of which are a straightforward adaptation of heuristics for the classical traveling salesman problem. In particular, two local search algorithms (2-p-opt and 1-shift) were introduced by Bertsimas.

In a previous report we have shown that the expressions for the cost evaluation of 2-p-opt and 1-shift moves, as proposed by Bertsimas, are not correct. In this paper we derive the correct versions of these expressions, and we show that the local search algorithms based on these expressions perform significantly better than those exploiting the incorrect expressions.

##### MSC:

90C27 | Combinatorial optimization |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

Combinatorial optimization; probabilistic traveling salesman problem; heuristics; local search
PDF
BibTeX
XML
Cite

\textit{L. Bianchi} et al., Eur. J. Oper. Res. 162, No. 1, 206--219 (2005; Zbl 1132.90364)

Full Text:
DOI

##### References:

[1] | Bartholdi, J.J.; Platzman, L.K., An O(nlogn) planar travelling salesman heuristic based on spacefilling curves, Operations research letters, 1, 4, 121-125, (1982) · Zbl 0488.90072 |

[2] | D.J. Bertsimas, Probabilistic combinatorial optimization problems, PhD thesis, MIT, Cambridge, MA, 1988 |

[3] | Bertsimas, D.J.; Chervi, P.; Peterson, M., Computational approaches to stochastic vehicle routing problems, Transportation science, 29, 4, 342-352, (1995) · Zbl 0853.90037 |

[4] | 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 |

[5] | Bertsimas, D.J.; Jaillet, P.; Odoni, A., A priori optimization, Operations research, 38, 6, 1019-1033, (1990) · Zbl 0721.90062 |

[6] | Bianchi, L.; Gambardella, L.M.; Dorigo, M., An ant colony optimization approach to the probabilistic traveling salesman problem, (), 883-892 |

[7] | Bianchi, L.; Gambardella, L.M.; Dorigo, M., Solving the homogeneous probabilistic traveling salesman problem by the ACO metaheuristic, (), 176-187 |

[8] | L. Bianchi, J. Knowles, Local search for the probabilistic traveling salesman problem: A proof of the incorrectness of Bertsimas’ proposed 2-p-opt and 1-shift algorithms. Technical Report IDSIA-21-02, IDSIA, Lugano, Switzerland, 2002 |

[9] | Bowler, N.E.; Fink, T.M.A.; Ball, R.C., Characterization of the probabilistic traveling salesman problem, Physical review E, 68, 3, 036703, (2003) |

[10] | Branke, J.; Guntsch, M., New ideas for applying ant colony optimization to the probabilistic TSP, (), 165-175 · Zbl 1033.90516 |

[11] | () |

[12] | P. Jaillet, Probabilistic traveling salesman problems, PhD thesis, MIT, Cambridge, MA, 1985 |

[13] | 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 |

[14] | Rossi, F.A.; Gavioli, I., Aspects of heuristic methods in the probabilistic traveling salesman problem, (), 214-227 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.