Im vorliegenden Beitrag wird ein Algorithmus zur vorhersagebasierten Fahrzeugrepositionierung für On-Demand-Ride-Pooling-Dienste vorgestellt. Mögliche zukünftige Anfragen werden als Stichproben aus einer erwarteten Nachfragevorhersage gezogen und damit zukünftige Flottenzustände simuliert, um räumliche Mängel an Fahrzeugen zu identifizieren. Es wird ein Optimierungsproblem formuliert, das Repositionierungsfahrten unter Berücksichtigung mehrerer Stichproben und Prognosehorizonte den Fahrzeugen zuweist. Der Algorithmus wird in einer agentenbasierten Simulation implementiert und mit anderen Algorithmen verglichen. Eine Fallstudie für Chicago, Illinois, zeigt erhöhte Service-Raten und Fahrzeugauslastungen während die Rechenzeit gering genug bleibt, um im Realbetrieb eingesetzt zu werden.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

On-Demand Ride-Pooling (ODRP) Dienste wurden in den letzten Jahren intensiv untersucht. Bei solchen Diensten fragen Kunden bei Bedarf Fahrten an, während der Betreiber einer Flotte den Fahrzeugen dynamisch individuelle Fahrpläne zuweist, um diese Anfragen zu bedienen. Nach Möglichkeit werden dabei Fahrten geteilt. Simulationsstudien (z. B. [1, 2, 3]) zeigten, dass die benötigte Flottengröße und die Belastung des Straßennetzes erheblich reduziert werden kann, wenn Taxifahrten oder Fahrten mit Privatfahrzeugen durch einen ODRP-Dienst ersetzt werden. Diese Studien nahmen jedoch eine hohe Marktdurchdringung eines solchen Dienstes an. Die Studie [4] zeigte hingegen, dass eine gewisse Anfragendichte nötig ist, um durch effektives Pooling Leerfahrten durch Anfahrt zum Kunden zu überwinden. Diese Skalierungseigenschaft (je höher die Anfragendichte, desto höher die Wahrscheinlichkeit teilbare Fahrten zu finden) von Ride-Pooling wurde durch makroskopische [5, 6] Modelle bestätigt.

Das zu Grunde liegende Optimierungsproblem zur Steuerung der ODRP-Flotte kann dem Dial-a-Ride-Problem (DARP) zugeordnet werden [7]. Da es NP-schwer ist, sind exakte Lösungsmethoden jedoch auf kleine Systemgrößen beschränkt. Um dennoch in Echtzeit auf neue Kundenanfragen reagieren zu können, wurden heuristische Methoden entwickelt, die dynamisch Fahrzeugen neue Pläne zuweisen (z. B. [8, 3, 9]). Entscheidungen, die diese Algorithmen treffen, sind allerdings meist myopisch. Wenn die Nachfrageverteilung asymmetrisch ist, kann dies mittelfristig zu einem Ungleichgewicht zwischen Nachfrage- und Fahrzeugverteilung führen. In solchen Fällen sammeln sich Fahrzeuge in Gebieten geringer Nachfrage, und fehlen in Gebieten mit hoher Nachfrage, wodurch Anfragen abgelehnt werden müssen oder eine Fahrt nur mit langen Wartezeiten angeboten werden kann.

Diese Studie behandelt das „Repositionierungs - (oder Rebalancing-) Problem“ für ODRP-Dienste. Ziel ist es ungenutzte Fahrzeuge proaktiv im Betriebsgebiet zu verteilen, um zukünftig erwartete Nachfrage obtimal abzudecken. Es wird ein Algorithmus vorgestellt, der das Teilen von Fahrten explizit berücksichtigt. In einer Simulationsstudie für Chicago, Illinois wird der Algorithmus getestet und mit anderen Repositionierungsmethoden verglichen.

2 Stand der Technik

Das Repositionierungsproblem tritt bei den meisten On-Demand Mobilitätsdiensten (ODM) auf, da Fahrzeuge sich durch asymmetrische Nachfrageverteilungen in Gebieten geringer Nachfrage sammeln. Im Gegensatz zu Car- oder Bikesharing-Diensten wird in dieser Studie ein ODM-Dienst betrachtet, bei dem jedem Fahrzeug ein Fahrer zur Verfügung steht oder Fahrzeuge autonom fahren und somit Repositionerungsfahrten jederzeit durchgeführt werden können. Erste Studien, die sich diesem Problem widmeten, konzentrierten sich auf Ride-Hailing-Dienste, die keine geteilten Fahrten zulassen. Da für jede angefragte Fahrt genau ein Fahrzeug benötigt wird, erlauben analytische Methoden die Berechnung von Ungleichgewichten zwischen Angebot und Nachfrage auf zonaler Ebene. Dabei wurden Lösungsansätze basierend auf Warteschlangentheorie [10] entwickelt, oder zukünftige Flottenzustände auf Basis von makroskopischen Modellen vorhergesagt [11]. Da die zonale Aggregation für Repositionierungen von großer Bedeutung ist [12], erwiesen sich Algorithmen, die die räumliche Korrelation zwischen Zonen berücksichtigen, als vorteilhaft [13].

Wenn Fahrten in ODRP-Diensten geteilt werden können, erhöht sich die Komplexität des Problems, da das Verhältnis zwischen erwarteter Nachfrage und erforderlichem Angebot nicht mehr trivial ist. Momentan ungenutzte Fahrzeuge können nun mehrere Kunden bedienen, zudem können Fahrzeuge während der Fahrt neue Kunden aufnehmen. Um dies zu berücksichtigen, wurde ein linearer (zu kalibrierender) Skalierungsfaktor eingeführt, um die Anzahl benötigter Fahrzeuge pro erwarteter Nachfrage abzuschätzen [14]. Als Alternative dazu können relative Nachfrage- und Angebotsverteilungen angeglichen werden, anstatt absolute Maße zu verwenden [15, 16]. Komplexere Algorithmen, wie beispielsweise der Verwendung von Markov-Entscheidungsprozessen [17], sind durch hohe Rechenzeiten meist auf kleine Systemgrößen beschränkt.

Die in dieser Studie verwendete Methodik beruht auf dem „Samplingverfahren“. Dabei werden von einer prognostizierten Nachfrageverteilung Stichproben gezogen und damit das zugrundeliegende Routenzuweisungsproblem explizit gelöst. Dieser Ansatz ermöglicht die explizite Einbeziehung von Servicedesign-Parametern, wie z. B. der Routenoptimierungsfunktion oder von zeitliche Randbedingungen in der Routenbildung. Da allerdings ein Vehicle-Routing-Problem gelöst werden muss, können Samplingverfahren rechenintensiv sein. Li et al. [18] entwickelte eine Lösungsmethode für das stochastische DARP unter Verwendung von Sampling, dessen Problemgröße allerdings auf 4 Fahrzeuge beschränkt war. Alonso-Mora et al. [19] verwendete Sampling, um potentielle zukünftigen Anfragen direkt in den Zuweisungsalgorithmus einzubinden. Die Methode ermöglichte Simulationen mit tausenden Fahrzeugen, allerdings erhöhte sich die Rechenzeit drastisch, wodurch Optimierungs-Timeouts eingeführt werden mussten, deren Einfluss auf die Zuweisung realer Nachfrage nicht nachvollziehbar ist.

In dieser Studie wird ein neuartiger Repositionierungsalgorithmus vorgestellt, der speziell auf Ride-Pooling-Dienste zugeschnitten ist. Der Algorithmus basiert auf dem Samplingverfahren und ist effizient genug, um eine Echtzeit-Anwendung auf Instanzen mit Hunderten von Fahrzeugen zu ermöglichen.

3 Methodik

Der Repositionierungsalgorithmus wird mittels Simulation evaluiert. Im Folgenden wird das Simulationsframework vorgestellt, welches auch den Kontrollalgorithmus zur Steuerung der Ride-Pooling-Flotte beinehaltet. Dabei wird insbesondere auf zwei Schritte des Kontrollalgorithmus eingegangen.

1) Der Zuweisung von Fahrplänen an Flottenfahrzeugen, um Kundenanfragen zu bedienen und

2) der Repositionierung von Fahrzeugen, um Verfügbarkeit für zukünftig erwartete Nachfrage zu gewährleisten.

Der Fokus liegt auf dem entwickelten Repositionierungsalgorithms.

3.1 Simulationsframework

Diese Studie verwendet das agentenbasierte Simulationsframework für ODM-Dienste Fleet-Py¹⁾ [20]. In der Simulation fordern Kunden Fahrten bei einem ODRP-Betreiber an, der wiederum seinen Fahrzeugen Fahrpläne zuweist, um die Anfragen zu bedienen. Die Fahrzeuge bewegen sich in einem Netzwerk G = (N, E) mit Knoten n ∈ N und Kanten e ∈ E. Jede Kundenanfrage r_i wird durch ein Tupel aus Startort o_i ∈ N , Zielort d_i ∈ N und dem Zeitpunkt der Anfrage t_i beschrieben. Es wird angenommen, dass Kunden den Dienst nicht nutzen, wenn sie nicht innerhalb einer maximalen Wartezeit von t? abgeholt werden können. Darüber hinaus sind die Kunden bereit einen Umweg von bis zu ∆^? relativ zur direkten Reisezeit zu akzeptieren, um Pooling zu ermöglichen. Die Flotte des Betreibers besteht aus Fahrzeugen v ∈ V mit Flottengröße |V |. Jedes Fahrzeug hat eine Kapazität von c_v Passagieren.

¹⁾ https://github.com/TUM-VT/FleetPy

Der Betreiber berechnet Fahrpläne   ψ, d. h. eine Liste von Haltepunkten, an denen Kunden in einem Fahrzeug ein- oder aussteigen. Zwischen den Haltepunkten fahren die Fahrzeuge auf der schnellsten Route im Netz. Fahrpläne gelten als zulässig, falls für jeden Kunden, der durch den jeweilgen Plan bedient würde, die maximale Wartezeitbeschränkung t^wait und die maximale Reisezeitbeschränkung ∆^? erfüllt ist, sowie zu keinem Zeitpunkt mehr als c_v Fahrgäste im Fahrzeug sind.

? Korrekte Darstellung und Formel in der PDF

Der Betreiber bewertet einen zulässigen Fahrplan anhand der Zielfunktion

ρ(ψ) = τ (ψ) − π|R_ψ| .                                           (1)

 τ (ψ) misst die Gesamtdauer, die zur Abarbeitung des Fahrplans benötigt wird, während |R_ψ| die Anzahl der Kunden darstellt, die bedient werden. π > 0 ist eine ausreichend große Zahl, um der Bedienung von Anfragen zu priorisieren. Ziel ist es Fahrpläne den Fahrzeugen zuzuweisen, die die Summe aller ρ(ψ) minimiert.

3.2  Zuweisungsalgorithmus

Der Zuweisungsalgorithmus erstellt aktualisierte Fahrpläne alle ∆t_A = 60s und weist neu eingegangene Anfragen den Fahrzeugen zu. Der verwendete Algorithmus zur Erstellung der Fahrpläne basiert auf [3]. Details der Implementierung sind in [9] zu finden. Da der Zuweisungsalgorithmus nicht der Schwerpunkt dieser Studie ist, wird er hier nur sehr oberflächlich beschrieben.

Grundsätzlich werden in einem ersten Schritt alle realisierbaren Fahrpläne auf der Grundlage des aktuellen Flottenzustandes und der aktuellen Kunden berechnet. Da die Anzahl möglicher Fahrpläne durch die verwendeten zeitlichen Randbedingungen stark eingeschränkt ist, kann der komplette Lösungsraum bestimmt werden. In einem zweiten Schritt wird ein Optimierungsproblem gelöst, welches die insgesamt besten Fahrpläne den Fahrzeugen zuweist.

3.3 Repositionierung

Sobald ein Fahrzeug einen Fahrplan abgeschlossen hat, kann es nur dann einen neuen Fahrplan zugewiesen bekommen, wenn eine Fahrtanfrage in der Nähe gestellt wird. Es werden daher Repositionierungsfahrten benötigt, um Fahrzeuge umzuverteilen. Typischerweise sind zu deren Ermittlung drei Schritte erforderlich: 1) Eine Prognose der zukünftigen Nachfrage. 2) Eine Methode, um den erwarteten Nutzen für die Entsendung von Fahrzeugen in eine bestimmte Region zu schätzen, und 3) ein Algorithmus zur Zuweisung von Repositionierungsfahrten.

Diese Studie konzentriert sich auf die letzten beiden Schritte. Es wird davon ausgegangen, dass das ODRP-Betriebsgebiet in Zonen Z unterteilt ist. Zusätzlich liegt eine Nachfrageprognose vor, die die erwartete Anzahl von Kunden λ^T_ij schätzt, welche innerhalb eines Zeitfensters zwischen [T, T + δ_T ] Fahrten von Zone i ∈ Z nach Zone j ∈ Z anfragen.

Der entwickelte Algorithmus beruht auf einem Samplingansatz und wird in Schritten von δ_T = 900s angewandt. Es werden künstliche Anfragen als Stichproben aus der prognostizierten Nachfrageverteilung gezogen. Diese Anfragen werden verwendet um, möglichst ähnlich zum Zuweisungsalgorithmus, Fahrpläne zu erstellen und damit zukünftige Flottenzustände zu berechnen, um Lücken in der Fahrzeugverfügbarkeit zu identifizieren.

Abbildung 1 gibt einen Überblick über den Repositionierungsalgorithmus. Im ersten Schritt (a) verwendet der Algorithmus als Input nur alle derzeit fahrenden (nicht untätigen) Fahrzeuge mit ihren jeweiligen momentan zugewiesenen Fahrplänen. (b) Für A_S verschiedene Stichproben werden Anfragen aus der Nachfragevorhersage gezogen. Diese Anfragen werden verfügbaren Fahrzeugen zugewiesen. Falls eine Anfrage nicht bedient werden kann, erstellt der Algorithmus ein neues hypothetisches Fahrzeug, das die Anfrage bedient. Ein hypothetisches Fahrzeug stellt somit einen identifizierten Bedarf an ein reelles Fahrzeug dar. Schließlich wird ein zonenbasiertes Zuweisungsproblem gelöst (c), das untätige Fahrzeuge zur Repositionierung in die Zone eines der hypothetischen Fahrzeuge zuweist (d).

Im Folgenden wird das Samplingverfahren und die Formulierung des Zuweisungsproblems genauer beschrieben.

3.3.1 Samplingverfahren

Zunächst werden zukünftige Anfragen aus der durch _λ^Ti,j beschriebenen Nachfragevorhersage innerhalb des Prognosehorizonts H gezogen. Dieser Horizont deckt die Zeitschritte T ∈ {t, t + δ_T , ..., t + H} ab.

Bild 1: Skizze des Algorithmus zur Berechnung von Repositionierungsfahrten.

Ein Poisson-Prozess mit der Rate λ^T_i,j bestimmt die Anzahl der angeforderten Fahrten von Zone i nach Zone j. Jeder Anfrage wird ein zufälliger Start- und Zielknoten innerhalb der Zonen zugewiesen. Deren Zeitpunkt wird zufällig im Intervall [T, T + δ_T ] gewählt. Die Flottenzustände werden in Zeitschritten von 60s in die Zukunft simuliert. In jedem Zeitschritt wird zunächst die Zuweisung neuer Anfragen behandelt. Um Repositionierungsentscheidungen schnell genug treffen zu können, ist es entscheidend, dass der hier verwendete Zuweisungsalgorithmus recheneffizient ist. Daher wird eine einfache Einfügeheuristik [8] verwendet: Die Anfrage wird nur in den aktuellen Fahrplan eines jeden Fahrzeugs eingefügt und derjenige Fahrplan zugewiesen, der die Zielfunktion (Gleichung 1) minimiert. Falls keine Lösung gefunden werden kann, wird ein neues hypothetisches Fahrzeug im Zonenzentroid der Anfrage erstellt und die Bedienung der Anfrage zugewiesen. Nachdem alle Anfragen des Zeitschritts zugewiesen wurden, werden die Fahrzeuge gemäß dem ihnen zugewiesenen Fahrplan bewegt.

Nachdem alle Anfragen bearbeitet wurden, werden die Eingangsparameter für das Optimierungsproblem erstellt. Ein hypothetisches Fahrzeug definiert einen zukünftigen Versorgungsengpass. Es wird dessen Startzone o_s,t, die Startzeit τ_s,t des Fahrplans und der Wert ρ_s,t der Zielfunktion des Fahrplans bestimmt. Die Startzeit beschreibt eine Randbedingung. Fahrzeuge müssen spätestens zu dieser Zeit in der Zone ankommen. Der Wert der Zielfunktion wird als Maß für den Nutzen des Betreibers verwendet, ein Fahrzeug in diese Zone zu repositionieren. Nicht immer können Fahrzeuge die Zone rechtzeitig erreichen. Daher kann es sinnvoll sein, dass ein Fahrzeug an einen späteren Haltepunkt im Fahrplan des hypothetischen Fahrzeugs repositioniert werden kann. Für jeden Fahrplan eines hypothetischen Fahrzeugs werden Teilfahrpläne definiert: Bei jedem Halt wird geprüft, ob noch Kunden im Fahrzeug sitzen würden. Falls dies nicht der Fall ist, wird ein neuer Teilfahrplan erstellt, der an diesem Haltepunkt beginnt.

Auf gleiche Weise werden für jeden Teilfahrplan die Parameter o_s,t, τ_s,t und ρ_s,t bestimmt.

3.3.2 Formulierung des Repositionierungsproblems

Ein ganzzahlig lineares Optimierungsproblem wird formuliert, um Repositionierungsfahrten zuzuweisen. Ungenutzte Fahrzeuge werden auf zonaler Ebene aggregiert. Da der Prognosehorizont H größer als die Repositionierungsperiode δ_T ist, werden auch mögliche zukünftige Repositionierungsentscheidungen berücksichtigt. Die Entscheidungsvariable θ⁰_o,d bezieht sich auf unmittelbare Repositionierungsfahrten, welche nach Lösung des Problems durchgeführt werden. Die Entscheidungsvariable θ?T,? hingegen beschreibt mögliche zukünftige Repositionierungsfahrten im Zeitschritt
T ∈ {1, 2, ..., T_max =  ^H?} in der Stichprobe s. θ⁰? ist dabei unabhängig von der Stichprobe s, da die Entscheidung zu einer guten Lösung in allen Realisierungen führen sollte. Das Optimierungsproblem ist wie folgt definiert:

? Korrekte Darstellung und Formel in der PDF

Formel in der PDF

Die Zielfunktion in Gleichung 2 beschreibt den Kompromiss zwischen Kosten für Repositionierung und deren erwarteten Nutzen. Der erste Term beschreibt die Kosten: c_o,d ≥ 0 ist die Reisezeit zwischen Zonenzentroiden. Der Faktor γ ∈ [0, 1] gewichtet die Kosten für die Zuweisung zukünftiger Repositionierungsfahrten. Der zweite Term beschreibt den erwarteten Nutzen:

ρ_s,t ≤ 0 ist der erwartete Nutzen einer Fahrt. φ^d,T_s,t ?      

? Korrekte Darstellung und Formel in der PDF

ist die entsprechende Entscheidungsvariable: Sie nimmt genau dann den Wert 1 an, wenn eine Repositionierungsfahrt aus Zone d ∈ Z im Zeitschritt T der Fahrt t aus der Stichprobe s zugeordnet wird. Die Menge T (s) enthält alle Fahrten aus Stichprobe s, während die Menge B(t) alle möglichen Entscheidungsvariablen (φ^d,T_s,t ?) enthält, die die Fahrt t rechtzeitig zur Startzeit τ_s,t erreichen können. Die Nebenbedingungen 3 und 4 beschränken die Anzahl an Fahrzeugen, die aus Zone o ∈ Z repositioniert werden können. Während für unmittelbare Repositionierungen in Nebenbedingung 3 nur die Anzahl der momentan untätigen Fahrzeuge V ^idle_o ?beachtet werden, werden bei zukünftigen Repositionierungen in Nebenbedingung 4 auch berücksichtigt, dass Fahrzeuge bereits in früheren Entscheidungszeitschritten entsandt wurden, zusätzliche Fahrzeuge mit aktuellen Zuweisungen untätig werden (∆V ^idle_τ,s,o ?)), oder Fahrzeuge untätig werden, nachdem sie ihre zugewiesene Fahrt nach Repositionierung beenden. D(o, τ ) ist dabei die Menge der Fahrten, die in der Zone o und der Entscheidungsperiode τ beendet werden. Durch die Gleichungen 5 und 6 wird jeder Repositionierungsfahrt genau einer Fahrt von hypothetischen Fahrzeugen pro Stichprobe s zugewiesen. Unmittelbaren Repositionierungsfahrten (Gleichung 5) können aus jeder Stichprobe genau eine Fahrt zugewiesen werden. Zukünftige Repositionierungsfahrten (Gleichung 6) können in jeder Stichprobe unterschiedlich sein. Gleichung 7 stellt sicher, dass jede Fahrt eines hypothetischen Fahrzeugs nur einmal zugewiesen wird.

? Korrekte Darstellung und Formel in der PDF

3.4 Vergleichsalgorithmen

Um die Leistungsfähigkeit des entwickelten Algorithmus zu bewerten, wird er in dieser Studie mit folgenden Algorithmen aus der Literatur verglichen:

• Keine Repositionierung: Es findet keine Repositionierung statt.
• Reagierende Repositionierung React [3]: Nach jedem Zuweisungsschritt werden ungenutzte Fahrzeuge zu den Orten nicht bedienter Anfragen geschickt.
• Repositionierung basierend auf Warteschlangentheorie QT [10]: Der Algorithmus beruht darauf durch Repositionierung die Warteschlangen von erwarteten Anfragen je Zone zu stabilisieren.
• Repositionierung mit Zeithorizont Hor [14]: Dieser Algorithmus zählt die erwartete Nachfrage pro Zone und optimiert auch die Zeitdauer, die ein repositionierendes Fahrzeug in dieser Zone innerhalb des Vorhersagehorizonts verfügbar wäre.

Die Algorithmen QT und Hor beruhen auf Nachfragevorhersagen pro Zonen und haben zwei freie Parameter: Die Prognosehorizonte H_QT und H_Hor definieren den Zeithorizont der Vorhersage.

Die Parameter µ_QT und µ_Hor sind Nachfrageskalierungsfaktoren, und beschrieben die Anzahl an Fahrten, die im Schnitt durch Pooling von Fahrzeugen bedient werden können. Dieser wird hier im QT -Algorithmus neu eingeführt, da dieser ursprünglich für Ride-Hailing entwickelt wurde.

4 Fallstudie

Der Algorithmus wird in einer Fallstudie von Chicago, Illinois, evaluiert. Analog zu [21] wird das Straßennetzwerk innerhalb der Stadtgrenze aus OpenStreetMap extrahiert und Nebenstraßen entfernt, um die Netzwerkgröße zu reduzieren. Es werden 4000 Zugangsknoten als mögliche Start- und Zielpunkt für Kundenanfragen definiert, die nicht an Hauptverkehrsstraßen liegen und höchsten 300m auseinanderliegen. Dies ermöglicht die Verwendung von Reisezeittabellen, um Rechenkosten für Routingabfragen zu verringern. Anfragen an den ODRP-Dienst werden anhand des TNC-Datensatzes für Chicago, Illinois²⁾ erstellt. Als Anfragen werden TNC-Fahrten für den 07.06.2022 verwendet, die innerhalb der Stadtgrenze von Chicago beginnen und enden. Nach Filtern möglicher fehlerhafter Einträge und Rundfahrten analog zu [21] verbleiben 127528 Fahrten. Die Anfragen starten und enden an einem zufälligen Zugangsknoten innerhalb des jeweiligen Abhol- und Absetzgebiets. Als Anfragenzeitpunkt wird ein zufälliger Sekundenwert aus dem gemeldeten 15-minütigen Startzeitintervall der Fahrt verwendet. Um die Rechenzeit zu reduzieren, wird nur eine 20% Stichprobe der erstellten Anfragen in der Simulation verwendet. Zur Kalibrierung der Netzwerkreisezeiten, werden die gemeldeten Fahrtzeiten mit den Reisezeiten der schnellsten Route im Netzwerk verglichen. Um den Verkehrszustand des entsprechenden Tages abzubilden, werden die Kantenreisezeiten mit einem Faktor von 1.62 skaliert, sodass die Reisezeiten der schnellsten Route im Durchschnitt den gemeldeten Fahrtzeiten pro Fahrt entsprechen. Basierende auf der Methode von [14], werden 48 Zonen mit jeweiligen Zentroiden definiert sodass jeder Zugangsknoten innerhalb von t^wait_max von einem Zentroid erreichbar ist.

²⁾ https://data.cityofchicago.org/Transportation/Transportation-Network-Providers-Trips-2022/2tdj-ffvb

Fahrzeuge haben eine Kapazität von c_v = 4. Es wird eine maximale Wartezeit von t^wait_max= 6 min und ein maximaler relativer Umweg von ∆^det_max  = 40% verwendet. Im Basisfall werden 300 Fahrzeuge eingesetzt, die im Szenario mit Repositionierung etwa 90% der Nachfrage bedienen.

Es werden zwei verschiedene Methoden zur Vorhersage von Nachfrage getestet:

1. Perfekte Vorhersage: Die Anzahl zukünftiger Anfragen zwischen Zone i und j im Prognoseintervall T bestimmt die Poisson-Rate λ^T_i,j .
2. Myopische Vorhersage: In jedem Zeitintervall T wird die Anzahl der Anfragen im vergangenen Zeitintervall {T − δ_T , T } zwischen Zone i und j als Poissonrate λ^T_i,j verwendet.

Komplexere Vorhersagealgorithmen sollten mindestens so gut abschneiden wie eine myopische Vorhersage, während die perfekte Vorhersage als bestmögliche Variante dient.

Repositionierungen werden alle δ_T = 900s berechnet und durchgeführt. Im Basisszenario wird ein Prognosehorizont von H = 2700s mit A_S = 3 und γ = 0.5 verwendet. Für den QT-Algorithmus wird µ_QT = 0.7 und H_QT = 2700s verwendet. Für den Hor-Algorithmus gilt µ_Hor =0.1 und H_Hor = 1800s.

Der Code ist in Python implementiert und Simulationen wurden auf einem Intel Xeon Silver Prozessor mit 2.10GHz und 192GB RAM durchgeführt. Optimierungsprobleme wurden mit „Gurobi 9.3“ (https://www.gurobi.com/ ) gelöst.

5 Ergebnisse

Abbildung 2 vergleicht den ODRP-Dienst mit und ohne dem entwickeltem Repositionierungsalgorithmus. Abbildung 2a zeigt die Anzahl der bedienten Anfragen für drei verschiedene Flottengrößen. Wenn keine Repositionierung stattfindet, werden sogar mit 350 Fahrzeugen nur etwa 50% der Anfragen bedient. Mit Repositionierung können mit 300 Fahrzeugen etwa 88% der Anfragen bedient werden. Abbildung 2b zeigt die Zeitdauer, die ein Fahrzeug im Schnitt damit verbringt, Kunden zu befördern und somit Umsatz für den Betreiber generiert (Fahrzeugumsatzstunden). In Szenarien mit Repositionierung generieren Fahrzeuge mindestens 14.5 Stunden Umsatz, während diese Auswertegröße ohne Repositionierung auf unter 11 Stunden fällt.

Abbildungen 2c und 2d zeigen die zeitliche Entwicklung der Flottenzustände während des Betriebstages für einen Dienst mit 300 Fahrzeugen ohne bzw. mit Repositionierung. Ohne Repositierung ist zu erkennen, dass ein Großteil der Flotte untätig ist und somit weder Kunden bedient noch zur Generierung von Umsatz beiträgt. Mit Repositionierung hingegen werden Fahrzeuge erfolgreich in Gebiete mit Nachfrage positioniert, wodurch die Flottenauslastung nur in Zeiten niedriger Nachfrage (z. B. 2-5 Uhr morgens) gering ist. Dies führt allerdings dazu, dass zusätzliche Repositionierungs- und damit Leerfahrten erzeugt werden.

Abbildungen 2e und 2f zeigen die räumliche Verteilung der unbedienten Nachfrage und die Positionen untätiger Fahrzeuge. Ohne Repositionierung zeigt sich eine deutliche Asymmetrie bezüglich dieser beiden Größen: Während die meisten Anfragen im Stadtzentrum von Chicago abgelehnt werden müssen, da keine Fahrzeuge vorhanden sind, sammeln sich viele Fahrzeuge in Randgebieten, besonders am Flughafen O’Hare im Nordwesten des Betriebsgebiets. Mit Repositionierung hingegen sinkt die absolute Anzahl an unbedienten Anfragen deutlich und die Fahrzeuge verteilen sich gemäß der Nachfrage über das Gebiet. Untätige Fahrzeuge sind vor allem im Stadtzentrum zu finden. Durch hohe Nachfrage ist deren Standdauer aber meist kurz. Abbildung 3 vergleicht verschiedene Repositionierungsalgorithmen und Vorhersagemethoden. Abbildung 3a zeigt die bedienten Kunden. Im Vergleich zu Abbildung 2a ist der große Nutzen von Repositionierung zu erkennen. Unabhängig von Algorithmus und Vorhersagemethode kann ein Dienst mit Repositionierung deutlich mehr Kunden als ohne Repositionierung bedienen. Im Vergleich der verschiedenen Algorithmen kann das vorgestellte Samplingverfahren die meisten Kunden bedienen.

Bild 2: Vergleich der Ergebnisse mit und ohne Anwendung von Repositionierung. Falls nicht anders spezifiziert, sind Ergebnisse mit 300 Fahrzeugen dargestellt.

Nur bei einer Flottengröße von 250 Fahrzeugen und der myopischen Prognose kann der Hor-Algorithmus etwas mehr Kunden bedienen. Selbst mit der myopischen Vorhersage liefert die Sampling-Methode bei höheren Flottengrößen bessere Ergebnisse als alle anderen Methoden. Insgesamt ist der Einfluss der Vorhersagemethode bei allen getesteten Algorithmen gering. Dies zeigt, dass der ODRP-Dienst auch bei ungenauen Nachfrageprognosen durch Repositionierung profitiert. Auch die Fahrzeugumsatzstunden (Abbildung 3b) können mit dem Samplingalgorithmus um etwa 30min pro Fahrzeug und Tag im Vergleich zu den anderen Methoden gesteigert werden.

Abbildung 3c zeigt den Anteil an Leerfahrten der Flotte, die sowohl Repositionierungsfahrten als auch leere Anfahrten zum Kunden umfassen. Der größte Anteil Lehrfahrten ist bei der Methode Hor zu beobachten, was auf eine aggressive Repositionierungsstrategie hinweist. Als Kompromiss können dafür vergleichsweise viele Kunden (Abbildung 3a) bedient werden. Der Samplingalgorithmus schneidet dagegen bei beiden Auswertegrößen gut ab. Die myopische Prognose erhöht den Anteil Leerkilometer um etwa 1 − 2%.

Abbildung 3d zeigt die Poolingsystemeffizienz, welche nach [22] definiert ist durch:

Formel in der PDF

Diese Größe stellt somit Fahrzeugkilometer (mit Leerfahrten) den potentiellen Direktfahrten von Kunden gegenüber. Die Systemeffizienz ist für alle Repositionerungsmethoden größer als eins. Es wird daher durch Pooling mehr Fahrtstrecke geteilt als Leerkilometer erzeugt werden. Der hohe Anteil an Leerfahrten führt bei der Hor-Methode zur geringsten Systemeffizienz. Mit einer perfekten Nachfrageprognose schneidet die Sampling-Methode am besten ab. Abbildung 3e zeigt, dass die Samplingmethode auch die geringste durchschnittliche Kundenwartezeit aller Methoden aufweist.

Mit durchschnittlich 73s Rechenzeit ist der Samplingalgorithmus zwar deutlich langsamer als die markroskopischen Vergleichsalgorithmen, allerdings ist eine Anwendung in Echtzeitdiensten trotzdem möglich, da die Rechenzeit deutlich kürzer als das Repositionierungsinterval ist. Außerdem kann die Samplingmethode leicht parallelisiert werden, da die verschiedenen Stichproben unabhängig voneinander berechnet werden können.

6 Zusammenfassung und Ausblick

In dieser Studie wurde ein Algorithmus vorgestellt, um für einen On-Demand Ride-Pooling Dienst ungenutzte Fahrzeuge basierend auf einer Nachfrageprognose zu repositionieren. Der Algorithmus verwendet ein Samplingverfahren, um zukünftige Flottenzustände akkurat abzuschätzen und Versorgungsengpässe zu identifizieren. Eine simulationsbasierte Fallstudie für Chicago, Illinois zeigt, dass der Algorithmus die Anzahl der bedienten Anfragen im Vergleich zu einem Dienst ohne Repositionierung fast verdoppeln kann.

Bild 3: Vergleich verschiedener Repositionierungsalgorithmen und Prognosemethoden. Da der React-Algorithmus keine Prognose benötigt, ist nur eine Kurve dargestellt.

Auch im Vergleich mit anderen Repositionierungsalgorithmen aus der Literatur schneidet der vorgestellte Algorithmus am besten ab. Er erhöht die Service-Rate und die Poolingeffizienz während Leerfahrten und Kundenwartezeiten reduziert werden. Als Kompromiss erhöht sich die Rechenzeit, welche dennoch niedrig genug für eine Anwendung in einem realen Dienst ist.

In Zukunft soll der Algorithmus weiter verfeinert werden. Zum Beispiel muss für das angewandte Samplingverfahren die Zuweisung von Repositionierungsfahrten nicht auf Zonenebene erfolgen, sondern erlaubt theoretisch die Zuweisung auf Knoteneben, was eine genauere Fahrzeugverteilung ermöglicht. Zudem kann in diesem Verfahren die zeitliche Änderung und Stochastizität von Netzwerkreisezeiten berücksichtigt werden. Diese Anpassungen und deren höhere Komplexität gehen allerdings mit einer möglichen erhöhten Rechenzeit einher, die es abzuschätzen gilt.

Literatur

1. International Transport Forum. Urban mobility system upgrade: How shared self-driving cars could change city traffic, 2015.
2. Markus Friedrich and Maximilian Hartl. MEGAFON - Modellergebnisse geteilter autonomer Fahrzeugflotten des öffentlichen Nahverkehrs, 2016.
3. Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus. On-demand high-capacity ride-sharing via dynamic trip-vehicle Proceedings of the National Academy of Sciences of the United States of America, 114(3):462–467, 2017.
4. Roman Engelhardt, Florian Dandl, Aledia Bilali, and Klaus Bogenberger. Quantifying the benefits of autonomous on-demand ride-pooling: A simulation study for munich, germany. In 2019 IEEE Intelligent Transportation Systems Conference (ITSC), pages 2992–2997. IEEE, 2019.
5. Tachet, O. Sagarra, P. Santi, G. Resta, M. Szell, S. H. Strogatz, and C. Ratti. Scaling law of urban ride sharing. Scientific Reports, 7(1):42868, 2017.
6. Aledia Bilali, Roman Engelhardt, Florian Dandl, Ulrich Fastenrath, and Klaus Bogenberger. Analytical and agent-based model to evaluate ride-pooling impact factors. Transportation Research Record: Journal of the Transportation Research Board, 2674(6):1–12, 2020.
7. Jean-François Cordeau and Gilbert Laporte. A tabu search heuristic for the static multivehicle dial-a-ride Transportation Research Part B: Methodological, 37(6):579–594, 2003.
8. Jang-Jei Jaw, Amedeo R. Odoni, Harilaos N. Psaraftis, and Nigel H.M. Wilson. A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time Transportation Research Part B: Methodological, 20(3):243–257, 1986.
9. Roman Engelhardt, Florian Dandl, and Klaus Bogenberger. Speed-up heuristic for an on demand ride-pooling algorithm. https://arxiv.org/pdf/2007.14877, 2020.
10. Rick Zhang and Marco Pavone. Control of robotic mobility-on-demand systems: A queueing-theoretical perspective. The International Journal of Robotics Research, 35(1- 3):186–203, 2016.
11. Amir Hosein Valadkhani and Mohsen Ramezani. Dynamic ride-sourcing systems for cityscale networks, part ii: Proactive vehicle repositioning. Transportation Research Part C: Emerging Technologies, 152:104159, 2023.
12. Florian Dandl, Michael Hyland, Klaus Bogenberger, and Hani S. Mahmassani. Evaluating the impact of spatio-temporal demand forecast aggregation on the operational performance of shared autonomous mobility fleets. Transportation, 46(6):1975–1996, 2019.
13. Arslan Ali Syed, Florian Dandl, Bernd Kaltenhäuser, and Klaus Bogenberger. Density based distribution model for repositioning strategies of ride hailing services. Frontiers in Future Transportation, 2, 2021.
14. Alex Wallar, Menno van der Zee, Javier Alonso-Mora, and Daniela Rus. Vehicle rebalancing for mobility-on-demand systems with ride-sharing. In IROS Madrid 2018, pages 4539–4546. IEEE, 2018.
15. Martin Kagerbauer, Nadine Kostorz, Gabriel Wilkes, Florian Dandl, Roman Engelhardt, Ulrich Glöckl, Eva Fraedrich, and Felix Zwick. Ridepooling in der Modellierung des Gesamtverkehrs - Methodenbericht zur MOIA Begleitforschung.
16. Tilmann Schlenther, Gregor Leich, Michal Maciejewski, and Kai Nagel. Addressing spatial service provision equity for pooled ride–hailing services through rebalancing. IET Intelligent Transport Systems, 17(3):547–556, 2023.
17. Hamid R. Sayarshad and Joseph Y.J. Chow. Non-myopic relocation of idle mobility-on-demand vehicles as a dynamic location-allocation-queueing Transportation Research Part E: Logistics and Transportation Review, 106:60–77, 2017.
18. Donghui Li, Constantinos Antoniou, Hai Jiang, Qianyan Xie, Wei Shen, and Weijian Han. The value of prepositioning in smartphone-based vanpool services under stochastic requests and time-dependent travel times. Transportation Research Record: Journal of the Transportation Research Board, 2673(2):26–37, 2019.
19. Javier Alonso-Mora, Alex Wallar, and Daniela Rus. Predictive routing for autonomous mobility-on-demand systems with ride-sharing. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3583–3590, 2017.
20. Roman Engelhardt, Florian Dandl, Arslan-Ali Syed, Yunfei Zhang, Fabian Fehn, Fynn Wolf, and Klaus FleetPy: A modular open-source simulation tool for mobility on-demand services. https://arxiv.org/pdf/2207.14246, 2022.
21. Florian Dandl, Michael Hyland, Klaus Bogenberger, and Hani S Mahmassani. Dual-horizon forecasts and repositioning strategies for operating shared autonomous mobility fleets. 99th Annual Meeting of the Transportation Research Board (TRB 2020), 2020.
22. Christian Liebchen, Martin Lehnert, Christian Mehlert, and Martin Schiefelbusch. Betriebliche Effizienzgrößen für Ridepooling-Systeme. In Making Connected Mobility Work: Technische und betriebswirtschaftliche Aspekte, pages 135–150. Springer Fachmedien Wiesbaden, Wiesbaden, 2021.