Saltar para o conteúdo

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

Origem: Wikilivros, livros abertos por um mundo aberto.

Agrupar-primeiro-rotas-depois

[editar | editar código-fonte]

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

Agrupamento elementar

[editar | editar código-fonte]

Algoritmo de varrimento

[editar | editar código-fonte]

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-Levi

[editar | editar código-fonte]

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 Jaikumar

[editar | editar código-fonte]

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.

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 Petal

[editar | editar código-fonte]

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).