# Heuristics for a variant of the traveling salesman problem

I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset.

Concretely, I have a graph with vertices $$V$$ and a family of subsets $$S = \{S_1, S_2, ..., S_n \}$$. I'm looking for a simple path $$\{(v_1, v_2), (v_2, v_3), ..., (v_{m}, v_{1})\}$$ such that for all $$S_i$$, there is a $$k$$ such that $$v_k \in S_i$$.

I'm interested in approximation algorithms, and heuristics for computing lower bounds for partial solutions for use in a branch and bound computation. Has this problem been studied elsewhere? If it helps, the problem is metric and the graph is complete.

• The closest thing I've found so far is this paper, but it's still quite a bit different from this problem. Oct 22 at 4:41