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

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 $(0,...,i,0)$ e $(0,j,...,0)$ puderem ser misturadas em uma rota apenas $(0,...,i,j,...,0)$, a distância poupada $s_{ij}=c_{i0}+c_{0j}-c_{ij}$ é 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 $s_{ij}=c_{i0}+c_{0j}-c_{ij}$ para $i,j=1,...,n$ e $i\ne j$
• Criar $n$ rotas de veículos $(0,i,0)$ para $i=1,...,n$
• 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 $s_{ij}$, determinar de existem duas rotas que possam ser misturadas.
  • Uma começando em $(0,j)$.
  • Outra terminando em $(i,0)$.
• Combinar ambas, eliminando $(0,j)$ e $(i,0)$ introduzindo $(i,j)$.

Versão sequencial:

• Passo 2. Extensão da rota.
  • Determinar a primeira poupança $s_{ki}$ ou $s_{jl}$ que possa ser utilizado para fundir o caminho actual com outro caminho terminando em $(k,0)$ ou começando em $(0,l)$.
  • 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.