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]

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

See also

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

References

1. C.E. Noon, "The Generalized Traveling Salesman Problem", PhD dissertation, 1988.
2. Noon, Charles E.; Bean, James C. (February 1993). "An efficient transformation of the generalized traveling salesman problem". INFOR: Information Systems and Operational Research. 31 (1): 39–44. doi:10.1080/03155986.1993.11732212. hdl:2027.42/6833.
3. Satyanarayana G. Manyam, Sivakumar Rathinam, Swaroop Darbha, David Casbeer, Yongcan Cao, Phil Chandler (2016). "GPS Denied UAV Routing with Communication Constraints". Journal of Intelligent & Robotic Systems. 84 (1–4): 691–703. doi:10.1007/s10846-016-0343-2. S2CID 33884807.{{cite journal}}: CS1 maint: multiple names: authors list (link)
4. Satyanarayana G. Manyam, Sivakumar Rathinam (2016). "On Tightly Bounding the Dubins Traveling Salesman's Optimum". Journal of Dynamic Systems, Measurement, and Control. 140 (7): 071013. arXiv:1506.08752. doi:10.1115/1.4039099. S2CID 16191780.
5. Satyanarayana G. Manyam, Sivakumar Rathinam, David Casbeer, Eloy Garcia (2017). "Tightly Bounding the Shortest Dubins Paths Through a Sequence of Points". Journal of Intelligent & Robotic Systems. 88 (2–4): 495–511. doi:10.1007/s10846-016-0459-4. S2CID 30943273.{{cite journal}}: CS1 maint: multiple names: authors list (link)