Wikilivros

Logística/Sistemas de distribuição/Escala de veículos/Agrupar-primeiro-e-rotas-depois: diferenças entre revisões

Explorar interativamente o histórico
[edição não verificada][edição não verificada]
← Edição anteriorEdição posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
He7d3r.bot (discussão | contribs)
Robôs
19 639 edições
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:
=Agrupar-primeiro-rotas-depois=▼
Segundo [[Logística/Referências#refbPEVH|(TOTH e VIGO, (2001, p.116 - 117)]] esta classe abarca três famílias de métodos abaixo descritos:▼
 
==Agrupamento elementar==▼
 
===[[w:Algoritmo|Algoritmo]] de varrimento===▼
:Este [[w:Algoritmo|algoritmo]] é aplicado a casos "planos" de PEV. É compostoComposto por duas partes:▼
 
*Divisão: [http[w://pt.wikipedia.org/wiki/Cluster |<i>clusters</i>]] exequíveis são inicialmente formados rodando um raio centrado no depósito.▼
*[[w:Problema do caixeiro viajante|Problema do caixeiro viajante]] (PCV): É obtida então para cada <i>cluster</i> uma rota, ao resolver PCV.
 
:Em alguns casos tem-se um fase de pós-[http[w://pt.wikipedia.org/wiki/Otimiza%C3%A7%C3%A3oOtimização| optimização]], onde vértices são trocados entre [http://pt.wikipedia.org/wiki/Cluster <i>clusters</i>] adjacentes e rotas são reoptimizadasoptimizadas novamente.▼
▲=Agrupar-primeiro-rotas-depois=
:Esta classe abarca três famílias de métodos abaixo descritos:
 
▲==Agrupamento elementar==
 
▲===[[w:Algoritmo|Algoritmo]] de varrimento===
▲:Este [[w:Algoritmo|algoritmo]] é aplicado a casos "planos" de PEV. É composto por duas partes:
▲*Divisão: [http://pt.wikipedia.org/wiki/Cluster <i>clusters</i>] exequíveis são inicialmente formados rodando um raio centrado no depósito.
*[http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante PCV]: É obtida então para cada [http://pt.wikipedia.org/wiki/Cluster <i>clusters</i>] uma rota, ao resolver [http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante PCV].
▲:Em alguns casos tem-se um fase de pós-[http://pt.wikipedia.org/wiki/Otimiza%C3%A7%C3%A3o optimização], onde vértices são trocados entre [http://pt.wikipedia.org/wiki/Cluster <i>clusters</i>] adjacentes e rotas são reoptimizadas.
 
*Assumindo cada vértice <math>\ i</math> é representado pelas suas coordenadas polares (θ<math>\ _{i}</math>,ρ<math>_{i}</math>) onde θ<math>\ _{i}</math> é o angulo e ρ<math>\ _{i}</math> é o comprimento do raio. Atribuindo o valor θ<math>\ _{i}^*=0</math> a um vértice arbitrário <math>\ i^*</math> e calculando os ângulos que sobram de <math>\ (0,i^*)</math>. Classificar os vértices por ordem crescente de (θ<math>\ _{i}</math>).
**Passo 1: (iniciação da rota).
:Escolher um veículo <math>\ k</math> não utilizado.
**Passo 2: (construção da rota).
:Começando no vértice sem rota que tenha o anguloângulo menor, afectar vértices ao veículo <math>\ k</math> até à sua capacidade máxima ou ao limite da duração máxima da rota não serem excedidos.
:Se permanecerem vértices sem rota voltar ao passo 1.
**Passo 3:([http://pt.wikipedia.org/wiki/Otimiza%C3%A7%C3%A3o optimização] da rota). Optimizar cada rota separadamente, resolvendo o correspondente [http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante PCV] (exacto ou aproximado).
 
===[[w:Algoritmo|Algoritmo]] de <i>Fisher e Jaikumar</i>===▼
▲[[Logística/Referências#refbPEVH|(TOTH e VIGO, 2001, p.117)]]
:O algoritmo de <i>Fisher e Jaikumar< segundo ([[Logística/i>Referências#refbPEVJ|Dorronsoro, 2007a]]) apresentado no livro <i>"A Generalized Assignment Heuristic for Vehicle Routing"</i> em 1981, resolve problemas de atribuição generalizada (PAG) ([http[w://en.wikipedia.org/wiki/Generalized_assignment_problemEN:Generalized assignment problem|<i>generalized assignment problem (GAP)</i>]] em Inglês), formando [http://pt.wikipedia.org/wiki/Cluster <i>clusters</i>].▼
 
:Assim:▼
▲===[[w:Algoritmo|Algoritmo]] de <i>Fisher e Jaikumar</i>===
▲:O algoritmo de <i>Fisher e Jaikumar</i> apresentado no livro <i>"A Generalized Assignment Heuristic for Vehicle Routing"</i> em 1981, resolve problemas de atribuição generalizada (PAG) ([http://en.wikipedia.org/wiki/Generalized_assignment_problem <i>generalized assignment problem (GAP)</i>] em Inglês), formando [http://pt.wikipedia.org/wiki/Cluster <i>clusters</i>].
▲:Assim:
*Passo 1: (selecção de sementes).
:Escolher pontos semente <math>\ j_{k}</math> em <math>\ V</math> para iniciar cada <i>cluster</i> <math>\ k</math>.
**Passo 2: (Atribuição de clientes às sementes)
:Calcular o custo <math>\ d_{ik}</math> de atribuir cada consumidor <math>\ i</math> a cada <i>cluster</i> <math>\ k</math> como <math>\ d_{ik}=min({c_{0i}+c_{ij_{k}}+c_{j_{k}0},c_{0j_{k}}+c_{j_{k}i}+c_{i0}})-(c_{0j_{k}}+c_{j_{k}0})</math>
*Passo 3: (Generalização de atribuição).
:Resolver (PAG) com custo <math>\ d_{ij}</math>, <math>\ q_{i}</math> peso do cliente e <math>\ Q</math> a capacidade do veículo.
*Passo 4: (Solução PCV).
:Resolver um PCV para cada <i>cluster</i> correspondente à solução PAG.
 
===[[w:Algoritmo|Algoritmo]] de <i>Bramel e Simchi-Levi</i>===▼
([[Logística/Referências#refbPEVJ|AUREN, 2007]])
 
Neste método de acordo com [[Logística/Referências#refbPEVH|(TOTH e VIGO, 2001, p.118)]] as sementes são determinadas resolvendo um problema de capacidade local e os vértices que sobram, numa segunda fase são gradualmente incluídos na rota alocada.▼
▲===[[w:Algoritmo|Algoritmo]] de <i>Bramel e Simchi-Levi</i>===
 
:Assim:▼
▲Neste método as sementes são determinadas resolvendo um problema de capacidade local e os vértices que sobram, numa segunda fase são gradualmente incluídos na rota alocada.
*Localizando as sementes <math>\ k</math>, denominados "concentradores", entre as <math>\ n</math> localizações dos clientes para minimizar a distância total de clientes da semente mas próxima, enquanto se assegura que a procura total atribuidaatribuída a qualaquerqualquer "concentrador" não excede <math>\ Q</math>.▼
 
▲:Assim:
 
▲*Localizando as sementes <math>k</math>, denominados "concentradores", entre as <math>n</math> localizações dos clientes para minimizar a distância total de clientes da semente mas próxima, enquanto se assegura que a procura total atribuida a qualaquer "concentrador" não excede <math>Q</math>.
*As rotas dos veículos são então concebidas, inserindo em cada passo a atribuição do cliente à rota da semente que tenha o custo mínimo possível.
*Considerando uma rota parcial <math>\ k</math> descrita pelo vector <math>\ (0=i_{0},i_{1},...,i_{l},i_{l+1}</math>=0), seja <math>\ T_{k}=(o,i_{1},...,i_{l}</math>, denotar t(<math>\ T_{k}</math>) o tamanho da solução de PCV óptimo em <math>\ T_{k}</math>.
*Então o custo de inserção <math>\ d_{ik}</math> de um cliente sem rota <math>\ i</math> numa rota <math>\ k</math> é <math>\ d_{ik}=t(T_{k}</math>∪<math>\ {{i}})-t(T_{k})</math>.
*Visto que calcular <math>d_{ik}</math> exactamente é perda de tempo, são propostas duas aproximações custo mais próximo de inserção <math>\ d_{ik}^*=min_{h=0,...,l}(c_{i_{h}i}+c_{ii_{h+1}}</math>−<math>c_{i_{h}i_{h+1}})</math> e custo directo <math>\ d_{ik}^*=min_{h=1,...,l}(2c_{iih})</math>.
 
==[http[w://en.wikipedia.org/wiki/Branch_and_boundBranch and bound|<i>Branch and bound</i>]] truncado==▼
[[Logística/Referências#refbPEVH|(TOTH e VIGO, 2001, p.118)]]
:A árvore de procura neste processo contém tantos níveis quantas forem as rotas, cada nivelnível contém um conjunto de rotas "não dominadas".▼
Na sua formulação <math>\ F_{h}</math> é o conjunto rotas livres (vértices) no nível <math>\ h</math>.▼
 
:Assim:▼
 
▲==[http://en.wikipedia.org/wiki/Branch_and_bound <i>Branch and bound</i>] truncado==
 
▲:A árvore de procura neste processo contém tantos níveis quantas forem as rotas, cada nivel contém um conjunto de rotas "não dominadas".
▲Na sua formulação <math>F_{h}</math> é o conjunto rotas livres (vértices) no nível <math>h</math>.
 
▲:Assim:
 
*Passo 1: (Inicio).
:Estabelecer <math>\ h=1</math> e <math>\ F_{h}=V</math> \ {0}.▼
 
▲:Estabelecer <math>h=1</math> e <math>F_{h}=V</math> \ {0}.
 
*Passo 2: (Gerar rota).
:Se <math>\ F_{h}=</math>∅, parar. Caso contrário, seleccionar um cliente sem rota <math>\ i</math>∈<math>\ F_{h}</math> e gerar o conjunto <math>\ R_{i}</math> de rotas contento <math>\ i</math> e cliente em <math>\ F_{h}</math>. Estas rotas são gradualmente geradas usando combinação linear de dois critérios: poupança e custos de inserção.▼
 
▲:Se <math>F_{h}=</math>∅, parar. Caso contrário, seleccionar um cliente sem rota <math>i</math>∈<math>F_{h}</math> e gerar o conjunto <math>R_{i}</math> de rotas contento <math>i</math> e cliente em <math>F_{h}</math>. Estas rotas são gradualmente geradas usando combinação linear de dois critérios: poupança e custos de inserção.
 
*Passo 3: (Avaliação da rota).
:Avaliar cada rota <math>\ r</math>∈<math>\ R_{i}</math>, usando a função <math>\ f(r)=t(S_{r}</math>∪<math>\ {{0}})+</math><math>\ u(F_{h}</math> \ <math>\ S_{r}</math>, onde <math>\ S_{r}</math> é o vértice do conjunto de rotas <math>\ r</math>,<math>\ t(S_{r}</math>∪{0}) é o tamanho de uma boa solução PCV em <math>\ S_{r}</math>∪{0} e <math>\ u(F_{h}</math> \ <math>\ S_{r})</math> é a dimensão da [http[w://en.wikipedia.org/wiki/Spanning_tree_protocolSpanning Tree Protocol|<i>"Spanning tree"</i>]] mais curta dos ainda clientes sem rota.▼
 
▲:Avaliar cada rota <math>r</math>∈<math>R_{i}</math>, usando a função <math>f(r)=t(S_{r}</math>∪<math>{{0}})+</math><math>u(F_{h}</math> \ <math>S_{r}</math>, onde <math>S_{r}</math> é o vértice do conjunto de rotas <math>r</math>,<math>t(S_{r}</math>∪{0}) é o tamanho de uma boa solução PCV em <math>S_{r}</math>∪{0} e <math>u(F_{h}</math> \ <math>S_{r})</math> é a dimensão da [http://en.wikipedia.org/wiki/Spanning_tree_protocol <i>"Spanning tree"</i>] mais curta dos ainda clientes sem rota.
 
*Passo 4: (Selecção de rota).
:Determinar a rota <math>\ r^*</math> subtituindo <math>\ min(r</math>∈<math>\ R_{i})</math> {<math>\ {f(r)}</math>}. Fixando <math>\ h=h+1</math> e <math>\ F_{h}=F_{h-1}</math> \ <math>\ S_{r^*}</math> . Voltar ao passo 2.▼
 
==[[w:Algoritmo|Algoritmo]] <i>Petal</i>==▼
▲:Determinar a rota <math>r^*</math> subtituindo <math>min(r</math>∈<math>R_{i})</math> {<math>{f(r)}</math>}. Fixando <math>h=h+1</math> e <math>F_{h}=F_{h-1}</math> \ <math>S_{r^*}</math> . Voltar ao passo 2.
:O algoritmo <i>petal</i> (de acordo com [[http:Logística//pt.wikipedia.org/wiki/P%C3%A9talaReferências#refbPEVJ|(Dorronsoro, pétala2007a)]]) é uma extenção do algoritmo de varrimento para gerar várias rotas, denominadas <i>petals</i> ([http://pt.wikipedia.org/wiki/P%C3%A9tala pétalas]), e faz uma selecção final ao resolver um conjunto de problemas particionados na forma:▼
 
[[Logística/Referências#refbPEVH|(TOTH e VIGO, 2001, p.118)]]
 
 
▲==[[w:Algoritmo|Algoritmo]] <i>Petal</i>==
 
▲:O algoritmo <i>petal</i> ([http://pt.wikipedia.org/wiki/P%C3%A9tala pétala]) é uma extenção do algoritmo de varrimento para gerar várias rotas, denominadas <i>petals</i> ([http://pt.wikipedia.org/wiki/P%C3%A9tala pétalas]), e faz uma selecção final ao resolver um conjunto de problemas particionados na forma:
 
 
<center><font color=#0000FF><math>\color{Blue}\sum(_{k}</math>∈<math>_{S})d_{k}x_{k}</math></font></center>▼
 
▲<center><font color=#0000FF><math>\color{Blue} \sum(_{k}</math>∈<math>\ _{S})d_{k}x_{k}</math></font></center>
 
:Sujeito a
 
<center><font color=#0000FF><math>\color{Blue} \sum</math><math>(_{k}</math>∈<math>\ _{S})a_{ik}x_{k}=1</math> ∀<math>\ i=1,...,n,</math> </font></center><br>
 
<center><font color=#0000FF><math>x_{k}</math> ∈ {0,1} ∀ k ∈ S, </font></center>▼
 
▲<centermath><font\ color=#0000FF><math>x_{k}</math> ∈ {0,1} ∀ k ∈ S, </font></center>
 
:Onde <math>\ S</math> é o conjunto de rotas <math>\ x_{k}=1</math> se e só se a rota <math>\ k</math> pertencer à solução, <math>\ a_{ik}</math> o parametro binário igual a 1 apenas se o vértice <math>\ i</math> pertencer à rota <math>\ k</math> e <math>\ d_{k}</math> o custo de ''petal'' <math>\ k</math>. Se as rotas corresponderem sectores de vértices contíguos, então este problema possui a propriedade da coluna circular e pode ser resolvido em [http://pt.wikipedia.org/wiki/NP_%28complexidade%29 tempo polinimial] (Ryan, Hjorring and Glover).
 
([[Logística/Referências#refbPEVJ|AUREN, 2007]])
{{AutoCat}}
Obtido em "https://pt.wikibooks.org/wiki/Logística/Sistemas_de_distribuição/Escala_de_veículos/Agrupar-primeiro-e-rotas-depois"