Verfahren der Tourenoptimierung: welcher Algorithmus wann trägt.

Warum die Verfahrensfrage überhaupt zählt

Wer Tourenplanung einkauft, bekommt fast immer dieselbe Antwort auf die Frage nach der Methode: „unser Optimierungsalgorithmus“. Das ist keine Antwort, sondern eine Kategorie. Tatsächlich rechnet unter praktisch jedem Produkt am Markt eine Kombination aus drei, vier bekannten Bausteinen, und die stehen in Aufsätzen, die zwischen 1959 und heute erschienen sind. Man kann sie benennen, und man kann fragen, welche davon drin sind.

Der Grund, warum sich das lohnt, ist nicht Neugier. Es ist die Reihenfolge der Hebel. Zwischen einem soliden und einem hervorragenden Verfahren liegen auf offenen Benchmarks wenige Prozent. Zwischen einem Modell, das Ihre Restriktionen abbildet, und einem, das sie vereinfacht, liegen zweistellige Prozentsätze – und die Frage, ob der Plan überhaupt fahrbar ist. Wer das weiß, stellt im Anbietertermin andere Fragen.

Das Problem dahinter, in drei Sätzen

Formal geht es um das Vehicle Routing Problem: Gegeben sind ein oder mehrere Depots, eine Menge Kunden mit Bedarfen und eine Flotte mit Kapazitäten; gesucht sind Touren, die alle Kunden bedienen und die Gesamtkosten minimieren. Der Ursprung ist ein Aufsatz von Dantzig und Ramser aus dem Jahr 1959 über die Belieferung von Tankstellen.1 Das Problem ist NP-schwer4 – praktisch heißt das nicht „unlösbar“, sondern: Der Aufwand, Optimalität zu beweisen, wächst schneller, als Rechenleistung ihn einholt.

Alles, was folgt, ist eine Antwort auf diese eine Schwierigkeit. Die Verfahren unterscheiden sich darin, wie sie mit der Unmöglichkeit umgehen, alles durchzuprobieren. Die Grundlagen dazu stehen ausführlich im Beitrag Vehicle Routing Problem.

Die drei Familien

Sortiert man die Verfahren nach dem, was sie tun, bleiben drei Gruppen. Fast jedes reale System benutzt aus jeder Gruppe etwas:

• Konstruktionsverfahren bauen aus dem Nichts einen ersten zulässigen Plan. Schnell, grob, unverzichtbar – ohne Startlösung hat die Verbesserung nichts, woran sie arbeiten kann.
• Verbesserungsverfahren nehmen einen Plan und verändern ihn schrittweise: lokale Suche, gesteuert von einer Metaheuristik, die verhindert, dass die Suche im erstbesten lokalen Minimum stehen bleibt. Hier entsteht der weitaus größte Teil der Einsparung.
• Exakte Verfahren beweisen, dass es keine bessere Lösung gibt. Wertvoll als Maßstab, in der Disposition praktisch nie einsetzbar.

Konstruktion: das Savings-Verfahren und seine Geschwister

Das bekannteste Konstruktionsverfahren ist das Savings-Verfahren von Clarke und Wright aus dem Jahr 1964.2 Es beginnt mit dem schlechtesten denkbaren Plan – je Kunde eine eigene Pendelfahrt ab Depot – und berechnet für jedes Kundenpaar die Ersparnis, die das Zusammenlegen bringt: die doppelt gefahrene Depotstrecke abzüglich des Umwegs. Diese Ersparnisse werden absteigend abgearbeitet, solange Kapazität und Tourstruktur es zulassen.

Bemerkenswert ist nicht das Alter, sondern die Güte. In einer Untersuchung, die die klassischen Verfahren systematisch nachimplementiert und nachgemessen hat, liegt Savings im Mittel rund sechs Prozent über der besten bekannten Lösung – bei Rechenzeiten im Bereich von Zehntelsekunden.2 Für eine Disposition, die heute von Hand plant, ist das bereits der größte Einzelsprung, den sie je machen wird. Ausführlich im Beitrag Savings-Algorithmus.

• Sweep- und Petal-Verfahren gruppieren zuerst geografisch und planen dann je Gruppe eine Tour („cluster-first, route-second“). Anschaulich, gut erklärbar, in der Güte meist unter Savings.
• Einfügeverfahren setzen Kunden nacheinander an der jeweils günstigsten Stelle in bestehende Touren ein. Ihr eigentlicher Wert liegt heute woanders: Sie sind der Wiederaufbau-Schritt in Large Neighborhood Search und laufen dort millionenfach.

Verbesserung: lokale Suche und ihre Grenze

Ein fertiger Plan lässt sich mit einer Handvoll immer gleicher Züge verändern: zwei Kanten tauschen (2-opt), eine Kundenfolge an anderer Stelle einhängen (Or-opt), einen Kunden zwischen Touren verschieben (Relocate) oder zwei Kunden tauschen (Swap). Man nimmt jeden Zug an, der besser ist, und hört auf, wenn keiner mehr besser ist.

Genau dort liegt das Problem: Der Punkt, an dem kein einzelner Zug mehr hilft, ist fast nie der beste Plan, sondern ein lokales Minimum. Aus ihm herauszukommen erfordert, vorübergehend eine schlechtere Lösung zu akzeptieren – und die Regeln dafür sind das, was man Metaheuristik nennt.

Die vier Metaheuristiken, die tatsächlich im Einsatz sind

• Tabu Search (Glover 1986, für Touren Gendreau/Hertz/Laporte 1994)5 führt Buch über kürzlich gemachte Züge und verbietet, sie sofort rückgängig zu machen. Die Suche wird dadurch gezwungen, das Tal zu verlassen. Robust, gut verstanden, wenig Einstellaufwand.
• Simulated Annealing (Kirkpatrick 1983)6 akzeptiert Verschlechterungen mit einer Wahrscheinlichkeit, die im Lauf der Rechnung sinkt. Sehr einfach zu implementieren, dafür empfindlich gegenüber der Abkühlkurve.
• Large Neighborhood Search (Shaw 1998), adaptiv erweitert von Ropke und Pisinger 20067, reißt in jedem Schritt einen Teil des Plans ein und baut ihn neu auf. Das ist der Ansatz, der mit vielen und harten Restriktionen am besten zurechtkommt – und deshalb der, der in der Praxis am häufigsten trägt.
• Guided Local Search (Voudouris/Tsang 1999)8 verändert nicht die Suche, sondern die Zielfunktion: Merkmale, die in lokalen Minima immer wieder auftauchen, werden mit Strafkosten belegt. In Googles OR-Tools ist GLS die übliche Wahl für Tourenprobleme.

Als derzeit stärkste Familie auf reinen Kapazitätsproblemen gilt Hybrid Genetic Search: eine Population von Lösungen, kombiniert mit lokaler Suche.10 Auf dem offenen Benchmark von Uchoa und Kollegen erreichen moderne Verfahren dieser Bauart im Mittel 0,19 Prozent Abstand zur besten bekannten Lösung.3 Die Tiefe zu diesen Verfahren steht im Beitrag Metaheuristiken.

Exakte Verfahren: der Maßstab, nicht das Werkzeug

Branch-Cut-and-Price-Verfahren beweisen Optimalität. Auf dem Benchmark von 2017 mit 100 Instanzen zwischen 100 und 1.000 Kunden ließen sich damit 40 Instanzen beweisbar optimal lösen, mit Rechenzeiten bis zu fünf Tagen für einen einzelnen Fall; die Grenze liegt in der Größenordnung von 275 Kunden.3 Ein Regionalnetz mit 320 Lieferstellen liegt bereits darüber.

Daraus folgt eine Haltung, die in Verkaufsgesprächen selten vorkommt: Optimalität ist kein sinnvolles Ziel. Sie ist ab dieser Größe nicht beweisbar, und sie wäre – für einen Plan, der auf geschätzten Standzeiten und prognostizierten Fahrzeiten beruht – ohnehin Scheingenauigkeit. Der Nutzen exakter Verfahren liegt woanders: Sie liefern auf kleinen Teilproblemen die Referenz, an der man misst, wie gut eine Heuristik wirklich ist.

Welches Verfahren wann trägt

Eine grobe, aber belastbare Zuordnung. Sie ersetzt keine Messung auf den eigenen Daten, hilft aber, ein Angebot einzuordnen:

• Wenige Fahrzeuge, kaum Restriktionen, Ergebnis in Sekunden – Savings plus lokale Suche. Reicht erstaunlich weit und ist in jeder Bibliothek enthalten.
• Viele harte Restriktionen – Zeitfenster, Lenkzeiten, Temperaturzonen, Fahrerqualifikationen: Large Neighborhood Search. Sie kommt mit Zulässigkeitsprüfungen zurecht, an denen reine Nachbarschaftszüge scheitern.
• Reine Kilometerminimierung, große Instanz, Rechenzeit vorhanden – Hybrid Genetic Search. Der letzte Prozentpunkt kommt von hier.
• Planung am laufenden Tag, Umplanung in Sekunden – nicht die Verfahrensfrage entscheidet, sondern die Architektur: warme Startlösung, begrenzte Nachbarschaft, harte Zeitschranke. Dazu manuelle gegen dynamische Tourenplanung.
• Kleines Teilproblem, Referenzwert gesucht – exaktes Verfahren, einmalig, offline.

Was in der Praxis mehr entscheidet als die Verfahrenswahl

Die unbequeme Wahrheit dieses Beitrags: In fast allen Projekten, die wir sehen, ist das Verfahren nicht der Engpass. Vier andere Dinge sind es:

• Das Modell. Ob Rampenzeiten je Kunde, mehrere Temperaturzonen oder Fahrerqualifikationen überhaupt abgebildet sind, entscheidet über die Fahrbarkeit – und damit über jede Zahl, die danach kommt. Die vollständige Liste steht in Restriktionen in der Tourenplanung.
• Die Distanz- und Zeitmatrix. Jedes Verfahren optimiert gegen die Matrix, die es bekommt. Ist sie Luftlinie statt Wegenetz, oder generisches Pkw-Routing statt Lkw-Profil, optimiert der Solver sauber auf eine falsche Wirklichkeit. Dazu Routing- und Optimierungs-API und Custom Routing.
• Die Zielfunktion. Kilometer, Zeit, Maut, CO₂ und Fahrerstunden zeigen nicht in dieselbe Richtung. Was gewichtet wird, ist eine betriebswirtschaftliche Entscheidung und keine mathematische. Was ein Kilometer aktuell kostet, rechnet der Lkw-Maut-Rechner aus.
• Die Datenqualität. Geschätzte Standzeiten und optimistische Fahrzeiten erzeugen Pläne, die im Rechner gewinnen und auf der Straße verlieren. Dazu Fahrzeit-Unsicherheit.

Drei Fragen für den Anbietertermin

• „Welches Verfahren läuft, und gegen welchen öffentlichen Benchmark ist es gemessen?“ Die Benchmarks sind offen. Wer die Frage nicht beantwortet, hat entweder nicht gemessen oder will die Zahl nicht nennen.
• „Was passiert, wenn eine Restriktion nicht erfüllbar ist?“ Gute Systeme zeigen, welche Nebenbedingung sie verletzen mussten und um wie viel. Schwache liefern stillschweigend einen Plan, der nicht fahrbar ist.
• „Wie lange rechnen Sie, und was ändert sich, wenn ich fünf Minuten mehr gebe?“ Die Antwort verrät, ob eine Metaheuristik läuft oder nur ein Konstruktionsverfahren mit Politur. Ein Verfahren, das von mehr Zeit nicht profitiert, hat keine Suche.

Wie eviit daraus ein Planungsmodell baut, beschreibt die Lösungsseite Tourenplanung & Logistikplanung; welche Bibliotheken und Lizenzen dahinterstehen, der Beitrag Solver im Vergleich. Und wie groß der Hebel in Ihrer eigenen Planung ist, beantwortet keine Verfahrensdiskussion, sondern der Tourenoptimierungs-Check auf vier Wochen Ihrer Ist-Daten.