Travelling Salesman on Subset of Points

Question

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?

Answer 1

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:

1. $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$
2. 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$