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. 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, 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 within each pattern (moving reels left or right).

In the above figure, patterns (width no more than 198) are rows; knife changes are indicated by the small white circles; for example, the first four patterns involve a roll of size 36 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 first pattern, which contains one size repeated twice, there are 5! / 2! = 60 permutations. The number of possible solutions to the above instance is 13! × (5!)⁵ × (6!)⁵ × (7!)³ / ((2!)¹² × (3!)³) ≈ 4.3 × 10³⁹. The above solution contains 43 knife changes, and has been obtained by a heuristic, but it is not known whether this is optimal.