Logística/Sistemas de distribuição/Escala de veículos/Heurística construtiva

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa

O algoritmo da poupança segundo Dorronsoro (2007d) foi desenvolvido por Clarke e Wright em 1964, aplica-se a problemas onde o número de veículos não é fixo (trata-se de uma variável de decisão). Funcionando igualmente em problemas directos ou indirectos. Quando duas rotas e puderem ser misturadas em uma rota apenas , a distância poupada é gerada. O algoritmo segue os seguintes passos (o primeiro passo é idêntico para a versão paralela e sequencial).

Passo 1. Cálculo da poupança.

  • Calcular poupança para e
  • Criar rotas de veículos para
  • Ordenar as poupanças de forma decrescente

Versão paralela:

  • Passo 2. Melhor margem possível.

Apartir do todo da lista de poupanças, executar:

  • Dando uma poupança , determinar de existem duas rotas que possam ser misturadas.
    • Uma começando em .
    • Outra terminando em .
  • Combinar ambas, eliminando e introduzindo .

Versão sequencial:

  • Passo 2. Extensão da rota.
    • Determinar a primeira poupança ou que possa ser utilizado para fundir o caminho actual com outro caminho terminando em ou começando em .
    • Implementar a mistura e repetir a operação à rota actual.
    • Se não for viável a mistura, considerar a rota seguinte e replicar operações
    • Parar quando não for possível fundir mais rotas.