Zustellsysteme auf der letzten Meile operieren in einer Welt, die selten stillsteht. Bestellungen treffen ein, während die Lastwagen bereits unterwegs sind, Verkehrsbedingungen ändern sich und Zeitfenster für die Zustellung sind oft eng gesteckt. In diesem Umfeld ist ein statischer Plan – eine Route, die einmal zu Beginn des Tages berechnet wurde – selten ausreichend. Stattdessen müssen Disponenten ihre Pläne ständig aktualisieren, indem sie neue Stopps in bestehende Routen einfügen oder diese umplanen, wenn ein Kunde storniert oder ein Fahrzeug ausfällt. Diese ständige Notwendigkeit zur Neuoptimierung schafft eine schwierige rechnerische Herausforderung: Das System muss in wenigen Sekunden eine neue, gültige Anordnung von Stopps finden. Wenn der Computer zu lange zum Nachdenken braucht, schließt sich das Zeitfenster für die Lieferung oder der Fahrer wartet untätig. Wenn der Computer eine neue Route vorschlägt, die gegen Regeln verstößt – etwa wenn ein Lkw zu schwer beladen ist oder zu spät ankommt –, bricht der gesamte Plan zusammen und das System muss von vorne beginnen. Das Ziel ist nicht nur, den kürzesten Pfad zu finden, sondern einen praktikablen Pfad, und zwar sofort.

Forscher der Hubei University of Automotive Technology haben einen neuen Ansatz für dieses Problem entwickelt, der eine Strategie aus der Welt der künstlichen Intelligenz nutzt, um diese blitzschnellen Entscheidungen zuverlässiger zu machen. Sie nennen ihr System SRI-ECR-balanced. Anstatt zu versuchen, jedes Mal, wenn eine neue Bestellung eingeht, die perfekte Route von Grund auf neu zu berechnen, arbeitet das System wie ein geschickter Editor, der ein paar Sätze entwirft, sie auf Fehler prüft, die guten Teile behält und die schlechten sofort korrigiert. Diese Methode, bekannt als spekulative Ausführung (Speculative Execution), ermöglicht es dem System, mehrere zukünftige Stopps gleichzeitig vorzuschlagen, zu verifizieren, welche sicher sind, und den Rest zu verwerfen, bevor sie ein Problem verursachen. Durch dies kann das System Konflikte viel schneller bewältigen als traditionelle Methoden und sicherstellen, dass ein Lieferplan auch dann machbar bleibt, wenn sich die Situation vor Ort schnell ändert.

Der Kern dieses neuen Frameworks ist ein Zyklus aus Entwurf, Verifizierung und Reparatur. Wenn eine neue Bestellung eingeht, schlägt ein „Entwurfsgenerator“ eine kurze Sequenz von Kunden vor, die zu der Route eines Lastwagens hinzugefügt werden sollen. In der Vergangenheit versuchten Systeme vielleicht, nur einen Kunden nach dem anderen einzufügen, was langsam ist, oder sie versuchten, eine lange Liste von Kunden auf einmal einzufügen, was oft zu Fehlern führt. Dieses neue System trifft ein Gleichgewicht: Es schlägt eine kleine Gruppe von Stopps vor, vielleicht fünf auf einmal. Ein separater „Verifizierer“ prüft diese Gruppe dann gegen die Regeln der Straße, wie etwa das Gewichtslimit des Lastwagens und das Zeitfenster des Kunden. Das System akzeptiert den längsten Abschnitt der vorgeschlagenen Gruppe, der den Regeln entspricht, und verwirft den Rest sofort. Wenn die ersten drei Stopps der vorgeschlagenen Gruppe in Ordnung sind, aber der vierte zu schwer für den Lastwagen ist, behält das System die ersten drei und macht beim vierten einen Rückschritt (Rollback). Es wirft nicht den gesamten Plan weg; es entfernt nur den Teil, der gegen die Regeln verstieß.

Soben die ungültigen Stopps zurückgesetzt wurden, tritt ein spezialisierter „Reparatur-Experte“ ein, um das Problem zu lösen. Dies ist kein generischer Fixer; das System diagnostiziert genau, was schiefgelaufen ist. Wenn das Problem darin besteht, dass der Lastwagen zu voll ist, priorisiert der Experte die Suche nach einem anderen Lastwagen mit mehr Platz. Wenn das Problem darin besteht, dass ein Kunde aufgrund eines engen Zeitfensters nicht erreicht wird, sucht der Experte nach einer Route, die früher ankommen kann. Dieser gezielte Ansatz ist entscheidend. Die Forscher fanden heraus, dass das System ohne diesen spezifischen, konfliktbewussten Reparatur-Schritt in Stresssituationen keine gültigen Routen finden konnte. Wenn das System gezwungen war, eine zufällige Reparaturmethode anstelle einer Expertenmethode zu verwenden, konnte es nur etwa ein Drittel der Probleme beheben, wodurch viele Bestellungen unbedient blieben. Mit dem Experten-Router konnte das System in ihren Tests jeden einzelnen Konflikt erfolgreich reparieren und so eine perfekte Bilanz an machbaren Plänen vorweisen.

Um diesen Prozess für den Echtzeitgebrauch schnell genug zu machen, verwendet das System auch eine Form von Speicher, den sogenannten „Route-Prefix-Cache“. In einer dynamischen Umgebung bleibt der Großteil der Route eines Lastwagens von einem Moment zum nächsten gleich; nur das Ende der Route ändert sich. Traditionelle Systeme berechnen oft die gesamte Reise neu, wann immer sie eine kleine Änderung vornehmen, und verschwenden dabei Zeit für Teile der Fahrt, die sich nicht geändert haben. Dieses neue System merkt sich die Berechnungen für die Teile der Route, die bereits bestätigt sind. Wenn es einen neuen Stopp prüfen muss, berechnet es nur den neuen Teil und nutzt die gespeicherten Daten für den Rest wieder. Dieser einfache Trick machte das System beim Evaluieren potenzieller Routen mehr als dreimal schneller. In Tests mit einem Standarddatensatz von 100 Kunden ermöglichte dieses Caching dem System, Routen 3,12-mal schneller zu evaluieren, als wenn es bei Null anfangen müsste. Bei einem größeren Test mit 200 Kunden betrug die Beschleunigung das 3,08-fache.

Die Forscher testeten ihr System gegen bestehende Werkzeuge, die in der Logistikbranche eingesetzt werden, darunter OR-Tools und PyVRP, welche leistungsstarke Solver sind, die darauf ausgelegt sind, die absolut kürzesten Routen zu finden. Sie führten Simulationen durch, in denen ständig neue Bestellungen eintrafen und in denen Zeitfenster künstlich eng gesetzt wurden, um Stress zu erzeugen. Unter diesen schwierigen Bedingungen benötigten die traditionellen Solver fast die vollen drei Sekunden, die für jede Entscheidung vorgesehen waren, um eine Lösung zu finden, und selbst dann produzierten sie manchmal Routen, die zwar etwas kürzer waren, aber eine längere Rechenzeit beanspruchten. Das neue System hingegen fand eine gültige Lösung in durchschnittlich weniger als einer halben Sekunde. Während die von ihm erzeugten Routen in der Gesamtdistanz etwa 7,8 % länger waren als die der leistungsstarken Solver, war dieser Kompromiss beabsichtigt. In einem realen Liefer-Szenario ist eine etwas längere Route, die sofort bereit ist, oft wertvoller als eine perfekte Route, die zu spät kommt. Das System priorisierte es, einen praktikablen Plan auf den Weg zu bringen, anstatt jeden letzten Kilometer an Effizienz herauszukitzeln.

Die Studie untersuchte auch, wie sich das System unter verschiedenen Risikoniveaus verhält. Sie verglichen einen „balancierten“ Ansatz, der das Risiko beim Hinzufügen eines neuen Stopps sorgfältig abwägt, mit einem „aggressiven“ Ansatz, der versucht, so viele Stopps wie möglich hinzuzufügen, bevor geprüft wird. Die aggressive Methode führte dazu, dass das System viele Fehler machte, die zurückgesetzt werden mussten, was es erheblich verlangsamte. Der balancierte Ansatz, der riskante Bewegungen bereits vor deren Vorschlag sanktioniert, reduzierte die Anzahl der Fehler und hielt das System reibungslos in Bewegung. Dies bestätigte, dass das System am besten arbeitet, wenn es mit Vorsicht spekuliert, also einige Schritte voraus plant, sie aber rigoros prüft, bevor es sich festlegt.

Die Forscher behaupteten nicht, dass ihr System das beste darin sei, die kürzestmögliche Route in einer statischen Welt zu finden, in der Zeit keine Rolle spielt. Sie stellten explizit klar, dass für Probleme, bei denen das einzige Ziel die Minimierung der Distanz ist und der Computer mehrere Sekunden Zeit zum Nachdenken hat, die traditionellen Solver weiterhin gewinnen. Der Wert dieses neuen Frameworks liegt spezifisch in der chaotischen, zeitlich unter Druck stehenden Welt der dynamischen Disposition. In diesen Szenarien ist die Fähigkeit, einen Konflikt sofort zu beheben und einen gültigen Plan aufrechtzuerhalten, wichtiger als eine marginale Verbesserung der Distanz. Das System bewies seinen Wert, indem es in den stressigsten Test-Szenarien 100 % der Kunden bediente, mit null abgelehnten Bestellungen, während es die Antwortzeit niedrig genug hielt, um für ein Live-Dispositionszentrum nutzbar zu sein.

Selbst als die Forscher zufälliges Rauschen einführten, um unvorhersehbare Verkehrsverzögerungen zu simulieren, hielt das System stand. Es bediente weiterhin alle Kunden und reparierte Konflikte erfolgreich, was zeigt, dass die Methode robust genug ist, um reale Unsicherheiten zu handhaben. Sie testeten das System auch mit einem Ausschnitt echter Lieferdaten eines großen Logistikunternehmens unter Verwendung tatsächlicher Lieferkoordinaten. Das System lief erfolgreich mit diesen realen Daten und bediente alle 80 Stopps des Testsets. Die Forscher wiesen jedoch vorsichtig auf die Grenzen ihres aktuellen Designs hin. Als sie ein viel größeres Szenario mit 400 Kunden testeten, konnte das System innerhalb des Zeitlimits keine perfekte Lösung finden und bediente nur etwa drei Viertel der Bestellungen. Dies deutet darauf hin, dass die Methode zwar gut für mittelgroße Flotten funktioniert, größere Operationen jedoch zusätzliche Strategien benötigen, um das Problem in kleinere Teile zu zerlegen.

Letztendlich demonstriert diese Arbeit einen Wandel in der Art und Weise, wie wir Routing-Probleme betrachten. Anstatt den Computer als einen Rechner zu sehen, der die eine beste Antwort finden muss, behandelten die Forscher ihn als einen Entscheidungsträger, der schnell eine gute Antwort finden muss. Durch die Übernahme der spekulativen Muster, die in der modernen künstlichen Intelligenz verwendet werden – Entwerfen, Verifizieren und Caching –, kann das System die Unsicherheit der dynamischen Lieferung mit Geschwindigkeit und Zuverlässigkeit navigieren. Die Ergebnisse legen nahe, dass für viele reale Logistikherausforderungen die Fähigkeit, sich sofort anzupassen, das wahre Maß für ein erfolgreiches System ist, selbst wenn dies bedeutet, dass die Routen mathematisch nicht perfekt sind. Das System verspricht nicht, alle Verzögerungen zu eliminieren oder jedes Mal den kürzesten Pfad zu finden, aber es verspricht, dass bei einer neuen Bestellung fast sofort ein Plan bereitsteht, um das Rad des Liefernetzwerks am Laufen zu halten.