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\neq 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.