Tourenoptimierung mit KI: was Lernverfahren wirklich beitragen.

Was im Markt „KI-Tourenoptimierung“ heißt

Wer heute nach Tourenoptimierung und KI sucht, findet fast ausschließlich Produktseiten. Sie versprechen intelligente Disposition, lernende Planung, KI-basierte Optimierung – und erklären in der Regel nicht, welche Größe eigentlich gelernt wird. Das ist bequem, weil unter dasselbe Etikett drei völlig verschiedene Dinge passen:

• Klassische Optimierung, neu beschriftet. Metaheuristiken wie Guided Local Search oder Ruin-and-Recreate lösen Tourenprobleme seit Jahrzehnten. Sie sind exzellent – aber sie lernen nichts. Wenn ein Anbieter „KI“ sagt und einen Solver meint, ist das Marketing, kein Betrug.
• Maschinelles Lernen auf den Eingangsgrößen. Fahrzeiten, Servicezeiten, Auftragsmengen, Fahrerverhalten: alles Vorhersageaufgaben, alles messbar besser mit gelernten Modellen. Hier steckt der belegbare Nutzen.
• Große Sprachmodelle. Sie schreiben Texte, fassen zusammen, erklären Pläne. Als Optimierer brechen sie bei realistischer Größe ein – mit Zahlen, die weiter unten stehen.

Die Frage „nutzt Ihr Anbieter KI?“ ist deshalb wertlos. Die brauchbare Frage lautet: Welche Größe wird gelernt, aus welchen Daten, und wer trifft am Ende die Entscheidung?

Die Tourenentscheidung ist Kombinatorik, keine Vorhersage

Eine Tour zu bilden heißt: Aufträge auf Fahrzeuge verteilen und in eine Reihenfolge bringen, so dass Kapazitäten, Zeitfenster, Lenkzeiten und Wegerestriktionen eingehalten werden und die Kosten minimal sind. Das ist das Vehicle Routing Problem – ein Optimierungsproblem mit harten Nebenbedingungen, dessen Lösungsraum mit der Stoppzahl fakultativ wächst. Was dahintersteckt, steht ausführlich in Tourenoptimierung: Definition, Verfahren, realistische Effekte.

Der entscheidende Unterschied zur Mustererkennung: Ein gelerntes Modell gibt eine wahrscheinliche Antwort. Eine Tourenplanung braucht eine zulässige. Ein neuronales Netz kann mit hoher Zuversicht eine Tour ausgeben, die das Rampenfenster reißt oder das zulässige Gesamtgewicht überschreitet – und es gibt keinen Mechanismus, der das verhindert. Solver garantieren Zulässigkeit konstruktiv. Deshalb sitzt in praktisch jedem produktiven System am Ende ein Solver, unabhängig davon, was auf der Website steht.

Was der Amazon-Wettbewerb 2021 gezeigt hat

Der bislang aussagekräftigste Test dieser Frage war die Amazon Last Mile Routing Research Challenge, ausgeschrieben 2021 mit Unterstützung des MIT Center for Transportation & Logistics. Amazon veröffentlichte 6.112 real gefahrene Zustelltouren aus 17 Depots und stellte eine ungewöhnlich offene Aufgabe: Erfahrene Fahrer weichen systematisch von den optimierten Routen des Systems ab, weil sie Dinge wissen, die im Modell fehlen. Teilnehmer sollten dieses stille Wissen einfangen – ausdrücklich mit „artificial intelligence, machine learning, deep learning, computer vision“, ausdrücklich um klassische Operations-Research-Methoden zu übertreffen.1

Den Hauptpreis von 100.000 US-Dollar gewann kein neuronales Netz. Gewonnen hat ein Verfahren von William Cook, Stephan Held und Keld Helsgaun: eine penalty-basierte lokale Suche, die den klassischen TSP-Löser LKH um Vehicle-Routing-Restriktionen erweitert. Gelernt wurde trotzdem – aber an einer anderen Stelle: Die Kombinationen von Restriktionen, die eine Lösung „fahrerähnlich“ machen, leiteten die Autoren aus der Analyse der historischen Tourdaten ab.2

Das ist die eigentliche Lehre des Wettbewerbs, und sie ist unbequem für beide Lager: Die Daten der Fahrer waren unverzichtbar. Der Solver war es auch. Was aus den Daten kam, war nicht die Route, sondern das Modell, gegen das gerechnet wurde.

Die zweite Bewährungsprobe: statisch gegen dynamisch

Ein Jahr später richteten die europäische OR-Gesellschaft EURO und die KI-Konferenz NeurIPS gemeinsam einen Tourenplanungswettbewerb aus, auf echten Speditionsdaten, mit über fünfzig Teams und zwei Aufgaben: einer statischen Tagesplanung und einer dynamischen Disposition über den Tag. Der Bericht der Organisatoren zieht eine Trennlinie, die schärfer ist als alles, was im Markt darüber gesagt wird.4

Bei der statischen Planung gewann klassische Optimierung: Alle Spitzenteams setzten auf Varianten der Hybrid Genetic Search, und die Deep-Learning-Referenzen der Organisatoren schlugen nicht einmal eine gierige Heuristik. Bei der dynamischen Variante war es umgekehrt – dort war maschinelles Lernen laut Bericht zentraler Bestandteil aller Gewinnerlösungen.

Der Grund liegt in der Natur der beiden Aufgaben. Bei der statischen Planung ist alles bekannt und die Zielfunktion exakt auswertbar – da gibt es nichts zu lernen, sondern zu suchen. Bei der dynamischen Disposition muss über die Zukunft entschieden werden: Lohnt es, ein Fahrzeug in einem Gebiet zu halten, in dem nachmittags erfahrungsgemäß Aufträge eintreffen? Genau dafür lassen sich Muster aus Historie lernen. Die Zahlen und Zitate dieses Wettbewerbs sind im Beitrag KI in der Tourenplanung: was heute funktioniert – und was nicht im Detail ausgewertet.

Wo Lernverfahren tatsächlich gewinnen: die Eingangsgrößen

Jede Tourenoptimierung rechnet gegen Annahmen. Wie lange braucht das Fahrzeug von A nach B? Wie lange steht es beim Kunden? Wie viel kommt morgen an Aufträgen? Diese Größen sind Vorhersagen – und genau dort ist maschinelles Lernen dem Erfahrungswert überlegen.

• Fahrzeit. Der bekannteste Beleg ist gleichzeitig das beste Beispiel dafür, wie man Zahlen liest. Google und DeepMind haben Ankunftszeiten mit Graph Neural Networks auf sogenannten Supersegments neu gerechnet und dafür „bis zu 50 %“ Verbesserung vermeldet.5 Gemessen wird dabei die Verringerung des Anteils grob falscher Prognosen, und der Wert gilt für Taichung; für Berlin sind es 21 %, und die Verbesserung des mittleren quadratischen Fehlers gegenüber der Echtzeit-Basislinie liegt in New York bei 8,8 %. Der Effekt ist echt und lohnend – nur eben kleiner als die runde Zahl. Wo der eigentliche Sprung liegt, zeigt der Vergleich im Beitrag KI in der Tourenplanung: vom historischen Durchschnitt zu einem gelernten Modell halbiert sich der Fehler, vom guten zum neuesten Modell kommen Bruchteile eines Prozentpunkts dazu.
• Servicezeit je Kunde. In der Praxis der größte stille Fehler: Pauschal zehn Minuten je Stopp sind bei einer Rampe falsch und bei einem Hinterhof erst recht. Aus Telematik- und Auftragsdaten lässt sich die Standzeit je Kunde und Tageszeit schätzen.
• Reihenfolgeverhalten der Fahrer. Eine 2023 in The Innovation veröffentlichte Arbeit hat die Zonenreihenfolge realer Amazon-Touren mit einem Word2Vec-Modell gelernt und nur innerhalb jeder Zone klassisch als TSP optimiert. Dieses hybride Verfahren schlug die reine Optimierung sowohl im mittleren Fehler als auch in der Streuung und war deutlich schneller.6 Bemerkenswert: Das „Sprachmodell“ dort ist Word2Vec, kein Chatbot.
• Auftrags- und Mengenprognose. Wer weiß, wie das Auftragsvolumen morgen aussieht, plant Fahrzeuge und Personal vor – statt jeden Morgen zu reagieren.

Alle vier Punkte haben eine gemeinsame Eigenschaft: Sie verbessern die Qualität des Modells. Und ein Optimierer ist immer nur so gut wie das Modell, gegen das er rechnet. Welche Restriktionen in dieses Modell gehören, listet Restriktionen in der Tourenplanung vollständig auf.

Warum ein Sprachmodell keine Touren plant

Seit Sprachmodelle alltäglich sind, liegt die Frage nahe, ob man ihnen die Disposition gleich mitgeben kann. Dazu gibt es Messwerte. In der Arbeit zu „Large Language Models as Optimizers“ wurden text-bison, GPT-3.5-turbo und GPT-4 auf Rundreiseprobleme unterschiedlicher Größe gesetzt. Das Ergebnis ist eindeutig – und es ist keine Frage der Modellgeneration, sondern der Problemgröße:3

• 10 Stopps: alle getesteten Modelle finden die optimale Lösung.
• 15 Stopps: Abweichung 0,2 % bis 4,4 %.
• 20 Stopps: Abweichung 1,4 % bis 30,4 %.
• 50 Stopps: Abweichung 11 % beim besten Modell, bis 219,8 % beim schwächsten – während klassische Konstruktionsheuristiken im Vergleich zwischen 0,2 % und 9,8 % blieben.

Die Autoren selbst schreiben, ihr Verfahren sei nicht dafür gedacht, spezialisierte Solver bei klassischen kombinatorischen Problemen zu schlagen, und dass die Leistung bei größeren Instanzen dramatisch einbricht. Man muss das nüchtern einordnen: 50 Stopps sind kein Grenzfall, sondern ein normaler Zustelltag. Ein Sprachmodell ist ein hervorragendes Werkzeug, um einen Tourenplan zu erklären, eine Ausnahme zu dokumentieren oder eine Disponentenfrage in eine Abfrage zu übersetzen. Es ist kein Optimierer.

Vier Fragen, die ein KI-Versprechen prüfen

Diese vier Fragen kosten zehn Minuten im Anbietertermin und trennen belegbare Verfahren von Etiketten:

• Welche Größe lernt Ihr Modell konkret – Fahrzeit, Servicezeit, Menge, Reihenfolge? Und aus welchen Daten: aus unseren oder aus fremden?
• Trifft die Tourenentscheidung ein Solver oder ein gelerntes Modell? Falls Letzteres: Wodurch ist garantiert, dass eine ausgegebene Tour zulässig ist?
• Was passiert mit einer harten Restriktion, die in Ihrem Modell nicht vorgesehen ist – wird sie verletzt, oder wird der Auftrag als unplanbar ausgewiesen?
• Wogegen wird die Einsparung gemessen: gegen unseren tatsächlichen Ist-Plan oder gegen ein rechnerisches Optimum ohne unsere Regeln?

Die letzte Frage ist die teuerste. Eine Optimierung gegen ein freies Optimum liefert regelmäßig zweistellige Prozentwerte, die verschwinden, sobald Rampenzeiten, Fahrerregeln und Temperaturzonen dazukommen. Wie groß der Unterschied ausfällt, ist in Manuelle vs. dynamische Tourenplanung an einem Beispiel nachgerechnet.

Wie eviit die Aufgabe teilt

Unsere Arbeitsteilung folgt genau der Trennlinie dieses Textes. Auf der Datenseite arbeiten Lernverfahren: Fahrzeit- und Servicezeitmodelle aus Ihren Telematik- und Auftragsdaten statt Pauschalen, Mengenprognosen, wo Historie vorliegt. Auf der Entscheidungsseite arbeiten etablierte Optimierungsverfahren gegen ein Modell Ihres Betriebs, in dem Restriktionen hart sind – ein Plan, der eine Regel verletzt, wird nicht ausgegeben, sondern als nicht planbar markiert.

Das ist der Kern von Tourenplanung und Logistikplanung und, wo Wege und Fahrzeuge das Problem sind, von Custom Routing. Wo Lernverfahren jenseits der Tourenplanung sinnvoll sind, steht unter KI-Lösungen. Und wie diese Bausteine technisch zusammengesetzt werden – Routing-Engine, Solver, Distanzmatrix –, erklärt Routing- und Optimierungs-API.