Algoritmo das economias

O Algoritmo das economias realiza a progressão da uma configuração para outra segundo o critério de minimização da função objetivo, também chamado de saving (economia). Um dos problemas clássicos que o algoritmo das economias pode resolver é o Problema de Roteamento de Veículos (PRV).

Um PRV consiste basicamente em estabelecer e organizar rotas ou itinerários eficientes para veículos realizarem entregas de mercadorias. Em outras palavras, dispomos de uma frota de $k$ veículos idênticos ou não e desejamos atender um conjunto de $n$ clientes, cada um com uma demanda específica. Todos os veículos devem partir e retornar a uma mesma origem (depósito) e cada cliente deve ser visitado uma única vez. O objetivo geral será minimizar o "custo total" de transporte no atendimento aos clientes, isto é, minimizar custos fixos, custos operacionais e o número de veículos envolvidos no transporte.

Arcos de menor custo devem substituir arcos mais caros dentro da rota que vai sendo melhorada nesses termos. No procedimento de economia e inserção não existe a obrigatoriedade de que a rota seja viável ao longo do processo de melhoria. Se alguma solução alcançada for viável, então caracteriza-se a obtenção de um limite superior para o problema.

O Algoritmo das Economias

Primeiramente, forma-se uma solução inicial para $n$ pontos de entrega com $n$ rotas, todas contendo o depósito e um ponto de entrega. Após esta fase, tenta-se unir duas rotas em uma rota factível a cada iteração. Sendo $i$ e $j$ dois pontos de entrega, o critério utilizado para eliminar o maior custo é dado por:

$S_{ij}=c_{i0}+c_{0j}-c_{ij}$

onde $c_{i0}$ é a distância entre o ponto de entrega $i$ e o depósito (aqui representado por $0$), $c_{0j}$ é a distância entre o depósito $0$ e o ponto de entrega $j$ e $c_{ij}$ é a distância entre os dois pontos de entrega.

A cada iteração as rotas são organizadas em conjuntos de pares. Um ponto $i$ e um ponto $j$ podem formar o par $(i,j)$ se:

• os pontos de entrega $i$ e $j$ não estão na mesma rota;
• a capacidade de carga do veículo não é violada;
• nem $i$ nem $j$ são pontos interiores em uma rota.

Um ponto interior em uma rota significa que seu ponto anterior e seu ponto sucessor não podem ser o depósito.