Set TSP problem: Difference between revisions
mNo edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
There is a direct transformation for an instance of the set TSP to an instance of the standard asymmetric TSP.<ref>{{cite journal|author=Charles Noon, James Bean|title=An efficient transformation of the generalized traveling salesman problem|year=1993|url=https://www.researchgate.net/publication/265366022_An_efficient_transformation_of_the_generalized_traveling_salesman_problem}}</ref> 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. |
There is a direct transformation for an instance of the set TSP to an instance of the standard asymmetric TSP.<ref>{{cite journal|author=Charles Noon, James Bean|title=An efficient transformation of the generalized traveling salesman problem|year=1993|url=https://www.researchgate.net/publication/265366022_An_efficient_transformation_of_the_generalized_traveling_salesman_problem}}</ref> 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<ref>{{cite journal|author=Satyanarayana G. Manyam, Sivakumar Rathinam, Swaroop Darbha, David Casbeer, Yongcan Cao, Phil Chandler|title=GPS Denied UAV Routing with Communication Constraints|year=2016|url=https://link.springer.com/article/10.1007/s10846-016-0343-2}}</ref>, tight lower bounds to the Dubins TSP and generalized Dubins path problem could be computed by solving a Set TSP<ref>{{cite journal|author=Satyanarayana G. Manyam, Sivakumar Rathinam|title=On Tightly Bounding the Dubins Traveling Salesman's Optimum|year=2016|url=https://arxiv.org/abs/1506.08752}}</ref>, <ref>{{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|url=https://link.springer.com/article/10.1007/s10846-016-0459-4}}</ref>. |
|||
==References== |
==References== |
||
{{reflist}} |
{{reflist}} |
||
[[Category: |
[[Category:Traveling salesman problem]] |
||
[[Category:NP-complete problems]] |
[[Category:NP-complete problems]] |
||
[[Category:Operations research]] |
[[Category:Operations research]] |
||
Revision as of 15:58, 6 March 2017
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].
References
- ^ Charles Noon, James Bean (1993). "An efficient transformation of the generalized traveling salesman problem".
{{cite journal}}: Cite journal requires|journal=(help) - ^ Satyanarayana G. Manyam, Sivakumar Rathinam, Swaroop Darbha, David Casbeer, Yongcan Cao, Phil Chandler (2016). "GPS Denied UAV Routing with Communication Constraints".
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link) - ^ Satyanarayana G. Manyam, Sivakumar Rathinam (2016). "On Tightly Bounding the Dubins Traveling Salesman's Optimum".
{{cite journal}}: Cite journal requires|journal=(help) - ^ Satyanarayana G. Manyam, Sivakumar Rathinam, David Casbeer, Eloy Garcia (2017). "Tightly Bounding the Shortest Dubins Paths Through a Sequence of Points".
{{cite journal}}: Cite journal requires|journal=(help)CS1 maint: multiple names: authors list (link)