Set TSP problem

In combinatorial optimization, the set TSP, also known as the generalized TSP, group TSP, One-of-a-Set TSP, Multiple Choice TSP or Covering Salesman Problem, is a generalization of the traveling salesman problem (TSP), whereby it is required to find a shortest tour in a graph which visits all specified subsets of the vertices of a graph. The subsets of vertices must be disjoint, since the case of overlapping subsets can be reduced to the case of disjoint ones. The ordinary TSP is a special case of the set TSP when all subsets to be visited are singletons. Therefore, the set TSP is also NP-hard.

There is a transformation for an instance of the set TSP to an instance of the standard asymmetric TSP. The idea is to connect each subset into a directed cycle with edges of zero weight, and inherit the outgoing edges from the original graph shifting by one vertex backwards along this cycle. The salesman, when visiting a vertex v in some subset, walks around the cycle for free and exits it from the vertex preceding v by an outgoing edge corresponding to an outgoing edge of v in the original graph.

The Set TSP has a lot of interesting applications in several path planning problems. For example, a two vehicle cooperative routing problem could be transformed into a set TSP, tight lower bounds to the Dubins TSP and generalized Dubins path problem could be computed by solving a Set TSP.

Illustration from the cutting stock problem

The one-dimensional cutting stock problem as applied in the paper / plastic film industries, involves cutting jumbo rolls into smaller ones. This is done by generating cutting patterns typically to minimise waste. Once such a solution has been produced, one may seek to minimise the knife changes, by re-sequencing the patterns (up and down in the figure), or moving rolls left or right within each pattern.