Travelling Salesman on Subset of Points I'd like to solve the travelling salesman problem, except that the salesman only needs to travel to a subset of the locations.
Each location has exactly one client, and each client has a "type". For example, the type of a client might be {male, aged 18-25, unemployed}.
If the sales man has visited a particular client type, then the salesman does not need to visit any more of that type (and therefore can miss out other locations that have this client type).
What are the "recommended" methods/heuristics for solving this problem?
 A: So if I understood correctly:


*

*you have a graph with set of vertices V representing the locations

*

*The vertices are labelled with the 'types' of clients


*There is a set of undirected, weighted edges (u,v) in E where (u,v) exists in E

*

*exists if it is possible to travel from location u to location v

*is weighted with the cost or distance of getting from u to v.



You want to find a set of edges connecting a subset of the vertices such that each unique label is included at least once in the subset of vertices.
My suggestion is to recast the problem as follows:


*

*Make the edges directed and add reverse edges for all the location-location edges

*Add vertices to the graph for each unique label

*Add a zero-weighted edge from each location to the labels associated with it


Since the edges are directed, there is no path that passes trough the 'label' vertices.
Now, if I'm right, your problem is (or is very similar to) a minimum-spanning tree problem because you want to find the set of edges that connects all of the label nodes at minimum cost.
A: You can reduce the problem to the classical TSP. Let $G = (V, E, W)$ be the original graph and consider a subset $U\subseteq V$. Let $G_U = (U, E_U, W_U)$ the restriction of $G$ to $U$ such that:

*

*$E_U$ is the collection of all edges $(u,v)\in U\times U$ in which there is a path in $G$ from $u$ to $v$

*For every $(u, v)\in E_U$, the weight/cost of the edge corresponds to the shortest path in $G$ from $u$ to $v$
Solve the classical TSP in $G_U$. From the optimal path you can retrieve to solution to the original problem in $G$
