Para a resolução de problemas de roteamento de veículos (PRV) podem ser utilizadas algumas heurísticas, que compreendem diferentes procedimentos. O procedimento de Economia e Inser

Gabarito

A

Comentário do professor

Clark e Wright é uma heurística clássica de *economia*, também chamada de algoritmo de economias, que combina o critério de economia com uma lógica de inserção. Parte-se da solução trivial: cada cliente em uma rota separada de/para o depósito.

Calcula-se a economia ao juntar dois clientes i e j por \(s_{ij}=c_{0i}+c_{0j}-c_{ij}\), onde \(c_{0i}\) e \(c_{0j}\) são as distâncias do depósito e \(c_{ij}\) é a distância direta entre i e j. Valores maiores indicam maior redução de custo.

As economias são ordenadas decrescentemente e os pares são avaliados sequencialmente. Se a união das rotas respeitar restrições (por exemplo, capacidade do veículo e sequência de extremidades), os clientes são inseridos na mesma rota, reduzindo o custo total.

Esse procedimento simples e eficiente gera boas soluções iniciais para PRV e serve como base para refinamentos posteriores.