Rotas-primeiro-agrupamento-depois

O caminho mínimo entre D e E não é D-E, mas sim D-F-E, com uma distância de 14.

Este método constrói numa primeira fase um tour de problema de caixeiro viajante (PCV) gigante não considerando restrições laterais, e decompondo este tour' em rota possíveis numa segunda fase. Esta ideia aplica-se a problemas com veículos livres.

Beasley o primeiro a abordar o tema, identificou que o problema da segunda fase é um problema de caminho mínimo standard num gráfico acíclico, que pode ser resolvido em $\ O(n^{2})$ tempo usando por exemplo o algoritmo de Dijkstra.

No algoritmo do caminho mínimo, o custo $\ d_{ij}$ de andar entre o nó $\ i$ e $\ j$ é igual a $\ c_{0i}+c_{0j}+l_{ij}$ , onde $\ l_{ij}$ é o custo de viajar de $\ i$ a $\ j$ num percurso PCV.

Se todos os clientes tiverem uma procura unitária o algoritmo é assintoticamente óptimo referem Haimovich e Rinnooy Kan. Todavia isso não acontece para procuras gerais, apenas em casos triviais (Bertsimas e Simchi-Levi) (TOTH e VIGO, 2002e, p.120 e 121).