Neue Methode für Fahrzeugplanung mit sofortiger Bestätigung von Voranfragen

Transportunternehmen, die On‑Demand‑Services anbieten, stehen vor der Herausforderung, Anfragen in Echtzeit zu bearbeiten. Besonders knifflig ist die Situation, wenn Fahrten bereits Stunden im Voraus gebucht werden: Die Agentur muss rasch entscheiden, ob die Anfrage angenommen werden kann, und gleichzeitig sicherstellen, dass alle angenommenen Fahrten wie versprochen ausgeführt werden.

Bestehende Algorithmen liefern entweder eine schnelle Bestätigung, dafür aber keine fortlaufende Optimierung der Routen, oder sie optimieren kontinuierlich, garantieren jedoch nicht, dass alle angenommenen Fahrten erfüllt werden. Um diese Lücke zu schließen, wurde ein neues Problemmodell entwickelt, das sowohl die sofortige Bestätigung als auch die kontinuierliche Routenoptimierung vereint.

Die vorgeschlagene Lösung kombiniert eine schnelle Einfügesuche für die Bestätigung mit einem „Anytime“-Algorithmus, der die Routen laufend verbessert. Durch den Einsatz von Reinforcement‑Learning wird ein nicht‑myopisches Zielfunktion trainiert, die beide Komponenten zu optimalen, langfristig vorteilhaften Entscheidungen führt.

In einer Evaluation mit einem realen Microtransit‑Datensatz einer US‑Transitbehörde konnte gezeigt werden, dass die neue Methode die Anzahl der erfolgreich bedienten Fahrten deutlich steigert und gleichzeitig die Reaktionszeit bei Voranfragen minimiert.