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
He7d3r.bot (discussão | contribs)
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[w://pt.wikipedia.org/wiki/Heur%C3%ADstica_de_Clarke_e_WrightEN:Heurística de Clarke e Wright| Clarke e Wright]], provavelmente talvez seja o método [http[w://pt.wikipedia.org/wiki/Heur%C3%ADstica_%28computa%C3%A7%C3%A3o%29Heurística (computação)|heurístico]] mais 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}-c_{ij}</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''':
: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)]]
*Passo 2: '''Melhor margem possível'''
**Apartir do todo da listelista 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''':
: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 2:'''Extensão da rota'''
 
 
*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}}