Logística/Sistemas de distribuição/Escala de veículos/Rotas-primeiro-agrupamento-depois: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
m Não é mais preciso inserir a navegação manualmente, basta manter a Predefinição:Lista de capítulos/Logística atualizada. Ver detalhes. |
Sem resumo de edição |
||
Linha 1:
=Rotas-primeiro-agrupamento-depois= ▼
[[Imagem:Prim Algorithm 0.png|right|thumb|280px|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 [[w:Problema do caixeiro viajante|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.
▲=Rotas-primeiro-agrupamento-depois=
▲[[Imagem:Prim Algorithm 0.png|right|thumb|280px|O caminho mínimo entre ''D'' e ''E'' não é D-E, mas sim D-F-E, com uma distância de 14.]]
▲:Beasley o primeiro a abordar o tema, identificou que o problema da segunda fase é um [http://pt.wikipedia.org/wiki/Problema_do_caminho_m%C3%ADnimo problema de caminho mínimo] ''standard'' num gráfico acíclico, que pode ser resolvido em <math>O(n^2)</math> tempo usando por exemplo o [http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra algoritmo de ''Dijkstra''].
▲:No algoritmo do caminho minimo, o custo <math>d_{ij}</math> de andar entre o nó <math>i</math> e <math>j</math> é igual a <math>c_{0i}+c_{0j}+l_{ij}</math>, onde <math>l_{ij}</math> é o custo de viajar de <math>i</math> a <math>j</math> num percurso PCV.
▲:Se todos os clientes tiverem uma procura unitária o algoritmo é assintoticamente optimo referem ''Haimovich e Rinnooy Kan''. Todavia isso não acontece para procuras gerais, apenas em casos triviais (''Bertsimas e Simchi-Levi'').
{{AutoCat}}
| |||