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.^[1] 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.^[2] 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,^[3] tight lower bounds to the Dubins TSP and generalized Dubins path problem could be computed by solving a Set TSP.^[4][5]

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. These moves do not affect the waste of the solution.

In the above figure, patterns (width no more than 198) are rows; knife changes are indicated by the small white circles; for example, patterns 2-3-4 have a roll of size 42.5 on the left - the corresponding knife does not have to move. Each pattern represents a TSP set, one of whose permutations must be visited. For instance, for the last pattern, which contains two repeated sizes (twice each), there are 5! / (2! × 2!) = 30 permutations. The number of possible solutions to the above instance is 12! × (5!)⁶ × (6!)⁴ × (7!)² / ((2!)⁹ × (3!)²) ≈ 5.3 × 10³⁵. The above solution contains 39 knife changes, and has been obtained by a heuristic; it is not known whether this is optimal. Transformations into the regular TSP, as described in ^[2] would involve a TSP with 5,520 nodes.

• Fagnano's problem of finding the shortest tour that visits all three sides of a triangle