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

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa

Rotas-primeiro-agrupamento-depois[editar | editar código-fonte]

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