Logística/Sistemas de distribuição/Escala de veículos/Agrupar-primeiro-e-rotas-depois

Agrupar-primeiro-rotas-depoisEditar

Segundo TOTH e VIGO (2002e, p.116 - 118) esta classe abarca três famílias de métodos abaixo descritos:

Agrupamento elementarEditar

Algoritmo de varrimentoEditar

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   é representado pelas suas coordenadas polares (θ  ) onde θ  é o angulo e ρ  é o comprimento do raio. Atribuindo o valor θ  a um vértice arbitrário   e calculando os ângulos que sobram de  . Classificar os vértices por ordem crescente de (θ ).
    • Passo 1: (iniciação da rota).

Escolher um veículo   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   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-LeviEditar

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  , denominados "concentradores", entre as   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  .
  • 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   descrita pelo vector  =0), seja  , denotar t( ) o tamanho da solução de PCV óptimo em  .
  • Então o custo de inserção   de um cliente sem rota   numa rota   é   .
  • Visto que calcular   exactamente é perda de tempo, são propostas duas aproximações custo mais próximo de inserção    e custo directo  .

Algoritmo de Fisher e JaikumarEditar

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   em   para iniciar cada cluster  .

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

Calcular o custo   de atribuir cada consumidor   a cada cluster   como  

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

Resolver (PAG) com custo  ,   peso do cliente e   a capacidade do veículo.

  • Passo 4: (Solução PCV).

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

Branch and bound truncadoEditar

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   é o conjunto rotas livres (vértices) no nível  .

Assim:

  • Passo 1: (Inicio).

Estabelecer   e   \ {0}.

  • Passo 2: (Gerar rota).

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

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

Determinar a rota   subtituindo    { }. Fixando   e   \   . Voltar ao passo 2.

Algoritmo PetalEditar

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:

  

Sujeito a

    

  ∈ {0,1} ∀ k ∈ S,

Onde   é o conjunto de rotas   se e só se a rota   pertencer à solução,   o parametro binário igual a 1 apenas se o vértice   pertencer à rota   e   o custo de petal  . 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).