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

Rotas-primeiro-agrupamento-depoisEditar

 
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   tempo usando por exemplo o algoritmo de Dijkstra.

No algoritmo do caminho mínimo, o custo   de andar entre o nó   e   é igual a  , onde   é o custo de viajar de   a   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).