Logística/Sistemas de distribuição/Escala de veículos/Rotas-primeiro-agrupamento-depois

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).