Route-first, cluster-second methods construct in a first phase a giant TSP tour, disregarding side constraints, and decompose this tour into feasible vehicle routes in a second phase. This idea applies to problems with a free number of vehicles. It was first put forward by Beasley who observed that the second phase problem is a standard shortest path problem on an acyclic graph and can thus be solved in ${O(n^{2})}$ time. In the shortest path algorithm, the cost ${d_{ij}}$ of traveling between nodes ${i}$ and ${j}$ is equal to ${c_{0i}+c_{0j}+l_{ij}}$, where ${l_{ij}}$ is the cost of traveling from ${i}$ to ${j}$ on the TSP tour.

We are not aware of any computational experience showing that route-first, cluster-second heuristics are competitive with other approaches.