Set TSP problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

  1. ^ Charles Noon, James Bean (1993). "An efficient transformation of the generalized traveling salesman problem". 
  2. ^ Satyanarayana G. Manyam, Sivakumar Rathinam, Swaroop Darbha, David Casbeer, Yongcan Cao, Phil Chandler (2016). "GPS Denied UAV Routing with Communication Constraints". 
  3. ^ Satyanarayana G. Manyam, Sivakumar Rathinam (2016). "On Tightly Bounding the Dubins Traveling Salesman's Optimum". 
  4. ^ 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.