New classes of efficiently solvable generalized traveling salesman problems

New classes of efficiently solvable generalized traveling salesman problems

0.00 Avg rating0 Votes
Article ID: iaor2000532
Country: Netherlands
Volume: 86
Issue: 1
Start Page Number: 529
End Page Number: 558
Publication Date: Mar 1999
Journal: Annals of Operations Research
Authors:
Abstract:

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 ∈ (1,…,n), if j ≥ 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), = 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.

Reviews

Required fields are marked *. Your email address will not be published.