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 verificada]
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição
Sem resumo de edição
 
Linha 1:
O [[w:Algoritmo|algoritmo]] da poupança segundo [[Logística/Referências#refbPEVI|Dorronsoro]] (20072007d) foi desenvolvido por [[w:EN:Heurística de Clarke e Wright| Clarke e Wright]] em 1964, aplica-se a problemas onde o número de [[w:Veículo|veículos]] não é fixo (trata-se de uma [[w:Variável (matemática)|variável]] de decisão). 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 [[w:Distância|distância]] poupada <math>\ s_{ij}=c_{i0}+c_{0j}-c_{ij}</math> é gerada. O [[w:Algoritmo|algoritmo]] segue os seguintes 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>
Linha 7:
 
Versão paralela:
*Passo 2:. Melhor margem possível.
Apartir do todo da lista de poupanças, executar:
*Dando uma poupança <math>\ s_{ij}</math>, determinar de existem duas rotas que possam ser misturadas.
Linha 14:
*Combinar ambas, eliminando <math>\ (0,j)</math> e <math>\ (i,0)</math> introduzindo <math>\ (i,j)</math>.
 
Versão [[w:Sequência (matemática)|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.