Es gibt in der Tourenplanung ein Verfahren, das älter ist als die meisten Speditionen, die es einsetzen, das ohne Computer funktioniert und das trotzdem in jeder modernen Optimierungsbibliothek steckt. Der Savings-Algorithmus von Clarke und Wright, veröffentlicht 1964 in Operations Research, ist der Maßstab, an dem sich alles andere messen lassen muss.
Wie er funktioniert – in einem Absatz
Man beginnt mit dem denkbar schlechtesten Plan: Für jeden Kunden fährt ein eigenes Fahrzeug vom Depot hin und zurück. Dann berechnet man für jedes Kundenpaar i und j die Ersparnis, die entsteht, wenn man beide auf einer Tour bedient statt auf zweien:
s(i,j) = d(Depot,i) + d(Depot,j) − d(i,j)
Das ist nichts anderes als die Depotstrecke, die man nicht mehr doppelt fährt, abzüglich des Umwegs zwischen den beiden Stopps. Diese Ersparnisse sortiert man absteigend. Dann geht man die Liste von oben nach unten durch und verbindet jeweils die beiden Touren, auf denen i und j liegen – aber nur, wenn beide noch am Ende ihrer jeweiligen Tour stehen und die zusammengelegte Ladung ins Fahrzeug passt. Man hört auf, wenn keine zulässige Verbindung mehr übrig ist.
Ein Durchlauf. Kein Zurückspringen. Keine Parameter. Man kann es mit Bleistift und Papier machen.
Wie gut ist er wirklich?
Hier wird es interessant, denn zu dieser Frage kursieren Zahlen, die sich nicht belegen lassen. Die belastbarste Antwort stammt aus einer Reproduktionsstudie: Jussi Rasku hat in seiner Dissertation an der Universität Jyväskylä fünfzehn klassische Verfahren neu implementiert und auf 454 CVRP-Benchmark-Instanzen gerechnet. Der Quellcode ist als Projekt VeRyPy öffentlich.
Die Ergebnisse für den Abstand zur besten bekannten Lösung:
- Clarke & Wright, parallele Variante: 6,3 Prozent im Mittel, 0,2 Sekunden Rechenzeit
- Beste Savings-Variante (Paessens 1988): 3,7 Prozent, 8,5 Sekunden
- Nearest Neighbour: 15,3 Prozent
- Sequenzielle Savings-Variante: 29,1 Prozent
Zum Vergleich die modernen Verfahren aus der Benchmark-Studie von Uchoa und Kollegen: UHGS erreicht 0,19 Prozent – in im Mittel 98,79 Minuten Rechenzeit pro Instanz.
Das ist die eigentliche Geschichte. Ein Verfahren von 1964 liefert in zwei Zehntelsekunden ein Ergebnis, das rund sechs Prozent neben dem Bestwert liegt. Ein Verfahren von 2017 kommt auf zwei Zehntel Prozent – braucht dafür aber gut anderthalb Stunden. Das Verhältnis von Aufwand zu Ergebnis ist beim alten Verfahren um Größenordnungen besser.
Rasku selbst formuliert es so:
„it is interesting to see that the original savings heuristic from Clarke and Wright (1964) (CW64-PS) still holds its ground against the later classical methods"
Eine Zahl, die Sie nicht verwenden sollten
In der Literatur und erst recht in Anbieterunterlagen liest man häufig, klassische Heuristiken wie Clarke & Wright lägen „typischerweise 10 bis 15 Prozent" über dem Optimum. Diese Angabe findet sich unter anderem bei Rasku selbst, der sie einer Arbeit von Renaud, Boctor und Laporte aus dem Jahr 1996 zuschreibt. In deren Abstract steht allerdings nur, Lösungen der ersten Heuristikgeneration seien „often far from optimal" – eine Spanne wird nicht genannt.
Wir verwenden deshalb die 6,3 Prozent aus der Reproduktionsstudie. Sie ist gemessen, auf 454 Instanzen gerechnet und der Code liegt offen.
Warum das Verfahren nach sechzig Jahren noch eingebaut wird
Google OR-Tools, die verbreitetste offene Optimierungsbibliothek, führt Savings als benannte Startheuristik – FirstSolutionStrategy.SAVINGS und PARALLEL_SAVINGS. Im Quellcode steht die akademische Quellenangabe im Klartext daneben:
// Savings algorithm (Clarke & Wright).// Reference: Clarke, G. & Wright, J.W.: "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points", Operations Research, Vol. 12, 1964, pp. 568-581
Dafür gibt es vier Gründe:
- Das Verhältnis von Aufwand zu Ergebnis. 6,3 Prozent in 0,2 Sekunden gegen 0,19 Prozent in 99 Minuten.
- Es ist deterministisch. Zweimal derselbe Input ergibt zweimal denselben Plan. Metaheuristiken tun das in der Regel nicht.
- Es ist erklärbar. Ein Disponent kann nachvollziehen, warum zwei Stopps auf einer Tour gelandet sind: weil die Ersparnis dieses Paars hoch genug war. Bei einem genetischen Algorithmus lässt sich diese Frage nicht beantworten.
- Es ist ein guter Startpunkt. Moderne Solver nutzen es nicht als Endergebnis, sondern als Ausgangslösung, die anschließend verbessert wird.
Der letzte Punkt ist der wichtigste. In einer heutigen Toolchain ist Savings nicht der Optimierer, sondern dessen erster Schritt.
Wann sechs Prozent reichen – und wann nicht
Rasku zieht aus seinen Zahlen eine Konsequenz, die für die Praxis brauchbarer ist als jede Prozentangabe:
„the performance of the simple classical heuristics is often good enough for practical, real world vehicle routing. Only if the operational fleet is capable of executing tightly planned routes, it is worth to pay the price in extra complexity brought in by a more sophisticated method."
Das ist der entscheidende Punkt. Die Frage ist nicht, ob 6,3 Prozent gut sind, sondern ob Ihre Flotte einen Plan überhaupt so genau fahren kann, dass sich der Unterschied bemerkbar macht. Wenn Standzeiten um zwanzig Minuten schwanken, Fahrer eigene Reihenfolgen bevorzugen und der Kunde ohnehin nachbestellt, ist der Unterschied zwischen 6,3 und 0,19 Prozent Rauschen.
Umgekehrt: Wo eng getaktet gefahren wird, wo Zeitfenster hart sind, wo jedes Fahrzeug zählt, ist er bares Geld. Bei 7.842 geplanten Kilometern an einem Tag sind sechs Prozent rund 470 Kilometer.
Was Savings strukturell nicht kann
Drei Dinge, die man wissen sollte, bevor man das Verfahren produktiv einsetzt:
- Es kennt keine Zeitfenster. Die Grundform berücksichtigt nur Kapazität. Zeitfenster, Lenkzeiten, Fahrzeugprofile müssen nachträglich geprüft oder in Varianten eingebaut werden – dann verliert es seine Einfachheit.
- Es verbessert nicht. Ist eine Verbindung einmal gemacht, wird sie nicht mehr in Frage gestellt. Genau hier setzen die modernen Verfahren an.
- Es optimiert Kilometer, nicht Kosten. Fahrerstunden, Maut und Verbrauch tauchen in der Ersparnisformel nicht auf.
Wer eine Software bewertet, sollte deshalb weniger fragen, welche Verfahren sie enthält, als welche Restriktionen sie abbilden kann – dazu haben wir eine vollständige Übersicht zusammengestellt.
Der praktische Nutzen für Sie
Savings ist die ehrlichste Vergleichsgröße, die es gibt. Wenn Ihnen jemand eine Optimierung verkauft, ist die richtige Frage nicht „wie viel spart das gegenüber unserer heutigen Planung?", sondern:
Wie viel besser ist es als Clarke & Wright von 1964?
Denn Savings ist in zwei Zehntelsekunden gerechnet und kostet nichts. Alles, was ein kommerzielles System darüber hinaus verlangt, muss den Abstand zu dieser Grundlinie rechtfertigen – nicht den Abstand zu einer schlecht gepflegten Excel-Tabelle.
Wo Savings zwischen den übrigen Methoden steht und wann welche davon trägt, ordnet der Überblick Verfahren der Tourenoptimierung ein. Was moderne Verfahren gegenüber dieser Baseline gewinnen, steht im Leitfaden zur Tourenoptimierung. Den direkten Vergleich zwischen gewachsener und gerechneter Planung zieht der Beitrag Manuelle vs. dynamische Tourenplanung.
Quellen
- Clarke, G.; Wright, J. W. (1964): Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research 12(4), S. 568–581. doi.org/10.1287/opre.12.4.568
- Rasku, J.; Kärkkäinen, T.; Musliu, N. (2019): Meta-Survey and Implementations of Classical Capacitated Vehicle Routing Heuristics with Reproduced Results. In: J. Rasku, Toward Automatic Customization of Vehicle Routing Systems, JYU Dissertations 113, Universität Jyväskylä, S. 133–260. urn.fi/URN:ISBN:978-951-39-7826-6
- Uchoa, E. u. a. (2017): New benchmark instances for the Capacitated Vehicle Routing Problem. EJOR 257(3), S. 845–858. doi.org/10.1016/j.ejor.2016.08.012
- Renaud, J.; Boctor, F. F.; Laporte, G. (1996): An Improved Petal Heuristic for the Vehicle Routeing Problem. JORS 47(2), S. 329–336. doi.org/10.1057/jors.1996.29
- Google OR-Tools, Quelldatei
routing_enums.proto(Apache-2.0-Lizenz)