Agrupar-primeiro-rotas-depois

Segundo 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 algoritmo é aplicado a casos "planos" de PEV. Composto por duas partes:

Divisão: clusters exequíveis são inicialmente formados rodando um raio centrado no depósito.
Problema do caixeiro viajante (PCV): É obtida então para cada cluster uma rota, ao resolver PCV.

Em alguns casos tem-se um fase de pós- optimização, onde vértices são trocados entre clusters adjacentes e rotas são optimizadas novamente.

Assumindo cada vértice $\ i$ $\ i$ é representado pelas suas coordenadas polares (θ $\ _{i}$ $\ _{i}$ ,ρ $_{i}$ $_{i}$ ) onde θ $\ _{i}$ $\ _{i}$ é o angulo e ρ $\ _{i}$ $\ _{i}$ é o comprimento do raio. Atribuindo o valor θ $\ _{i}^{*}=0$ $\ _{i}^{*}=0$ a um vértice arbitrário $\ i^{*}$ $\ i^{*}$ e calculando os ângulos que sobram de $\ (0,i^{*})$ $\ (0,i^{*})$ . Classificar os vértices por ordem crescente de (θ $\ _{i}$ $\ _{i}$ ).
- Passo 1: (iniciação da rota).

Escolher um veículo $\ k$ 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 $\ k$ 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 $\ k$ , denominados "concentradores", entre as $\ n$ 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 $\ Q$ .
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 $\ k$ descrita pelo vector $\ (0=i_{0},i_{1},...,i_{l},i_{l+1}$ =0), seja $\ T_{k}=(o,i_{1},...,i_{l}$ , denotar t( $\ T_{k}$ ) o tamanho da solução de PCV óptimo em $\ T_{k}$ .
Então o custo de inserção $\ d_{ik}$ de um cliente sem rota $\ i$ numa rota $\ k$ é $\ d_{ik}=t(T_{k}$ ∪ $\ {i})-t(T_{k})$ .
Visto que calcular $d_{ik}$ exactamente é perda de tempo, são propostas duas aproximações custo mais próximo de inserção $\ d_{ik}^{*}=min_{h=0,...,l}(c_{i_{h}i}+c_{ii_{h+1}}$ − $c_{i_{h}i_{h+1}})$ e custo directo $\ d_{ik}^{*}=min_{h=1,...,l}(2c_{iih})$ .

Algoritmo de Fisher e Jaikumar

O algoritmo de Fisher e Jaikumar segundo (Dorronsoro, 2007e) apresentado no livro "A Generalized Assignment Heuristic for Vehicle Routing" em 1981, resolve problemas de atribuição generalizada (PAG) (generalized assignment problem (GAP) em Inglês), formando clusters.

Assim:

Passo 1: (selecção de sementes).

Escolher pontos semente $\ j_{k}$ em $\ V$ para iniciar cada cluster $\ k$ .

- Passo 2: (Atribuição de clientes às sementes)

Calcular o custo $\ d_{ik}$ de atribuir cada consumidor $\ i$ a cada cluster $\ k$ como $\ 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})$

Passo 3: (Generalização de atribuição).

Resolver (PAG) com custo $\ d_{ij}$ , $\ q_{i}$ peso do cliente e $\ Q$ a capacidade do veículo.

Passo 4: (Solução PCV).

Resolver um PCV para cada cluster correspondente à solução PAG.

Branch and bound 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 $\ F_{h}$ é o conjunto rotas livres (vértices) no nível $\ h$ .

Assim:

Passo 1: (Inicio).

Estabelecer $\ h=1$ e $\ F_{h}=V$ \ {0}.

Passo 2: (Gerar rota).

Se $\ F_{h}=$ ∅, parar. Caso contrário, seleccionar um cliente sem rota $\ i$ ∈ $\ F_{h}$ e gerar o conjunto $\ R_{i}$ de rotas contento $\ i$ e cliente em $\ F_{h}$ . 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 $\ r$ ∈ $\ R_{i}$ , usando a função $\ f(r)=t(S_{r}$ ∪ $\ {0})+$ $\ u(F_{h}$ \ $\ S_{r}$ , onde $\ S_{r}$ é o vértice do conjunto de rotas $\ r$ , $\ t(S_{r}$ ∪{0}) é o tamanho de uma boa solução PCV em $\ S_{r}$ ∪{0} e $\ u(F_{h}$ \ $\ S_{r})$ é a dimensão da Spanning tree mais curta dos ainda clientes sem rota.

Passo 4: (Selecção de rota).

Determinar a rota $\ r^{*}$ subtituindo $\ min(r$ ∈ $\ R_{i})$ { $\ {f(r)}$ }. Fixando $\ h=h+1$ e $\ F_{h}=F_{h-1}$ \ $\ S_{r^{*}}$ . Voltar ao passo 2.

Algoritmo Petal

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

$\ \sum (_{k}$ ∈ $\ _{S})d_{k}x_{k}$

Sujeito a

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

$\ x_{k}$ ∈ {0,1} ∀ k ∈ S,

Onde $\ S$ é o conjunto de rotas $\ x_{k}=1$ se e só se a rota $\ k$ pertencer à solução, $\ a_{ik}$ o parametro binário igual a 1 apenas se o vértice $\ i$ pertencer à rota $\ k$ e $\ d_{k}$ o custo de petal $\ k$ . 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).