O truque de economia de Clarke e Wright tornou as rotas de entrega computáveis à mão

Em 1964, G. Clarke e J. W. Wright, trabalhando com a Cooperative Wholesale Society em Manchester, publicaram "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points" na Operations Research. O alvo deles era o problema de roteamento que Dantzig e Ramser haviam formalizado em 1959 — e para o qual as soluções exatas eram lentas demais para serem computadas.

O algoritmo de economia deles é quase constrangedoramente simples: comece com uma viagem de ida e volta separada para cada cliente, depois, para cada par de clientes, calcule quanta distância você economiza ao atendê-los em uma única viagem em vez de duas; funda os pares em ordem da maior economia, desde que a capacidade do veículo permita. Um curso da University of Southern Denmark ainda o ensina como a heurística construtiva clássica para o roteamento de veículos com capacidade.

Funcionou onde os métodos exatos não funcionavam: as rotas podiam ser calculadas à mão ou com os primeiros computadores, e o método tornou-se um bloco de construção padrão — uma solução inicial forte que metaheurísticas posteriores, como 2-opt, busca tabu e algoritmos genéticos, refinam.

Funda primeiro os pares que economizam mais distância

A medida de economia fez da escolha gulosa a escolha certa

Funcionou sem poder computacional caro

As restrições de capacidade foram tratadas naturalmente durante a fusão

Sua saída serviu de base para décadas de algoritmos melhores

Quando a resposta exata custa demais, uma regra gulosa sobre a medida certa ("economia") obtém a maior parte do valor — e você pode calculá-la hoje.

O algoritmo de economia de Clarke-Wright tornou-se uma das ideias mais citadas no roteamento de veículos e permanece uma referência em livros didáticos e softwares até hoje, frequentemente como ponto de partida para a otimização de rotas em frotas de entrega.