Route-First Cluster-Second Method

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 time. In the shortest path algorithm, the cost of traveling between nodes i and j is equal to , where 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.