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

被引:45
作者
Bianchi, L
Knowles, J
Bowler, N
机构
[1] SUPSI, IDSIA, CH-6928 Manno, Switzerland
[2] Free Univ Brussels, IRIDIA, B-1050 Brussels, Belgium
[3] Met Off, Exeter EX1 3PB, Devon, England
关键词
combinatorial optimization; probabilistic traveling salesman problem; heuristics; local search;
D O I
10.1016/j.ejor.2003.10.016
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
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. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码:206 / 219
页数:14
相关论文
共 14 条
[1]  
Bartholdi J. J. III, 1982, Operations Research Letters, V1, P121, DOI 10.1016/0167-6377(82)90012-8
[2]   FURTHER RESULTS ON THE PROBABILISTIC TRAVELING SALESMAN PROBLEM [J].
BERTSIMAS, D ;
HOWELL, LH .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 65 (01) :68-95
[3]   Computational approaches to stochastic vehicle routing problems [J].
Bertsimas, D ;
Chervi, P ;
Peterson, M .
TRANSPORTATION SCIENCE, 1995, 29 (04) :342-352
[4]  
Bertsimas D, 1988, THESIS MIT CAMBRIDGE
[5]   A PRIORI OPTIMIZATION [J].
BERTSIMAS, DJ ;
JAILLET, P ;
ODONI, AR .
OPERATIONS RESEARCH, 1990, 38 (06) :1019-1033
[6]  
Bianchi L., 2002, LECT NOTES COMPUTER, V2439, P883
[7]  
BIANCHI L, 2002, IDSIA2102
[8]  
Bianchi L., 2002, INT WORKSH ANT ALG, P176, DOI [10.1007/3-540-45724-0_15, DOI 10.1007/3-540-45724-0_15]
[9]   Characterization of the probabilistic traveling salesman problem [J].
Bowler, NE ;
Fink, TMA ;
Ball, RC .
PHYSICAL REVIEW E, 2003, 68 (03) :7
[10]  
Branke J, 2003, LECT NOTES COMPUT SC, V2611, P165