L'astuce d'économie de Clarke et Wright a rendu les itinéraires de livraison calculables à la main

En 1964, G. Clarke et J. W. Wright, travaillant avec la Cooperative Wholesale Society à Manchester, ont publié « Scheduling of Vehicles from a Central Depot to a Number of Delivery Points » dans Operations Research. Leur objectif était le problème de routage que Dantzig et Ramser avaient formalisé en 1959 — et pour lequel les solutions exactes étaient trop lentes à calculer.

Leur algorithme des économies est d'une simplicité presque embarrassante : commencer par un aller-retour séparé pour chaque client, puis pour chaque paire de clients calculer la distance économisée en les servant sur un seul trajet plutôt que deux ; fusionner les paires par ordre d'économie décroissante, tant que la capacité du véhicule le permet. Un cours de l'Université du Danemark du Sud l'enseigne encore comme l'heuristique constructive classique pour le problème de routage de véhicules avec capacités.

Il fonctionnait là où les méthodes exactes échouaient : les itinéraires pouvaient être calculés à la main ou avec les premiers ordinateurs, et la méthode est devenue un bloc de construction standard — une solution de départ solide que des métaheuristiques ultérieures comme 2-opt, la recherche tabou et les algorithmes génétiques affinent.

Fusionner d'abord les paires qui économisent le plus de distance

La mesure d'économie faisait du choix glouton le bon choix

Il fonctionnait sans puissance de calcul coûteuse

Les contraintes de capacité étaient gérées naturellement lors de la fusion

Son résultat a servi de base à des décennies de meilleurs algorithmes

Quand la réponse exacte coûte trop cher, une règle gloutonne sur la bonne mesure (« économies ») vous apporte l'essentiel de la valeur — et vous pouvez la calculer dès aujourd'hui.

L'algorithme des économies de Clarke-Wright est devenu l'une des idées les plus citées en routage de véhicules et reste une référence dans les manuels et les logiciels aujourd'hui, souvent comme point de départ pour l'optimisation d'itinéraires dans les flottes de livraison.