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.C.E. Noon, [https://hdl.handle.net/2027.42/161841 "The Generalized Traveling Salesman Problem"], PhD dissertation, 1988. 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.{{cite journal
| last1 = Noon | first1 = Charles E.
| last2 = Bean | first2 = James C.
| date = February 1993
| doi = 10.1080/03155986.1993.11732212
| hdl = 2027.42/6833
| issue = 1
| journal = INFOR: Information Systems and Operational Research
| pages = 39–44
| title = An efficient transformation of the generalized traveling salesman problem
| volume = 31| hdl-access = free
}} 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,{{cite journal|author=Satyanarayana G. Manyam, Sivakumar Rathinam, Swaroop Darbha, David Casbeer, Yongcan Cao, Phil Chandler|title=GPS Denied UAV Routing with Communication Constraints|journal=Journal of Intelligent & Robotic Systems|volume=84|pages=691–703|year=2016|issue=1–4 |doi=10.1007/s10846-016-0343-2|s2cid=33884807 }} tight lower bounds to the Dubins TSP and generalized Dubins path problem could be computed by solving a Set TSP.{{cite journal|author=Satyanarayana G. Manyam, Sivakumar Rathinam|title=On Tightly Bounding the Dubins Traveling Salesman's Optimum|journal=Journal of Dynamic Systems, Measurement, and Control|volume=140|issue=7|pages=071013|year=2016|arxiv=1506.08752|doi=10.1115/1.4039099|s2cid=16191780 }}{{cite journal|author=Satyanarayana G. Manyam, Sivakumar Rathinam, David Casbeer, Eloy Garcia|title=Tightly Bounding the Shortest Dubins Paths Through a Sequence of Points|year=2017|journal=Journal of Intelligent & Robotic Systems|volume=88|issue=2–4|pages=495–511|doi=10.1007/s10846-016-0459-4|s2cid=30943273 }}
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.
file:generalised TSP knife changes.png
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 × (6!)4 × (7!)2 / ((2!)9 × (3!)2) ≈ 5.3 × 1035. 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 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