Algoritmo das economias
Origem: Wikipédia, a enciclopédia livre.
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.
[editar] 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:
Sij = ci0 + c0j − cij
onde ci0 é a distância entre o ponto de entrega i e o depósito (aqui representado por 0), c0j é a distância entre o depósito 0 e o ponto de entrega j e cij é 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.
