Mostrar código-fonte de Logística/Sistemas de distribuição/Escala de veículos/Agrupar-primeiro-e-rotas-depois

=Agrupar-primeiro-rotas-depois=
Segundo [[Logística/Referências#refbPEVZ|TOTH e VIGO]] (2002e, p.116 - 118) esta classe abarca três famílias de métodos abaixo descritos:

==Agrupamento elementar==

===Algoritmo de varrimento===
Este [[w:Algoritmo|algoritmo]] é aplicado a casos "planos" de PEV. Composto por duas partes:

*Divisão: [[w: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-[[w:Otimização| optimização]], onde vértices são trocados entre <i>clusters</i> adjacentes e rotas são optimizadas novamente.

*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 â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:(optimização da rota). Optimizar cada rota separadamente, resolvendo o correspondente PCV (exacto ou aproximado).

===Algoritmo de Bramel e Simchi-Levi===
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.

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 atribuída a qualquer "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>.

===Algoritmo de Fisher e Jaikumar===
O algoritmo de Fisher e Jaikumar segundo ([[Logística/Referências#refbPEVJ|Dorronsoro, 2007e]]) apresentado no livro <i>"A Generalized Assignment Heuristic for Vehicle Routing"</i> em 1981, resolve problemas de atribuição generalizada (PAG) ([[w:EN:Generalized assignment problem|<i>generalized assignment problem (GAP)</i>]] em Inglês), formando <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: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 ní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:

*Passo 1: (Inicio).
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.

*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 [[w: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.

==Algoritmo <i>Petal</i>==
O algoritmo <i>petal</i> é uma extenção do algoritmo de varrimento para gerar várias rotas, denominadas <i>petals</i>, e faz uma selecção final ao resolver um conjunto de problemas particionados na forma:

<math>\ \sum(_{k}</math>∈<math>\ _{S})d_{k}x_{k}</math>

:Sujeito a 

<math>\ \sum</math><math>(_{k}</math>∈<math>\ _{S})a_{ik}x_{k}=1</math> ∀<math>\ i=1,...,n,</math>  

<math>\ x_{k}</math> ∈ {0,1} ∀ k ∈ S, 

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 tempo polinimial  (Ryan, Hjorring and Glover).

{{AutoCat}}