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 ${\displaystyle k}$ veículos idênticos ou não e desejamos atender um conjunto de ${\displaystyle 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 ${\displaystyle n}$ pontos de entrega com ${\displaystyle 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 ${\displaystyle i}$ e ${\displaystyle j}$ dois pontos de entrega, o critério utilizado para eliminar o maior custo é dado por:

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

onde ${\displaystyle c_{i0}}$ é a distância entre o ponto de entrega ${\displaystyle i}$ e o depósito (aqui representado por ${\displaystyle 0}$), ${\displaystyle c_{0j}}$ é a distância entre o depósito ${\displaystyle 0}$ e o ponto de entrega ${\displaystyle j}$ e ${\displaystyle 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 ${\displaystyle i}$ e um ponto ${\displaystyle j}$ podem formar o par ${\displaystyle (i,j)}$ se:

• os pontos de entrega ${\displaystyle i}$ e ${\displaystyle j}$ não estão na mesma rota;
• a capacidade de carga do veículo não é violada;
• nem ${\displaystyle i}$ nem ${\displaystyle 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.

Este artigo sobre Algoritmos é um esboço. Você pode ajudar a Wikipédia expandindo-o.