Logística/Sistemas de distribuição/Escala de veículos/Heurística construtiva: 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:
▲:O [[w:Algoritmo|algoritmo]] desenvolvido por [http://pt.wikipedia.org/wiki/Heur%C3%ADstica_de_Clarke_e_Wright Clarke e Wright], provavelmente talvez seja o método [http://pt.wikipedia.org/wiki/Heur%C3%ADstica_%28computa%C3%A7%C3%A3o%29 heurístico] conhecido para a resolução de PEV. Foi exposto no trabalho [http://www.jstor.org/pss/167703 <i>"Scheduling of vehicles from a central depot to a number of delivery points"</i>] em 1964 e baseia-se na noção de poupança. [[Logística/Referências#refbPEVH|(Toth e Vigo, 2001, p.110)]]
▲:Tem aplicação refere [[Logística/Referências#refbPEVI|Dorronsoro]] (2007), a problemas onde o número de veículos é variável, funcionando igualmente em problemas directos ou indirectos. Quando duas rotas <math>\ (0,...,i,0)</math> e <math>\ (0,j,...,0)</math> puderem ser misturadas em uma rota apenas <math>\ (0,...,i,j,...,0)</math>, a distância poupada <math>\ s_{ij}=c_{i0}+c_{0j}</math> é gerada. O [[w:Algoritmo|algoritmo]] segue os passos seguintes (o primeiro passo é idêntico para a versão paralela e sequencial):
▲*Passo 1:'''Cálculo da poupança'''
▲**Calcular poupança <math>\ s_{ij}=c_{i0}+c_{0j}-c_{ij}</math> para <math>\ i,j=1,...,n</math> e <math>\ i \ne j</math>
▲**Criar <math>\ n</math> rotas de veículos <math>\ (0,i,0)</math> para <math>\ i=1,...,n</math>
▲**Ordenar as poupanças de forma decrescente
▲;'''Versão paralela''':
▲*Passo 2: '''Melhor margem possível'''
▲**Apartir do todo da liste de poupanças, executar:
▲***Dando uma poupança <math>\ s_{ij}</math>, determinar de existem duas rotas que possam ser misturadas.
▲****Uma começando em <math>\ (0,j)</math>.
▲****Outra terminando em <math>\ (i,0)</math>.
▲***Combinar ambas, eliminando <math>\ (0,j)</math> e <math>\ (i,0)</math> introduzindo <math>\ (i,j)</math>.
▲;'''Versão sequencial''':
▲*Passo 2:'''Extensão da rota'''
**Determinar a primeira poupança <math>\ s_{ki}</math> ou <math>\ s_{jl}</math> que possa ser utilizado para fundir o caminho actual com outro caminho terminando em <math>\ (k,0)</math> ou começando em <math>\ (0,l)</math>.
**Implementar a mistura e repetir a operação à rota actual.
**Se não for viável a mistura, considerar a rota seguinte e replicar operações
**Parar quando não for possível fundir mais rotas.
{{AutoCat}}
|