New classes of efficiently solvable generalized Traveling Salesman Problems

We consider the n-city traveling salesman problem (TSP), symmetric or asymm etric, 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 soug ht 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 i s a special case of the Prize Collecting TSP (PCTSP). In any of the three c ases, 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 o f arcs linear in n and exponential in the parameter k (which is independent of the problem size). Besides providing linear time algorithms for the sol ution of these problems, the reduction to a shortest path problem also prov ides a compact linear programming formulation. Finally, for TSPs or PCTSPs that do not have the required attributes, these algorithms can be used as h euristics that find in linear time a local optimum over an exponential-size neighborhood.