„Unsere KI optimiert Ihre Touren." Der Satz steht auf vielen Websites und sagt nichts. Was tatsächlich rechnet, sind Verfahren mit Namen wie Tabu Search oder Large Neighborhood Search – sämtlich älter als der aktuelle KI-Zyklus, sämtlich gut dokumentiert und sämtlich mit veröffentlichten Leistungsdaten. Wer sie kennt, kann Anbieter besser bewerten.
Alle vier folgen demselben Grundgedanken: Eine gute Lösung findet man nicht, indem man immer nur bergauf geht. Man muss zwischendurch schlechter werden dürfen.
Warum reine Verbesserung nicht funktioniert
Ein einfacher Optimierer nimmt einen Plan und probiert kleine Änderungen: zwei Stopps tauschen, einen Stopp auf eine andere Tour verschieben. Wird der Plan besser, behält man die Änderung. Das nennt sich lokale Suche und endet zuverlässig in einer Sackgasse – einem lokalen Optimum, in dem jede einzelne Änderung verschlechtert, obwohl anderswo deutlich bessere Pläne liegen.
Alle folgenden Verfahren lösen genau dieses Problem, jedes auf eigene Art.
Tabu Search: Verbotene Rückschritte
Fred Glover prägte den Begriff 1986. Die Idee: Man geht immer zum besten Nachbarn, auch wenn er schlechter ist als der aktuelle Stand. Damit die Suche nicht sofort zurückspringt, führt man eine „Tabu-Liste" der zuletzt rückgängig gemachten Züge – diese dürfen für einige Runden nicht wiederholt werden. Das Verbot ist der Motor: Es zwingt die Suche, das Tal zu verlassen.
Für die Tourenplanung ist die Referenz TABUROUTE von Gendreau, Hertz und Laporte (1994). Im Abstract steht ein Detail, das Praktiker regelmäßig überrascht:
„During the course of the algorithm, infeasible solutions are allowed."
Der Optimierer arbeitet also zeitweise mit Plänen, die Kapazitäten verletzen. Nur so kommt er von einer zulässigen Lösung zur nächsten besseren. Am Ende steht wieder ein zulässiger Plan – der Weg dorthin führt aber durch unzulässiges Gelände.
Simulated Annealing: Kontrolliertes Abkühlen
Kirkpatrick, Gelatt und Vecchi übertrugen 1983 ein Verfahren aus der Metallurgie auf Optimierungsprobleme. Man akzeptiert eine Verschlechterung mit einer Wahrscheinlichkeit, die anfangs hoch ist und nach einem festen Plan sinkt. Früh in der Suche springt der Algorithmus wild umher, spät verhält er sich wie eine reine Verbesserungssuche.
Der Vergleich mit dem Abkühlen von Metall ist nicht bloß Bildsprache – die Formel stammt tatsächlich aus der statistischen Physik. Wichtig zu wissen: Simulated Annealing ist kein Tourenplanungsverfahren, sondern ein allgemeines Prinzip, das auf beliebige Optimierungsprobleme angewendet wird.
Large Neighborhood Search: Abreißen und neu bauen
Das für die Tourenplanung heute wichtigste Verfahren geht auf Paul Shaw (1998) zurück und wurde von Ropke und Pisinger (2006) zur Adaptive Large Neighborhood Search weiterentwickelt.
Die Idee bricht mit der lokalen Suche: Statt einzelne Stopps zu tauschen, reißt man zehn bis vierzig Prozent aller Stopps aus dem Plan heraus – nach Verwandtschaft, nach Kosten oder zufällig – und fügt sie anschließend wieder ein. Das ist ein riesiger Suchschritt, der Plankonfigurationen erreicht, die durch Einzeltausche nie entstanden wären.
Das „adaptive" bezieht sich darauf, dass mehrere Abriss- und Einfügeregeln miteinander konkurrieren. Der Algorithmus führt Buch, welche zuletzt erfolgreich waren, und wählt diese häufiger. Aus dem Abstract:
„The heuristic is tested on more than 350 benchmark instances with up to 500 requests. It is able to improve the best known solutions from the literature for more than 50% of the problems."
Bemerkenswert: Die Autoren kombinieren ALNS mit einem Simulated-Annealing-Akzeptanzkriterium. Diese Verfahren sind keine Konkurrenten, sie werden gestapelt.
In einer Folgearbeit lösten Pisinger und Ropke mit einem einzigen vereinheitlichten Modell fünf verschiedene VRP-Varianten und verbesserten dabei 183 von 486 Bestwerten. Für die Praxis relevant ist ihre eigene Begründung: Das vereinheitlichte Modell erlaube es dem Disponenten, verschiedene Problemvarianten für einzelne Kunden oder Fahrzeuge zu mischen. Genau das braucht man im Alltag.
Guided Local Search: Die Landkarte verbiegen
Voudouris und Tsang (1999) verfolgen einen anderen Ansatz. Wenn die Suche feststeckt, ändern sie nicht die Suche – sie ändern die Bewertung. Merkmale der festgefahrenen Lösung, etwa besonders lange Einzelstrecken, bekommen einen Strafaufschlag. Damit erscheint die aktuelle Lösung teuer, und die Suche wandert von selbst weiter. Die echten Entfernungen bleiben unangetastet; nur die interne Zielfunktion wird verzerrt.
Das klingt akademisch, ist aber kommerziell hoch relevant: Guided Local Search ist die von Google OR-Tools empfohlene Standardeinstellung. Im Quellcode steht dazu, dies sei „generally the most efficient metaheuristic for vehicle routing".
Was in den offenen Werkzeugen wirklich steckt
Wer OR-Tools einsetzt, hat genau fünf Metaheuristiken zur Auswahl, plus eine Automatik: Greedy Descent, Guided Local Search, Simulated Annealing, Tabu Search und Generic Tabu Search. Eine eigenständige ALNS-Metaheuristik ist nicht darunter – LNS existiert dort nur als Ebene innerhalb der lokalen Suche.
Zwei Punkte, die in Projekten regelmäßig für Überraschungen sorgen:
- Das Standard-Zeitlimit ist praktisch unendlich. Die Metaheuristiken beenden sich nicht von selbst; wer kein Limit setzt, wartet.
- OR-Tools rechnet keine Entfernungen. Die Distanzmatrix beziehungsweise die Fahrzeitfunktion muss man selbst beisteuern – aus OSRM, Valhalla oder einem eigenen Netz.
Google selbst formuliert die Grenze in der Dokumentation deutlich:
„For sufficiently large problems, it could take OR-Tools (or any other routing software) years to find the optimal solution. As a result, OR-Tools sometimes returns solutions that are good, but not optimal."
Eine Optimalitätsgarantie gibt es in der Routing-Dokumentation an keiner Stelle.
Die Warnung der Forschung an sich selbst
Zum Schluss ein Punkt, der bei der Anbieterauswahl hilft. Kenneth Sörensen hat 2015 einen vielbeachteten Aufsatz mit dem Titel „Metaheuristics – the metaphor exposed" veröffentlicht. Aus dem Abstract:
„the field of combinatorial optimization has witnessed a true tsunami of 'novel' metaheuristic methods, most of them based on a metaphor […] this line of research is threatening to lead the area of metaheuristics away from scientific rigor."
Gemeint sind Verfahren, die sich nach Ameisen, Bienen, Wölfen oder Harmonien benennen und deren Neuheitswert oft in der Metapher liegt, nicht im Algorithmus. 2022 folgte ein gemeinsamer Aufruf mehrerer führender Forscher unter dem Titel „the elephant in the room".
Noch aufschlussreicher ist eine zweite Arbeit von Sörensen und Kollegen: Sie implementierten einen publizierten „verbesserten Clarke-and-Wright-Algorithmus" nach und zeigten, dass die veröffentlichten Ergebnisse mit dem beschriebenen Verfahren gar nicht hätten entstehen können. Die Arbeit hatte ein Peer-Review in einer gelisteten Zeitschrift durchlaufen.
Die Konsequenz für die Praxis: Wenn schon in begutachteten Fachartikeln Leistungsangaben stehen, die sich nicht reproduzieren lassen, dann verdient eine Prozentzahl in einer Verkaufsunterlage erst recht eine Rückfrage. Die richtige lautet: Auf welchen Instanzen, gegen welche Baseline, in welcher Rechenzeit?
Was Sie daraus mitnehmen
- Metaheuristiken sind kein Marketingbegriff, sondern eine überschaubare Zahl gut dokumentierter Verfahren aus den Jahren 1983 bis 2006.
- Sie werden kombiniert, nicht gegeneinander ausgespielt – ALNS mit SA-Akzeptanz ist der Normalfall.
- Die offenen Werkzeuge sind ausgereift, aber sie brauchen ein Zeitlimit und ein Wegenetz, das jemand beisteuern muss.
- Leistungsangaben ohne Angabe von Instanz, Baseline und Rechenzeit sind wertlos.
Warum ein Verfahren, das auf Benchmarks glänzt, im Betrieb trotzdem unbrauchbare Pläne liefern kann, ist ein eigenes Thema – wir haben es hier auseinandergenommen.
Wo diese Verfahren im Gesamtbild stehen – neben Konstruktionsheuristiken und exakten Verfahren –, ordnet der Überblick Verfahren der Tourenoptimierung ein; was sie auf echten Daten liefern, der Leitfaden zur Tourenoptimierung. Wer sie selbst betreiben will, findet die Bausteine und ihre Kosten unter Routing- und Optimierungs-API.
Quellen
- Glover, F. (1986): Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5), S. 533–549. doi.org/10.1016/0305-0548(86)90048-1
- Gendreau, M.; Hertz, A.; Laporte, G. (1994): A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science 40(10), S. 1276–1290. doi.org/10.1287/mnsc.40.10.1276
- Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P. (1983): Optimization by Simulated Annealing. Science 220(4598), S. 671–680. doi.org/10.1126/science.220.4598.671
- Shaw, P. (1998): Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. CP98, LNCS 1520, S. 417–431. doi.org/10.1007/3-540-49481-2_30
- Ropke, S.; Pisinger, D. (2006): An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science 40(4), S. 455–472. doi.org/10.1287/trsc.1050.0135
- Pisinger, D.; Ropke, S. (2007): A general heuristic for vehicle routing problems. Computers & Operations Research 34(8), S. 2403–2435. doi.org/10.1016/j.cor.2005.09.012
- Voudouris, C.; Tsang, E. (1999): Guided local search and its application to the traveling salesman problem. EJOR 113(2), S. 469–499. doi.org/10.1016/S0377-2217(98)00099-X
- Sörensen, K. (2015): Metaheuristics – the metaphor exposed. International Transactions in Operational Research 22(1), S. 3–18. doi.org/10.1111/itor.12001
- Sörensen, K.; Arnold, F.; Palhazi Cuervo, D. (2019): A critical analysis of the „improved Clarke and Wright savings algorithm". ITOR 26(1), S. 54–63. doi.org/10.1111/itor.12443