El truco de ahorros de Clarke y Wright hizo que las rutas de reparto fueran calculables a mano

En 1964, G. Clarke y J. W. Wright, trabajando con la Cooperative Wholesale Society en Mánchester, publicaron «Scheduling of Vehicles from a Central Depot to a Number of Delivery Points» en Operations Research. Su objetivo era el problema de enrutamiento que Dantzig y Ramser habían formalizado en 1959, y para el cual las soluciones exactas eran demasiado lentas de calcular.

Su algoritmo de ahorros es casi vergonzosamente simple: se empieza con un viaje de ida y vuelta separado para cada cliente, luego, para cada par de clientes, se calcula cuánta distancia se ahorra al atenderlos en un solo viaje en lugar de dos; se fusionan los pares en orden de mayor ahorro, siempre que la capacidad del vehículo lo permita. Un curso de la Universidad del Sur de Dinamarca todavía lo enseña como la heurística constructiva clásica para el enrutamiento de vehículos con capacidad.

Funcionó donde los métodos exactos no lo hacían: las rutas podían calcularse a mano o con computadoras tempranas, y el método se convirtió en un bloque de construcción estándar: una solución inicial sólida que metaheurísticas posteriores como 2-opt, la búsqueda tabú y los algoritmos genéticos refinan.

Fusionar primero los pares que ahorran más distancia

La medida de ahorro hizo que la elección codiciosa fuera la elección correcta

Funcionaba sin necesidad de una potencia de cálculo costosa

Las restricciones de capacidad se manejaban de forma natural durante la fusión

Su resultado sirvió de base para décadas de mejores algoritmos

Cuando la respuesta exacta cuesta demasiado, una regla codiciosa sobre la medida correcta («ahorros») te da la mayor parte del valor, y puedes calcularla hoy.

El algoritmo de ahorros de Clarke-Wright se convirtió en una de las ideas más citadas en el enrutamiento de vehículos y sigue siendo una referencia en libros de texto y software hoy en día, a menudo como punto de partida para la optimización de rutas en flotas de reparto.