„KI-gestützte Tourenoptimierung" steht inzwischen auf fast jedem Angebot. Die interessante Frage ist nicht, ob das stimmt, sondern wobei genau maschinelles Lernen etwas beiträgt. Darauf gibt es eine ungewöhnlich klare Antwort, weil es einen Wettbewerb gab, in dem beide Lager mit denselben echten Daten gegeneinander antraten.
Vorweg die wichtigste Unterscheidung: Es gibt zwei völlig verschiedene Anwendungen von maschinellem Lernen in der Tourenplanung, die regelmäßig vermischt werden. Erstens die Vorhersage von Fahrzeiten. Zweitens das Lösen des Tourenproblems selbst. Bei der einen funktioniert KI hervorragend, bei der anderen nicht.
Der Wettbewerb, der es entschieden hat
2022 richteten die europäische OR-Gesellschaft EURO und die KI-Konferenz NeurIPS gemeinsam einen Tourenplanungswettbewerb aus. Die Daten stammten von ORTEC – echte Speditionsdaten, kein akademisches Zufallsmuster. Über fünfzig Teams, dreizehn Wochen Zeit, zwei Aufgaben: eine statische Planung und eine dynamische Disposition über den Tag.
Der Bericht der Organisatoren formuliert das Gesamtergebnis so:
„While the OR community primarily relies on simplistic ML methods, the ML community generally uses deep learning, but fails to outperform OR baselines."
Und konkreter:
„most of them do not currently outperform state-of-the-art OR solution strategies, which are typically based on fast local searches with additional metaheuristic strategies."
Bei der statischen Planung gewann klassische Optimierung. Alle Spitzenteams setzten auf Varianten der Hybrid Genetic Search – ein Verfahren aus der Operations Research, kein neuronales Netz. Die eigenen ML-Referenzimplementierungen der Organisatoren schnitten nicht einmal besser ab als eine simple gierige Heuristik.
Aber – und das ist die zweite Hälfte, die selten mitzitiert wird:
„Compared to the static variant, very significant progress beyond the baseline strategies has been made for the dynamic variant of the problem. All the best approaches used machine learning as a key component of their winning policies."
Bei der dynamischen Disposition war maschinelles Lernen bei allen Gewinnern zentraler Bestandteil.
Das ist die ehrliche Trennlinie: Den Tagesplan am Morgen rechnet klassische Optimierung besser. Die Frage, was man mit einem um 10:40 Uhr eingehenden Auftrag macht – annehmen, ablehnen, warten –, beantwortet maschinelles Lernen besser.
Warum das so ist
Beim statischen Problem ist die Aufgabe vollständig bekannt und die Zielfunktion exakt auswertbar. Da gibt es nichts zu lernen; man muss suchen, und darin sind spezialisierte Verfahren nach sechzig Jahren Entwicklung sehr gut.
Beim dynamischen Problem muss man über die Zukunft entscheiden: Lohnt es, ein Fahrzeug in einem Gebiet zu halten, weil dort erfahrungsgemäß nachmittags Aufträge kommen? Das ist genau die Art von Frage, für die sich Muster aus historischen Daten lernen lassen.
Übrigens: Wer „dynamisch" liest, sollte prüfen, was gemeint ist. Eine Übersichtsarbeit von Psaraftis, Wen und Kontovas hat die Forschungsliteratur zum dynamischen Routing systematisch ausgewertet:
„Some 80% of the problems in the taxonomy involve the dynamic appearance of customers, some 10% involve dynamic travel times and some 3% consider vehicle breakdowns."
Achtzig Prozent der Arbeiten meinen neu eintreffende Aufträge, nur zehn Prozent veränderliche Fahrzeiten. Wer „dynamische Tourenplanung" kauft und Stauberücksichtigung erwartet, bekommt möglicherweise etwas anderes.
Was Umplanung tatsächlich bringt
Auch dazu gibt es belegte Zahlen statt Versprechen. Die Fachliteratur misst den „value of information" – die Lücke zwischen einem Plan, der die Aufträge des Tages erst nach und nach erfährt, und einem, der sie morgens alle kennt. Gendreau und Kollegen berichten für ihr Tabu-Search-Verfahren Werte zwischen 2,5 und 4,1 Prozent.
Für vorausschauendes Disponieren – das Fahrzeug wird bewusst in einem Gebiet gehalten, in dem Aufträge erwartet werden – haben Ichoua, Gendreau und Potvin gemessen: bei vier Fahrzeugen im Mittel 4,1 Prozent Verbesserung, bei sechs Fahrzeugen 2,3 Prozent. Ihre eigene Schlussfolgerung ist die für die Praxis wichtigste:
„This strategy is also more effective when it is applied on harder problems (i.e., smaller fleet size or higher request arrival rates)."
Vorausschau zahlt sich also besonders aus, wenn die Flotte knapp ist – also im heutigen Markt.
Fahrzeitprognose: hier wirkt ML wirklich
Der zweite Anwendungsfall ist der überzeugendere, und hier lässt sich die Größenordnung sauber belegen. Baidu hat für seinen Kartendienst veröffentlicht, wie sich die Genauigkeit von Ankunftszeitprognosen entwickelt hat. Für Peking:
- Historischer Durchschnitt als Ausgangswert: 41,25 Prozent mittlerer prozentualer Fehler
- Ein gelerntes Modell von 2020: 22,03 Prozent
- Das Nachfolgemodell von 2022: 21,22 Prozent
Das ist die ganze Geschichte in drei Zahlen. Der Schritt vom statischen Durchschnitt zu einem gelernten Modell halbiert den Fehler. Der Schritt vom guten zum neuesten Modell bringt 0,8 Prozentpunkte. Der erste Schritt ist das Geld, der zweite das Marketing.
Und die Kalibrierung, die man im Kopf behalten sollte: Selbst modernste städtische Fahrzeitprognosen liegen bei rund 20 bis 27 Prozent mittlerem Fehler. Wer Ihnen einstellige Werte für innerstädtische Zustellung verspricht, misst etwas anderes.
Ein Beispiel für den Unterschied zwischen Blog und Fachartikel
Google und DeepMind haben 2020 vermeldet, die Genauigkeit von Ankunftszeiten sei „um bis zu 50 Prozent" verbessert worden, unter anderem in Berlin. Im zugehörigen Fachartikel steht etwas anderes.
Die Kennzahl ist dort definiert als „relative reduction in negative ETA outcomes" – also die Verringerung des Anteils grob falscher Prognosen, wobei die Schwelle für „grob falsch" nirgends genannt wird. Der Wert für Berlin beträgt 21 Prozent, nicht 50. Die 50 stammen aus Taichung. Und die im selben Artikel ausgewiesene Verbesserung des mittleren quadratischen Fehlers gegenüber der Echtzeit-Basislinie liegt in New York bei 8,8 Prozent.
Das ist kein Vorwurf an die Forscher – deren Artikel ist sauber. Es ist eine Illustration dafür, wie aus einer differenzierten Messung eine runde Marketingzahl wird.
Die unbequeme Studie
Zum Abschluss ein Befund, der zur Vorsicht mahnt. Manibardo, Laña und Del Ser haben sechzehn Verfahren zur Verkehrsprognose systematisch verglichen – mit sauber abgestimmten Hyperparametern und einer naiven Basislinie. Ihr Ergebnis:
„the statistical analysis concludes that from the statistical point of view, there is no clear winner in the benchmark, nor any empirically supported reason for using Deep Learning based traffic forecasting models detrimentally to shallow modeling alternatives."
Und eine Beobachtung zur Publikationspraxis, die man sich merken sollte:
„A common practice observed in the literature is that test data are carefully chosen in order to obtain the desired performance for the presented traffic forecasting method."
Einschränkung: Das sind Verkehrsflussprognosen an festen Zählstellen, keine Routenfahrzeiten. Die Lehre über Basislinien überträgt sich, die Zahlen nicht.
Was Sie fragen sollten
Wenn ein Anbieter mit KI wirbt, führen drei Fragen schnell zur Sache:
- Wofür genau? Fahrzeitprognose oder Tourenbildung? Bei ersterem ist ML klar überlegen, bei letzterem – statisch – nicht.
- Gegen welche Basislinie gemessen? Der Größenvorteil hängt fast vollständig davon ab, wogegen verglichen wird. Gegen einen Klassendurchschnitt sind es zwei Drittel, gegen ein historisches Profil rund die Hälfte, gegen eine gute Routing-Engine deutlich weniger.
- Auf welchen Daten? Ein Verfahren, das auf gleichmäßig verteilten Zufallspunkten glänzt, hat mit einem Liefergebiet mit Clustern, Zeitfenstern und Fahrzeugprofilen wenig zu tun.
Es gibt sogar eine Fachpublikation, die genau wegen dieses Problems geschrieben wurde: Accorsi, Lodi und Vigo haben Richtlinien für die rechnerische Prüfung von ML-Verfahren in der Tourenplanung veröffentlicht, weil ML-Arbeiten regelmäßig gegen schlecht eingestellte OR-Verfahren antreten.
Unsere Einordnung
Wir setzen maschinelles Lernen dort ein, wo es belegt trägt – vor allem bei Fahrzeiten aus Telematikdaten. Die Tourenbildung selbst rechnen wir mit klassischen Optimierungsverfahren, weil die dafür nachweislich besser sind. Das ist keine Technologieskepsis, sondern das Ergebnis eines Wettbewerbs mit echten Daten.
Welche Verfahren dabei zum Einsatz kommen, steht im Beitrag zu den Metaheuristiken. Warum ein Plan auf Durchschnittsfahrzeiten teuer wird, rechnet der Beitrag zu unsicheren Fahrzeiten durch.
Die vollständige Einordnung, was Lernverfahren in der Tourenoptimierung beitragen – samt der Zahlen zum Amazon-Wettbewerb und zu Sprachmodellen als Optimierern –, steht im Leitfaden Tourenoptimierung mit KI. Welche Verfahren stattdessen die Arbeit machen und was sie realistisch bringen, ordnet der Leitfaden zur Tourenoptimierung ein. Wer prüft, ob ein Produkt oder ein eigenes Modell zur eigenen Planung passt, findet die Entscheidungshilfe unter Tourenplanung Software.
Quellen
- Kool, W.; Bliek, L.; Numeroso, D.; Zhang, Y.; Catshoek, T.; Tierney, K.; Vidal, T.; Gromicho, J. (2023): The EURO Meets NeurIPS 2022 Vehicle Routing Competition. PMLR 220, S. 35–49. proceedings.mlr.press
- Psaraftis, H. N.; Wen, M.; Kontovas, C. A. (2016): Dynamic vehicle routing problems: Three decades and counting. Networks 67(1), S. 3–31. doi.org/10.1002/net.21628
- Gendreau, M.; Guertin, F.; Potvin, J.-Y.; Taillard, É. (1999): Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching. Transportation Science 33(4), S. 381–390. doi.org/10.1287/trsc.33.4.381
- Ichoua, S.; Gendreau, M.; Potvin, J.-Y. (2006): Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching. Transportation Science 40(2), S. 211–225. doi.org/10.1287/trsc.1050.0114
- Huang, J. u. a. (2022): DuETA: Traffic Congestion Propagation Pattern Modeling … at Baidu Maps. CIKM '22, S. 3172–3181. doi.org/10.1145/3511808.3557091
- Derrow-Pinion, A. u. a. (2021): ETA Prediction with Graph Neural Networks in Google Maps. CIKM '21, S. 3767–3776. doi.org/10.1145/3459637.3481916
- Manibardo, E. L.; Laña, I.; Del Ser, J. (2022): Deep Learning for Road Traffic Forecasting: Does it Make a Difference? IEEE T-ITS 23(7), S. 6164–6188. doi.org/10.1109/TITS.2021.3083957
- Liu, S.; Zhang, Y.; Tang, K.; Yao, X. (2023): How Good Is Neural Combinatorial Optimization? IEEE Computational Intelligence Magazine 18(3), S. 14–28. doi.org/10.1109/MCI.2023.3277768
- Accorsi, L.; Lodi, A.; Vigo, D. (2022): Guidelines for the computational testing of machine learning approaches to vehicle routing problems. Operations Research Letters 50(2), S. 229–234. doi.org/10.1016/j.orl.2022.01.018