Clarke und Wrights Einsparungstrick machte Lieferrouten von Hand berechenbar

Im Jahr 1964 veröffentlichten G. Clarke und J. W. Wright, die mit der Cooperative Wholesale Society in Manchester zusammenarbeiteten, „Scheduling of Vehicles from a Central Depot to a Number of Delivery Points“ in Operations Research. Ihr Ziel war das Routingproblem, das Dantzig und Ramser 1959 formalisiert hatten – und für das exakte Lösungen zu langsam zu berechnen waren.

Ihr Einsparungsalgorithmus ist fast schon peinlich einfach: Man beginnt mit einer separaten Rundreise für jeden Kunden und berechnet dann für jedes Kundenpaar, wie viel Strecke man einspart, wenn man beide auf einer Tour statt auf zwei bedient; anschließend führt man die Paare in der Reihenfolge der größten Einsparung zusammen, solange die Fahrzeugkapazität es zulässt. Ein Kurs der University of Southern Denmark lehrt ihn noch heute als klassische konstruktive Heuristik für das kapazitierte Fahrzeugrouting.

Er funktionierte dort, wo exakte Methoden versagten: Routen konnten von Hand oder mit frühen Computern berechnet werden, und die Methode wurde zu einem Standardbaustein – einer starken Ausgangslösung, die spätere Metaheuristiken wie 2-opt, Tabu-Suche und genetische Algorithmen verfeinern.

Führe zuerst die Paare zusammen, die die meiste Strecke einsparen

Das Einsparungsmaß machte die gierige Wahl zur richtigen Wahl

Er lief ohne teure Rechenleistung

Kapazitätsbeschränkungen wurden beim Zusammenführen auf natürliche Weise berücksichtigt

Sein Ergebnis bildete die Grundlage für Jahrzehnte besserer Algorithmen

Wenn die exakte Antwort zu viel kostet, bringt eine gierige Regel auf dem richtigen Maß („Einsparungen“) den größten Teil des Werts – und man kann sie heute berechnen.

Der Einsparungsalgorithmus von Clarke und Wright wurde zu einer der meistzitierten Ideen im Fahrzeugrouting und ist bis heute eine Referenz in Lehrbüchern und Software, oft als Ausgangspunkt für die Routenoptimierung in Lieferflotten.