New classes of efficiently solvable generalized Traveling Salesman Problems

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) ofthe cities is given, and an optimal tour is sought subject to the condition that for any pairi, j ∈ (1..., n), if j ≥ i + k, then i precedes j in the tour. In another case, position i in the tourhas to be assigned to some city within k positions from i in the above ordering. This case isclosely related to the TSP with time windows. In a third case, an optimal tour visiting m outof n cities is sought subject to constraints of the above two types. This is a special case ofthe Prize Collecting TSP (PCTSP). In any of the three cases, k may be replaced by city‐specificintegers k(i), i=1,..., n. These problems arise in practice. For each class, we reducethe problem to that of finding a shortest source‐sink path in a layered network with a numberof arcs linear in n and exponential in the parameter k (which is independent of the problemsize). Besides providing linear time algorithms for the solution of these problems, the reductionto 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 canbe used as heuristics that find in linear time a local optimum over an exponential‐sizeneighborhood. Copyright Kluwer Academic Publishers 1999