New classes of efficiently solvable generalized Traveling Salesman Problems

被引:43
作者
Balas, E [1 ]
机构
[1] Carnegie Mellon Univ, GSIA, Pittsburgh, PA 15213 USA
关键词
Positive Integer; Time Window; Short Path; Local Optimum; Linear Time;
D O I
10.1023/A:1018939709890
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We consider the n-city traveling salesman problem (TSP), symmetric or asymmetric, with the following attributes. In one case, a positive integer k and an ordering (1,..., n) of the cities is given, and an optimal tour is sought subject to the condition that for any pair i, j is an element of (1..., n), if j greater than or equal to i + k, then i precedes j in the tour. In another case, position i in the tour has to be assigned to some city within k positions from i in the above ordering. This case is closely related to the TSP with time windows. In a third case, an optimal tour visiting m out of n cities is sought subject to constraints of the above two types. This is a special case of the Prize Collecting TSP (PCTSP). In any of the three cases, k may be replaced by city-specific integers k(i), i = 1,..., n. These problems arise in practice. For each class, we reduce the problem to that of finding a shortest source-sink path in a layered network with a number of arcs linear in n and exponential in the parameter k (which is independent of the problem size). Besides providing linear time algorithms for the solution of these problems, the reduction to a shortest path problem also provides a compact linear programming formulation. Finally, for TSPs or PCTSPs that do not have the required attributes, these algorithms can be used as heuristics that find in linear time a local optimum over an exponential-size neighborhood.
引用
收藏
页码:529 / 558
页数:30
相关论文
共 34 条
[1]  
ASCHEUER N, 1990, INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, P19
[2]   THE PRECEDENCE-CONSTRAINED ASYMMETRIC TRAVELING SALESMAN POLYTOPE [J].
BALAS, E ;
FISCHETTI, M ;
PULLEYBLANK, WR .
MATHEMATICAL PROGRAMMING, 1995, 68 (03) :241-265
[3]   THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM .2. POLYHEDRAL RESULTS [J].
BALAS, E .
NETWORKS, 1995, 25 (04) :199-216
[4]   THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM [J].
BALAS, E .
NETWORKS, 1989, 19 (06) :621-636
[5]  
BALAS E, 1991, WORKSH COMB OPT SCI
[6]  
BALAS E, 1986, ORSA TIMS M LOS ANG
[7]  
BALAS E, 1997, 625 MSRR GSIA CARN M
[9]  
BURDYUK VY, 1976, ENG CYBERN, V14, P12
[10]  
Burkard R. E., 1991, Optimization, V22, P787, DOI 10.1080/02331939108843720