Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study

被引:70
作者
Balas, E [1 ]
Simonetti, N
机构
[1] Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA
[2] Bryn Athyn Coll New Church, Bryn Athyn, PA 19009 USA
关键词
dynamic programming; algorithms; complexity; heuristics; vehicle routing; traveling salesman problem;
D O I
10.1287/ijoc.13.1.56.9748
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Consider the following restricted (symmetric or asymmetric) traveling-salesman problem (TSP): given an initial ordering of the n cities and an integer k > 0, find a minimum-cost feasible tour, where a feasible tour is one in which city i precedes city j whenever j greater than or equal to i + k in the initial ordering. Balas (1996) has proposed a dynamic-programming algorithm that solves this problem in time linear in Ir, though exponential in k. Some important real-world problems are amenable to this model or some of its close relatives. The algorithm of Balas (1996) constructs a layered network with a layer of nodes for each position in the tour, such that source-sink paths in this network are in one-to-one correspondence with tours that satisfy the postulated precedence constraints. In this payer we discuss an implementation of the dynamic-programming algorithm for the general case when the integer k is replaced with city-specific integers k(j), j = 1,..., n. We discuss applications to, and computational experience with, TSPs with time windows, a model frequently used in vehicle routing as well as in scheduling with setup, release and delivery times. We also introduce a new model, the TSP with target times, applicable to Justin-Time scheduling problems. Finally for TSPs that have no precedence restrictions, we use the algorithm as a heuristic that finds in linear time a local optimum over an exponential-size neighborhood. For this case, we implement an iterated version of our procedure, based on contracting some arcs of the tour produced by a first application of the algorithm, then reapplying the algorithm to the shrunken graph with the same k.
引用
收藏
页码:56 / 75
页数:20
相关论文
共 23 条
[1]  
[Anonymous], 1995, NETWORK MODELS
[2]  
APPLEGATE D, 1997, INT S MATH PROGR LAU
[3]  
ASCHEUER N, 1997, SOLVING ATSP TIME WI
[4]   AN EXACT ALGORITHM FOR THE TIME-CONSTRAINED TRAVELING SALESMAN PROBLEM [J].
BAKER, EK .
OPERATIONS RESEARCH, 1983, 31 (05) :938-945
[5]   THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM [J].
BALAS, E .
NETWORKS, 1989, 19 (06) :621-636
[6]   New classes of efficiently solvable generalized Traveling Salesman Problems [J].
Balas, E .
ANNALS OF OPERATIONS RESEARCH, 1999, 86 (0) :529-558
[7]  
BURKARD RE, 1997, 52 SFB TU
[8]   AN OPTIMAL ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS [J].
DUMAS, Y ;
DESROSIERS, J ;
GELINAS, E ;
SOLOMON, MM .
OPERATIONS RESEARCH, 1995, 43 (02) :367-371
[9]  
GENDREAU M, 1995, CRT9507 U MONTR
[10]  
GILMORE PC, 1985, TRAVELING SALESMAN P, P87