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 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 direct transformation for an instance of the set TSP to an instance of the standard asymmetric TSP.^[1] The idea is to first create disjoint sets and then assign a directed cycle to each set. The salesman, when visiting a vertex in some set, then walks around the cycle for free. To not use the cycle would ultimately be very costly.

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

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. 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 ^[1] would involve a TSP with 5,520 nodes.

References