Dynamic Vehicle Routing Problem with Prompt Confirmation of Advance Requests

Diese Arbeit stellt ein neues dynamisches Fahrzeugrouting-Verfahren vor, das durch die Kombination einer schnellen Einfügesuche für die sofortige Auftragsbestätigung und eines Reinforcement-Learning-gesteuerten Anytime-Algorithmus zur kontinuierlichen Routenoptimierung sowohl die Echtzeitbestätigung als auch die maximale Auslastung von Vorbestellungen in On-Demand-Verkehrsdiensten gewährleistet.

Amutheezan Sivagnanam, Ayan Mukhopadhyay, Samitha Samaranayake, Abhishek Dubey, Aron Laszka

Veröffentlicht 2026-03-10
📖 5 Min. Lesezeit🧠 Tiefgang

Each language version is independently generated for its own context, not a direct translation.

Stellen Sie sich vor, Sie leiten einen kleinen, aber sehr geschäftigen Busdienst in einer Stadt. Ihre Aufgabe ist es, Menschen von A nach B zu bringen. Das Problem ist: Die Leute rufen an, um eine Fahrt zu buchen, aber sie rufen zu unterschiedlichen Zeiten an. Manchmal rufen sie an, wenn der Bus gerade erst losfährt, manchmal rufen sie schon zwei Stunden vorher an.

Das ist wie ein riesiges, sich ständig veränderndes Puzzle. Und genau darum geht es in diesem wissenschaftlichen Papier. Die Forscher haben ein neues System entwickelt, das dieses Puzzle viel besser löst als die alten Methoden.

Hier ist die Geschichte ihres Systems, einfach erklärt:

1. Das große Dilemma: „Sofort antworten" vs. „Das Beste planen"

Stellen Sie sich vor, ein Kunde ruft an und fragt: „Können Sie mich in einer Stunde abholen?"

  • Der alte Weg (Methode A): Der Dispatcher sagt sofort: „Ja!" oder „Nein!". Aber sobald er „Ja" gesagt hat, ist die Entscheidung endgültig. Er darf den Bus nicht mehr umplanen, auch wenn später ein besserer Weg auftaucht. Das ist sicher für den Kunden, aber oft ineffizient für den Bus.
  • Der andere alte Weg (Methode B): Der Dispatcher sagt: „Warten Sie mal, ich plane gerade." Er wartet, bis alle Busse perfekt geplant sind, und gibt dann erst eine Antwort. Das ist super effizient für die Busse, aber der Kunde muss ewig warten und weiß nicht, ob er überhaupt eine Fahrt bekommt.

Das Problem: Bisher gab es keine Methode, die dem Kunden sofort eine Antwort gibt („Ja, wir holen Sie ab!") und dem Dispatcher gleichzeitig erlaubt, die Busse danach immer weiter zu optimieren, ohne die Zusage zu brechen.

2. Die Lösung: Der „Sofort-Check" und der „Nachtschicht-Optimierer"

Die Forscher haben ein System gebaut, das wie ein zweistufiger Prozess funktioniert. Man kann es sich wie einen Türsteher und einen Chef-Planer vorstellen.

Schritt 1: Der Türsteher (Prompt Confirmation)

Wenn ein neuer Anruf kommt, muss der „Türsteher" innerhalb von Sekunden entscheiden: „Ja, wir können das schaffen" oder „Nein, leider nicht".

  • Wie macht er das? Er schaut sich die aktuellen Fahrpläne der Busse an. Er versucht, den neuen Passagier einfach wie ein Puzzleteil in den bestehenden Plan zu schieben, ohne alles umzuwerfen.
  • Das Geniale: Er nutzt eine Art „intuitives Bauchgefühl" (ein KI-Modell), das gelernt hat, nicht nur auf den jetzigen Moment zu schauen, sondern auch in die Zukunft. Er fragt sich: „Wenn ich diesen Passagier jetzt nehme, habe ich später noch genug Platz für andere, die vielleicht anrufen?"

Schritt 2: Der Chef-Planer (Continual Optimization)

Sobald der Türsteher „Ja" gesagt hat und dem Kunden Bescheid gegeben hat, ist die Arbeit noch nicht getan. Bis zum nächsten Anruf vergeht vielleicht eine Minute oder fünf.

  • In dieser Zeit schaltet der „Chef-Planer" ein. Er ist wie ein Schachspieler, der zwischen den Zügen des Gegners nachdenkt.
  • Er nimmt die Fahrpläne und schaut: „Können wir die Routen noch ein bisschen glatter machen? Können wir einen Bus entlasten, damit er später schneller einen neuen Passagier aufnehmen kann?"
  • Er darf dabei die Zusage an den Kunden nicht brechen (der muss pünktlich abgeholt werden), aber er darf die Reihenfolge der anderen Stopps optimieren.

3. Der „Kluge Kopf" (Künstliche Intelligenz)

Das Herzstück des Systems ist eine künstliche Intelligenz (KI), die durch Verstärkungslernen (Reinforcement Learning) trainiert wurde.

Stellen Sie sich vor, wir lassen einen Roboter Millionen von Mal diesen Busdienst simulieren.

  • Wenn er eine schlechte Entscheidung trifft (z. B. einen Passagier ablehnt, obwohl er ihn hätte nehmen können, oder einen Plan macht, der später zu Chaos führt), bekommt er einen „Minus-Punkt".
  • Wenn er viele Passagiere glücklich macht und die Busse effizient nutzt, bekommt er einen „Plus-Punkt".

Nach Millionen von Simulationen hat der Roboter gelernt, nicht nur das Offensichtliche zu tun, sondern die langfristige Strategie zu verstehen. Er weiß: „Wenn ich jetzt einen kleinen Umweg mache, spare ich später Zeit und kann mehr Leute befördern."

4. Das Ergebnis: Weniger Absagen, mehr Zufriedenheit

Die Forscher haben ihr System mit echten Daten aus den USA getestet (sowohl mit einem echten Microtransit-Dienst als auch mit Taxis aus New York).

  • Geschwindigkeit: Das System sagt innerhalb von 0,2 bis 1 Sekunde zu oder ab. Das ist schneller als ein Mensch, der einen Kaffee trinkt.
  • Effizienz: Das Wichtigste: Das System hat viel weniger Fahrten abgelehnt als alle anderen bekannten Methoden. Es hat die Anzahl der erfolgreichen Fahrten deutlich erhöht.

Zusammenfassung in einem Bild

Stellen Sie sich vor, Sie sind ein Dirigent eines Orchesters (die Busse).

  • Die alten Methoden waren entweder so, dass Sie sofort „Ja" sagten, aber dann das Orchester nicht mehr anpassen durften (schlechte Musik), oder Sie warteten zu lange, bis Sie antworteten (die Musiker langweilten sich).
  • Die neue Methode: Sie sagen dem Solisten sofort: „Du darfst mitspielen!" (Prompt Confirmation). Aber während das Orchester spielt, hören Sie genau hin und passen die Lautstärke und den Takt der anderen Instrumente ständig an, damit das ganze Stück perfekt klingt (Continual Optimization). Und Ihr Gehirnteil (die KI) hat gelernt, dass man manchmal eine kleine Pause einlegen muss, um später eine große Melodie spielen zu können.

Fazit: Dieses Papier zeigt, wie man durch eine clevere Kombination aus „schnellem Ja-Nein" und „laufender Optimierung" mit KI einen besseren, schnelleren und zuverlässigeren öffentlichen Verkehr für alle schaffen kann.