Is there a special name for this 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) [Wik1], 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». [Wik2] It is also known as the "travelling politician problem", which deals with "states" that have (one or more) "cities" and the salesman has to visit exactly one "city" from each "state". [Wik1]
Does an algorithm exist that solves this problem? If not, is there a way to reformulate this problem into a known one?
«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», [Wik2] so it should admit (known) algorithms of polynoimal computation complexity only in special cases. On the other hand, «Noon and Bean demonstrated that the generalized travelling salesman problem can be transformed into a standard travelling salesman problem with the same number of cities, but a modified distance matrix» [Wik1] . «There is a direct transformation for an instance of the set TSP to an instance of the standard asymmetric TSP. [BN] 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. [Wik2] The obtained TSP can be solved with professional software such as Concorde.
The author thanks to Alexander Wolff from Würzburg University (Germany) for his kind help.
[BN] James Bean, Charles Noon. An efficient transformation of the generalized traveling salesman problem (1993).
[Wik1] Wikipedia, Travelling salesman problem.
[Wik2] Wikipedia, Set TSP problem.