Kurzfassung

Das Kernstück eines On-Demand Shuttle-Systems ist ein intelligenter Matching-Algorithmus, bei dem Fahrgastanfragen den Fahrzeugen optimiert zugewiesen werden. Eine geeignete Plattform zur Modellierung und Simulation passender Algorithmen ist eine mikroskopische Verkehrssimulation, wie sie auch von anderen Verkehrsmitteln bekannt ist. Allerdings wurden On-Demand Shuttle-Systeme bisher nicht ausreichend in Mikrosimulationsumgebungen untersucht, was höchstwahrscheinlich auf die besonderen Eigenschaften des dynamischen Routings zurückzuführen ist. Ziel dieser Arbeit ist es, diese Lücke zu schließen und eine Plattform für On-Demand Shuttle-Systeme in einer mikroskopischen Verkehrssimulation zu modellieren. Ein spontaner Matching-Algorithmus wird vorgestellt und seine Implementierung in der Mikrosimulation ausgearbeitet. Die Ergebnisse einer Fallstudie werden vorgestellt und das Potenzial einer solchen Plattform sowie weitere Forschungsthemen werden am Ende des Beitrags diskutiert.

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

1 Einleitung

Nachfragegesteuerte Verkehre erschließen einen Verkehrsraum in verschiedenen Formen, bspw. in einer Linie (Bedarfslinienverkehr), einem Korridor (Richtungsbandbetrieb), einem Sektor (Sektorbetrieb) oder einer Fläche (Flächenbetrieb) [1]. Ein On-Demand-System im Flächenbetrieb kann als eine Verkehrsart definiert werden, bei der Fahrzeuge nicht nach einem vordefinierten Zeitplan auf einer vordefinierten Route fahren, um Fahrgäste zu befördern. Stattdessen fordern Fahrgäste bei Bedarf über eine Smartphone-App ein Fahrzeug an (Zeitflexibilität) und können direkt vom Start- zum Zielort fahren (Routenflexibilität). Diese Flexibilität ist für viele Fahrgäste attraktiv und solche On-Demand-Systeme bekommen immer größere Beliebtheit, insbesondere in dicht besiedelten städtischen Gebieten. Taxiähnliche Systeme (wie Uber oder Lyft) sowie Mikromobilitäts-Sharing-Systeme sind bekannte Beispiele für diese On-Demand-Mobilität. Eine weitere Anwendung ist das On-Demand Shuttle-System, bei dem eine Fahrzeugflotte zentral disponiert wird, um unterschiedliche Fahrgastanfragen zu bedienen. Weltweit gibt es viele Anwendungen von On-Demand Shuttle-Systemen, und es besteht eine große Begeisterung dafür, die Fahrzeuge in Zukunft durch autonome Fahrzeuge zu ersetzen, was zu einer erheblichen Senkung der Betriebskosten führen würde.

Ein wichtiger Aspekt der On-Demand Shuttle-Systeme ist die Betriebsart. Ridehailing und Ridepooling sind vor allem die beiden bekannten Formen. Unter Ridehailing versteht man das System, bei dem Fahrgäste während ihrer Fahrt alleine reisen, d. h. ein exklusives System. Exklusive Taxisysteme wurden in [2] und [3] ausführlich analysiert. Ridepooling ermöglicht es hingegen, Fahrten mit anderen Personen zu teilen, wenn zum Beispiel beide Fahrgäste ein ähnliches Ziel haben. Die Bündelung der Fahrten als solche steigert zwar die Gesamteffizienz, könnte aber gleichzeitig Unzufriedenheit der Fahrgäste aufgrund von Umwegen (daher längere Reisezeiten) und mangelnder Exklusivität (daher Unannehmlichkeiten) bedeuten.

Der Kern eines On-Demand-Shuttle-Systems ist ein intelligenter Matching-Algorithmus, bei dem Fahrgastanfragen den Fahrzeugen optimiert zugewiesen werden. Diese Optimierung kann je nach Art des Betriebs (Ridehailing oder Ridepooling) viele Parameter haben.

Mikroskopische Verkehrssimulationen werden häufig zur Analyse von Verkehrsmanagementmaßnahmen eingesetzt, indem Was-wäre-wenn-Szenarien erstellt und verglichen werden [4]. Allerdings wurden bisherige On-Demand Shuttle-Systeme in Mikrosimulationsumgebungen nicht ausreichend untersucht. In der herkömmlichen Mikrosimulation bewegen sich Fahrzeuge mit voller Kenntnis darüber, wohin sie fahren müssen, da sie alle eine vordefinierte Route haben, um ihre Ziele zu erreichen. An jeder Kreuzung (die als Entscheidungspunkt angesehen werden können) erhalten Fahrzeuge eine Routeninformation, die angibt, in welche Richtung sie fahren müssen. Dieser Ansatz wird als statisches Routing bezeichnet und ist sinnvoll, wenn nicht mehrere Fahrtmöglichkeiten von A nach B bestehen. Ein On-Demand-System unterscheidet sich jedoch von diesem Standardfall, da Fahrzeuge ihre Fahrt ausgelöst durch ein Ereignis starten (z. B. eine anstehende Anfrage oder das Bringen eines Fahrgasts zum Zielpunkt), und die gewählte Route wird zeitnah als kürzester Weg/Zeit basierend auf ihrer aktuellen Position sowie der Verkehrssituation berechnet. Darüber hinaus kann eine Fahrtanfrage (oder Fahrzeugbewegungen allgemein) von jeder Haltestelle zu jeder Haltestelle erfolgen, was zu mehreren Bewegungsmöglichkeiten führt. Ein statisches Routing ist daher nicht mehr möglich, was ein Grund dafür sein könnte, dass solche Systeme nicht bevorzugt in Mikrosimulationen modelliert werden. Diese besondere Eigenschaft von On-Demand-Systemen erfordert einen externen Algorithmus, der auf der Mikrosimulationsumgebung aufbaut.

Ziel dieser Arbeit ist es, diese Lücke zu schließen und eine Plattform für On-Demand Shuttle-Systeme in einer mikroskopischen Verkehrssimulation zu modellieren. Diese Anwendung würde folgende Vorteile mit sich bringen:

• eine Testumgebung zur Untersuchung verschiedener Fahrzeug-Anfrage-Matching-Algorithmen ermöglichen,
• eine Simulationsplattform auch für andere On-Demand-Modi wie Mikromobilität und Taxis bereitstellen,
• die Interaktion zwischen On-Demand-Fahrzeugen und anderen Verkehrsmitteln gewähren,
• eine ganzheitliche mikroskopische Verkehrssimulation unter Berücksichtigung aller Verkehrsmodi ermöglichen.

Die Simulationen wurden in der mikroskopischen Verkehrssimulationssoftware Vissim der Firma PTV AG [5] durchgeführt. Wie bereits erwähnt, reichten Standardfunktionalitäten nicht aus, um die Besonderheiten von On-Demand-Systemen zu erfassen. Um dem entgegenzuwirken, wurden Algorithmen in Python programmiert und die Simulation extern gesteuert, um insbesondere die On-Demand-Shuttles zu disponieren.

2 Methodik

Bei einem On-Demand-Shuttle-System sendet ein Fahrgast eine Anfrage an das System, in der er angibt, dass er zu einem bestimmten Zeitpunkt (oft sofort) von A nach B fahren möchte. Nach dieser Anfrage muss ihm das System ein Fahrzeug zur Abholung schicken und dieses Fahrzeug transportiert den Fahrgast dann zum Zielpunkt. Dieses Phänomen ist als Dial-a-Ride-Problem (DARP) bekannt. In der Literatur gibt es zwei Arten von DARP, nämlich statisches und dynamisches DARP [6]. Beim statischen DARP sind die Anfragen im Voraus bekannt und das System versucht, anhand der Start- und Zielpunkte die beste Tour zu generieren. Ein On-Demand-System nur mit Vorausbuchung oder ein fahrplanbasiertes öffentliches Verkehrssystem könnte hierfür gute Beispiele sein. So wurden in [7] die Zuweisungen eines statischen DARP von On-Demand-Fahrzeugen in der SUMO-Mikrosimulationsumgebung umgesetzt. Bei einem dynamischen DARP werden Anfragen für sofortige Fahrten jedoch spontan erhalten, also das System muss „online“ reagieren. Diese Studie befasst sich mit dem dynamischen DARP, wie im Folgenden ausführlich erläutert. Die Matching-Methode von [8] wurde als Basis genommen und weiterentwickelt.

Wenn eine Anfrage im System erfasst wird, muss der Dispositionsalgorithmus entscheiden, welches Fahrzeug diese übernimmt. Dies hängt von der Art des On-Demand-Systems und einer Reihe von Parametern ab:

2.1 Fall Ridehailing

In einem Ridehailing-System werden die Anfragen nacheinander abgearbeitet. Für jedes stillstehende Fahrzeug gibt es nur eine Einfügemöglichkeit der neuen Anfrage. Wenn zu einem bestimmten Zeitpunkt eine neue Anfrage vom Fahrgast X im System eintrifft, ist die Möglichkeit für ein stillstehendes Fahrzeug unkompliziert:

• Zuerst wird X abgeholt (Pick-up), dann wird X zum Ziel gebracht (Drop-off): X_P → X_D

Man kann davon ausgehen, dass auch ein bereits besetztes Fahrzeug für diese Anfrage in Frage kommen könnte. Da beim Ridehailing jedoch keine Fahrtbündelung zulässig ist, kann das Fahrzeug die neue Anfrage erst dann bedienen, wenn es die bestehende Anfrage abgearbeitet hat. Beispielsweise hat ein Fahrzeug gerade Fahrgast A abgeholt und in diesem Moment geht eine neue Anfrage von Fahrgast X im System ein. Die einzige Einfügemöglichkeit wird wie folgt sein:

• Zuerst wird A zum Ziel gebracht, dann X abgeholt, dann X zum Ziel gebracht: A_D → X_P → X_D

Für den Fall, dass eine neue Anfrage eintrifft, während das Fahrzeug bereits unterwegs ist, um einen Fahrgast A abzuholen, gibt es zwei Alternativen. Entweder holt das Fahrzeug zunächst die bestehende Anfrage ab, bringt sie zum Ziel und bedient dann die neue Anfrage; oder es holt zunächst die neue Anfrage ab, bringt sie zum Ziel und bedient dann die bestehende. Letzteres eignet sich besonders für die Fälle, in denen sowohl der Abhol- als auch der Zielpunkt der neuen Anfrage auf dem Weg des Fahrzeugs zur Abholung der bestehenden Anfrage ist. Die beiden Einfügemöglichkeiten sind wie folgt:

• Zuerst wird A abgeholt, dann A zum Ziel gebracht, dann X abgeholt, dann X zum Ziel gebracht: 
  A_P → A_D → X_P → X_D

• Zuerst wird X abgeholt, dann X zum Ziel gebracht, dann A abgeholt, dann A zum Ziel gebracht: 
  X_P → X_D → A_P → A_D

2.2 Fall Ridepooling

Beim Ridepooling wird der Auswahlprozess komplizierter. Selbst wenn nur ein Fahrzeug für die neue Anfrage in Betracht gezogen wird, gibt es verschiedene Kombinationen, um diese neue Anfrage und die bereits im Fahrzeug befindlichen oder noch abzuholenden Fahrgäste zu bedienen. Dieser Fall kann in drei Unterfällen behandelt werden: i) wenn ein bereits besetztes Fahrzeug eine neue Anfrage erhält, ii) wenn ein Fahrzeug, das auf dem Weg zur Abholung eines Fahrgasts ist, eine neue Anfrage erhält, iii) beide Fälle zusammen. Alle diese Unterfälle werden in den folgenden Teilen erläutert:

2.2.1 Ridepooling mit im Fahrzeug befindlichen Fahrgästen

In diesem Fall hat ein Fahrzeug gerade Fahrgast A abgeholt und in diesem Moment geht eine neue Anfrage von Fahrgast X im System ein. Wenn dieses Fahrzeug ihn auch bedienen möchte, hat es genau drei Möglichkeiten:

• Zuerst wird X abgeholt, dann A zum Ziel gebracht, dann X zum Ziel gebracht:
  X_P → A_D → X_D

• Zuerst wird X abgeholt, dann X zum Ziel gebracht, dann A zum Ziel gebracht:
  X_P → X_D → A_D

• Zuerst wird A zum Ziel gebracht, dann X abgeholt, dann X zum Ziel gebracht: 
   A_D → X_P →X_D

Steigt die Zahl der im Fahrzeug befindlichen Fahrgäste, erhöht sich entsprechend auch die Zahl der Kombinationen. Unter der Annahme, dass i die Anzahl der im Fahrzeug befindlichen Fahrgäste ist, kann die Anzahl der Kombinationen zur Bedienung der im Fahrzeug befindlichen Fahrgäste sowie der neuen Anfrage so formuliert werden:

Formel in der PDF

Es müssen i Drop-offs mit einem neuen Pick-up sowie einem neuen Drop-off kombiniert werden, wofür es (i+2)! Möglichkeiten gibt. Bei der Hälfte dieser Möglichkeiten ist der neue Pick-up vor dem neuen Drop-off. Bei der anderen Hälfte ist es umgekehrt. Daher muss die Gesamtzahl noch durch zwei geteilt werden. 

Nach Gleichung (1) führen kleine i-Werte zu einer geringen Anzahl an Kombinationen (z. B. drei Kombinationen für i=1), etwas größere i-Werte führen jedoch zu einer höheren Anzahl an Kombinationen (z. B. 60 Kombinationen für i=3). Darüber hinaus führen noch größere Werte zu einer sehr großen Anzahl von Kombinationen (z. B. 2520 Kombinationen für i=5).

2.2.2 Ridepooling mit abzuholenden Fahrgästen

In diesem Fall wurde gerade ein Fahrzeug für eine Anfrage A zugewiesen und ist auf dem Weg, ihn abzuholen. In diesem Moment geht eine neue Anfrage von Fahrgast X im System ein. Wenn dieses Fahrzeug ihn auch bedienen möchte, hat es genau sechs Möglichkeiten:

• Zuerst wird A abgeholt, dann X abgeholt, dann A zum Ziel gebracht, dann X zum Ziel gebracht:
  A_P → X_P → A_D → X_D

• Zuerst wird A abgeholt, dann X abgeholt, dann X zum Ziel gebracht, dann A zum Ziel gebracht:
  A_P → X_P → X_D → A_D

• Zuerst wird A abgeholt, dann A zum Ziel gebracht, dann X abgeholt, dann X zum Ziel gebracht: 
  A_P → A_D → X_P → X_D

• Zuerst wird X abgeholt, dann A abgeholt, dann A zum Ziel gebracht, dann X zum Ziel gebracht:
  X_P → A_P → A_D → X_D

• Zuerst wird X abgeholt, dann A abgeholt, dann X zum Ziel gebracht, dann A zum Ziel gebracht:
  X_P → A_P → X_D → A_D

• Zuerst wird X abgeholt, dann X zum Ziel gebracht, dann A abgeholt, dann A zum Ziel gebracht:
  X_P → X_D → A_P → A_D

Ebenso wie bei dem vorherigen Unterfall erhöht sich durch die Erhöhung der Zahl der abzuholenden Fahrgäste auch die Zahl der Kombinationen. Unter der Annahme, dass t die Anzahl der von einem Fahrzeug abzuholenden Fahrgäste ist, kann die Anzahl der Kombinationen zur Bedienung der abzuholenden Fahrgäste sowie der neuen Anfrage so formuliert werden:

Formel in der PDF

Es müssen t Pick-ups und t Drop-offs mit einem neuen Pick-up sowie einem neuen Drop-off kombiniert werden, wofür es (2t+2)! Möglichkeiten gibt. Für jedes Pick-up—Drop-off—Paar (t+1 Stück) ist der Pick-up bei der Hälfte der Möglichkeiten vor dem Drop-off. Bei der anderen Hälfte ist es umgekehrt. Daher muss die Gesamtzahl noch durch 2t+1 geteilt werden.

Nach Gleichung (2) führen kleine t-Werte zu einer geringen Anzahl von Kombinationen (z. B. sechs Kombinationen für t=1), größere t-Werte führen jedoch sehr schnell zu einer sehr großen Anzahl von Kombinationen (z. B. 2520 Kombinationen für t=3).

2.2.3 Ridepooling mit im Fahrzeug befindlichen und abzuholenden Fahrgästen

In diesem Fall verfügt ein Fahrzeug über einen im Fahrzeug befindlichen Fahrgast A und ist zwischenzeitlich auch einer Anfrage B (abzuholenden Fahrgast) zugeordnet. In diesem Moment geht eine neue Anfrage von Fahrgast X im System ein. Dieser Fall kann als Kombination der beiden vorherigen Unterfälle betrachtet werden. Da die Anzahl der Kombinationen auch bei kleinen Werten hoch ist, wird hier auf eine Auflistung der Kombinationen verzichtet. Abgesehen davon gilt unter der Annahme, dass i die Anzahl der im Fahrzeug befindlichen Fahrgäste und t die Anzahl der von einem Fahrzeug abzuholenden Fahrgäste ist, kann die Anzahl der Kombinationen so formuliert werden: 

Formel in der PDF

2.3 Darstellung eines Beispiels

Falls mehrere Fahrzeuge im System verfügbar sind, verfügt jedes Fahrzeug über eine bestimmte Anzahl an Kombinationsmöglichkeiten und alle diese Kombinationen werden innerhalb eines Pools miteinander verglichen, um die optimale Zuordnung zu ermitteln. Dies lässt sich anhand eines quadratischen Gitternetzes in Bild 1 veranschaulichen:

Bild 1: Darstellung einer beispielhaften Situation in einem quadratischen Gitternetz

Hier ist X die neue Anfrage, die von Xp nach Xd fahren möchte. Es gibt drei verfügbare Fahrzeuge im Netz, die Kreise zeigen die aktuellen Positionen der Fahrzeuge und die Buchstaben neben Kreisen stellen die Fahrgäste im Fahrzeug dar. Dreiecke zeigen die Abholpunkte der Anfragen und Quadrate die Ziele, beide haben die gleiche Farbe wie der entsprechende Kreis. Während Fahrzeug 1 derzeit stillstehend ist, befindet sich in Fahrzeug 2 ein Fahrgast (I) und bei Fahrzeug 3 ein Fahrgast, der abgeholt werden soll (T). In dieser Konstellation sind insgesamt 10 Optionen zu prüfen (Tabelle 1).

Bei jeder Option werden die Perspektive des Fahrgastes und die Perspektive des Betreibers analysiert. Beim Ridepooling gibt es für Fahrgäste vor allem zwei Nachteile: i) die Wartezeit auf das Fahrzeug, ii) die Umwegzeit aufgrund des Poolings. Während ein im Fahrzeug befindlicher Fahrgast nur unter letzterem leidet, leiden die neue Anfrage und ein abzuholender Fahrgast je nach Situation unter beidem. Im Allgemeinen wird eine „Akzeptanzrate“ für jeden entsprechenden Fahrgast und die neue Anfrage anhand der folgenden Formel berechnet:

Formel in der PDF

Der Durchschnitt der Akzeptanzraten der betrachteten Fahrgäste gibt einen Wert über die Perspektive des Fahrgasts an.

Aus Sicht des Betreibers besteht das Ziel jedoch darin, die Anfragen so weit wie möglich zu bündeln, was zur Berechnung einer Poolingrate führt:

Formel in der PDF

Die Gesamtpunktzahl einer Option wird dann durch die Addition der beiden Raten berechnet, was dann zu GP = AR_avg + PR führt. Je höher der GP-Wert ist, desto besser sind die Chancen für die Option.

Tabelle 1: Mögliche Optionen für die beispielhafte Situation

In Tabelle 1 sind zehn mögliche Optionen für drei verfügbare Fahrzeuge in Ridepooling zusammengefasst. Die Fahrzeugkapazität wurde mit 2 angenommen, die Fahrzeuggeschwindigkeiten wurden als gleich und konstant angenommen sowie die Ein-/Ausstiegszeiten wurden vernachlässigt. Für jede Option werden Akzeptanzraten (AR) für aktuelle und neue Fahrgäste, eine Poolingrate (PR) und ein Gesamtpunkt (GP) berechnet. Beispielsweise lässt sich Fahrzeug 2 mit der Option Xp-Id-Xd untersuchen, wo der aktuelle Fahrgast I (im Fahrzeug befindlichen) gerade eingestiegen ist. Für diesen beträgt die direkte Fahrzeit 12 Einheiten, die Fahrzeit im Fahrzeug auch 12 Einheiten und die Wartezeit 0 (da sich der Fahrgast bereits im Fahrzeug befindet). Dies führt zu einem AR von 1. Für die neue Anfrage hingegen beträgt die direkte Fahrzeit 4 Einheiten, die Fahrzeit im Fahrzeug 20, und die Wartezeit 4. Dies führt zu einem AR von 0,167. Die Poolingrate (PR) wird berechnet, indem die gesamten Fahrgastminuten (32 Einheiten) durch die gesamten Fahrzeugsitzminuten (24x2=48 Einheiten) geteilt werden, was zu 0,667 führt. Der Gesamtpunkt (GP) ist dann der Durchschnitt der AR-Werte plus PR, in diesem Fall 1,25. Beim Vergleich aller zehn GP-Werte stellt sich heraus, dass die Option mit 1,25 der beste Kandidat ist und mit der neuen Anfrage X gepaart wird.

Es gibt auch zwei Regeln im System, die zu einer Vorfilterung einiger Optionen führen. Dies sind die maximale Wartezeit (WZ) und die Umwegquote (UQ). Die maximale Wartezeit ist die maximal akzeptable Zeit, die ein Fahrgast nach dem Absenden einer Anfrage zur Abholung benötigt. Die Umwegquote ist das Verhältnis der tatsächlichen Fahrzeit (durch Bündelung erhöht) zur direkten Fahrzeit. Auch wenn sich Option 2 bei der Überprüfung der GP-Werte als die Beste herausstellte, ist zu beobachten, dass sie für den neuen Fahrgast einen großen Umweg mit sich bringt (UQneu=5). Unter der Annahme eines maximalen DR-Werts von 2,5 würde diese Option (sowie drei weitere Optionen) eliminiert und somit der ausgewählte Kandidat auf Option 3 (GP=1,15) geändert werden.

Nachdem die Optionen herausgefiltert werden, die gegen die beiden Regeln verstoßen, wird die Option mit dem höchsten GP ausgewählt. Falls unterhalb der Schwellenwerte keine Option mehr vorhanden ist, wird die Anfrage keinem Fahrzeug zugewiesen und daher abgelehnt.

2.4 Implementierung in einer mikroskopischen Verkehrssimulation

Wie bereits erwähnt, reichen Standardfunktionen der Mikrosimulation nicht aus, um die Besonderheiten von On-Demand-Systemen zu erfassen, dennoch bietet die Modellierung eines On-Demand-Systems in der Mikrosimulation viele Vorteile. Hierzu wurde die Simulationssoftware Vissim der Firma PTV AG [5] eingesetzt. Vissim bietet keine Standardlösung für On-Demand-Fahrzeuge, bietet jedoch eine externe Programmierung über eine Schnittstelle namens COM. Mit der COM-Schnittstelle können Codes wie in Python auf das Modell angewendet werden, was eine externe Steuerung des Systems ermöglicht.

Zunächst wurde die Simulation mit Netzwerkobjekten wie Straßen, Haltestellen, Lichtsignalanlagen und anderen Fahrzeugzuflüssen aufgebaut. Für eine dynamische Steuerung von Fahrzeugen waren zwei Dinge notwendig, a) die Option „Dynamische Umlegung“ wurde aktiviert und b) das Netzwerk wurde mit Knoten und Kanten versehen. Dieses Phänomen bezieht sich auf die Graphentheorie, bei der ein Graph aus Knoten und Kanten besteht. Knoten können als Verzweigungspunkte des Netzwerks (z. B. Kreuzungen) betrachtet werden und Kanten sind die Verbindungen zwischen ihnen. Nach diesem Schritt wurden die kürzesten Routen zwischen den Knoten durch Dijkstras Kürzester-Weg-Algorithmus (Shortest path algorithm) basierend auf diesen Knoten und Kanten berechnet [9]. Auf diese Weise wurden die Entfernungen zwischen der aktuellen Fahrzeugposition und den Abhol- & Zielpunkten berechnet und bildeten eine Grundlage für die Auswahl der besten Option.

Außerdem wurde der in den vorherigen Abschnitten erläuterte Matching-Algorithmus in Python implementiert. Dies wurde in der COM-Schnittstelle angewendet, hier mussten spezielle Aspekte berücksichtigt werden, z. B. mit welchen Objektattributen gearbeitet werden soll oder ob ein Fahrzeug an jedem Netzwerkpunkt sofort eine neue Route erhalten kann. Simulationsobjekte wurden bei Bedarf um neue Attribute erweitert (z. B. Fahrzeugstatus wie idle/empty-drive/occupied oder Leerfahrzeit eines Fahrzeugs zur Verwendung in weiteren Analysen).

Als letzter Schritt wurde ein beliebiger Anfragepool erstellt, der aus einzelnen Anfragen bestand, die die Informationen einer Starthaltestelle, einer Zielhaltestelle und des Zeitpunkts der Anfrage beinhalteten. Mit diesen Anfragen wurde das Simulationsmodell wiederum über die COM-Schnittstelle gespeist.

Die Mikrosimulation läuft dann mit diesen Eingaben, Anfragen werden den Fahrzeugen zugewiesen (oder sie werden abgelehnt), Fahrzeuge werden entsprechend ihrer Zuweisungen an verschiedene Standorte geschickt und schließlich liefert die Simulation Ergebnisse für die Analyse. Der Arbeitsablauf in der Simulation ist im folgenden Bild zusammengefasst:

Bild 3: Campus der Universität der Bundeswehr München mit 16 in roten Kreisen dargestellten Shuttle-Haltestellen

Basierend auf den Ein-/Ausgängen des Campus und den wichtigsten Campus-Standorten wurden 16 Shuttle-Haltestellen festgelegt. Haltestellen wurden in der Mikrosimulation als „Einzelparkplätze“ modelliert, um die dynamische Umlegung zu nutzen. Alle fünf Minuten wurden nach dem Zufallsprinzip Anfragen mit Start- und Zielpunkten generiert. Dieser Anfragepool wurde für alle Szenarien gleich verwendet, um einen Vergleich zu ermöglichen.

Die Shuttles starteten an zufällig ausgewählten Haltestellen und nutzten das Straßennetz des Campus, um Fahrgäste abzuholen und zum Ziel zu bringen. Da den Shuttles nicht das gesamte Netzwerk zur Verfügung steht (z. B. Fußgängerwege oder Netzwerk außerhalb des Campus), wurde bei der Definition der Infrastruktur eine Einschränkung über Straßentyp (Gehwege) und Knotentyp (Shuttle-relevante und -irrelevante Knoten) vorgenommen. Bei jeder neuen Anfrage wurden die aktuellen Positionen der Shuttles ermittelt und über den Algorithmus verschiedene Optionen berechnet, um die „beste“ Option zu finden. Die Optionen wurden durch die maximalen Wartezeiten, maximalen Umwegquoten und die Kapazität der Shuttles eingeschränkt, d. h. Optionen, die im Verlauf einer Shuttle-Tour zu einer Überschreitung der Shuttle-Kapazität führen, wurden nicht berücksichtigt. Nach der sofortigen Zuweisung eines Shuttles zur neuen Anfrage wurde die Shuttle-Tour (und deren Route) entsprechend aktualisiert.

Obwohl beim Ridehailing die Route eines Shuttles immer von einer Haltestelle zur anderen erfolgt, sind beim Ridepooling Routenänderungen unterwegs möglich, beispielsweise kann der Shuttle eine neue Anfrage entgegennehmen, bevor dieser den Fahrgast im Fahrzeug zum Ziel bringt. Hierzu wurden Routenänderungen auf ein fahrendes Shuttle angewendet, wobei der kürzeste Weg zwischen der aktuellen Shuttle-Position und dem neuen Ziel mithilfe des Dijkstra-Algorithmus berechnet wurde.

Aufgrund der Geschwindigkeitsbeschränkungen auf dem Campus und des geplanten autonomen Shuttle-Betriebs wurde eine Höchstgeschwindigkeit von 15 km/h angenommen. In dieser Studie wurden Rebalancing-, Relocation- oder Lade-/Betankungsstrategien nicht berücksichtigt.

In den vorangegangenen Kapiteln wurde bereits diskutiert, dass eine hohe Anzahl an im Fahrzeug befindlichen und/oder abzuholenden Fahrgästen sehr schnell zu einer Vielzahl von Kombinationen führen kann (siehe Gleichung 3). Aus diesem Grund wurde eine zusätzliche Einschränkung wie in [10] für die Fälle verwendet, in denen die Anzahl der Optionen über 10.000 war. Hier wurden die Kombinationen, die die vorherige Reihenfolge der Abhol- und Zielorte nicht erhalten haben, weggelassen. Zum Beispiel, wenn die aktuelle Reihenfolge eines Shuttles „T18P,T18D,I17D,T19P,T15P,T19D,T15D“ ist (T: abzuholender Fahrgast, I: im Fahrzeug befindlichen Fahrgast, die Zahlen sind die Anfrage-IDs) und eine neue Anfrage eintrifft (nämlich N20), beträgt die Anzahl der Optionen 22.680. In diesem Fall ist nur eine reine Einfügung möglich. Eine Option wie „T18P,T18D,I17D,N20P,T19P,N20D,T15P,T15D,T19D“ wird nicht mehr berücksichtigt, da die bisherige Reihenfolge geändert wurde (siehe die zwei letzten Elemente). Dadurch ließe sich die Anzahl der Kombinationen drastisch reduzieren.

Weitere in den Simulationsszenarien verwendete Parameter sind wie folgt:

• Ein-/Ausstiegszeiten: 30 Sekunden
• Höchstgeschwindigkeit der Shuttles: 15 km/h
• Simulationsdauer: 2 Stunden
• Anfragefrequenz: alle 5 Minuten
• Maximale Wartezeit: 10 Minuten
• Maximale Umwegquote: 4

In der Mikrosimulation wurden 4 Szenarien erstellt:

• Szenario I mit 1 Shuttle mit der Kapazität 1 (Ridehailing)
• Szenario II mit 1 Shuttle mit der Kapazität 3 (Ridepooling)
• Szenario III mit 2 Shuttles mit der Kapazität 1 (Ridehailing)
• Szenario IV mit 2 Shuttles mit der Kapazität 3 (Ridepooling)

Ziel war es, die Auswirkung der Betriebsart (Ridehailing vs. Ridepooling) und der Flottengröße auf wichtige Kennzahlen zu analysieren. Die Ergebnisse der Simulationen sind in der folgenden Tabelle zusammengefasst:

Tabelle 2: Ergebnisse der Simulationsszenarien

Aus den Ergebnissen lässt sich erkennen, dass die Anzahl der abgelehnten Anfragen stark von der Flottengröße sowie der Fahrzeugkapazität abhängt. Die höchste Zahl trat im Szenario I auf, wo ein Shuttle als Ridehailing eingesetzt wurde. Ein Drittel der insgesamt 24 Anfragen musste abgelehnt werden. Mit einem Wechsel der Betriebsart und einer Fahrzeugkapazität von 3 könnten drei der abgelehnten Anfragen erneut bedient werden. Eine Vergrößerung der Flottengröße (von einem Shuttle auf zwei) führte zu mehr bedienten Anfragen, im Ridehailing waren es 6 mehr und im Ridepooling 5 mehr.

Die durchschnittliche Besetzung wurde berechnet, indem die gesamten Personenkilometer durch die gesamten Fahrzeugkilometer dividiert wurden. Aufgrund der leeren Fahrten z. B. zur Abholung waren Werte unter 1 möglich. Hier zeigt sich, dass erwartungsgemäß die Betriebsart eine große Rolle für die durchschnittliche Besetzung spielte. Bemerkenswert ist, dass sich die Besetzung nur verdoppelt, obwohl die Fahrzeugkapazität verdreifacht wird. Darüber hinaus kam es von Szenario II zu Szenario IV zu einem Rückgang der durchschnittlichen Besetzung um 10 %. Dies kann daran liegen, dass durch einen Shuttle mehr Pooling gefördert wurde als durch zwei, und in Szenario II 5 Anfragen abgelehnt werden mussten, sodass die übrigen Fahrten in diesem Szenario kompakter durchgeführt wurden.

Die durchschnittliche Wartezeit war bei den Ridepooling-Szenarien geringer als beim Ridehailing. Durch die Bündelung können die Fahrgäste mit geringeren Wartezeiten rechnen, was als klarer Vorteil gesehen werden kann. Vergleicht man Szenario I-III oder II-IV, lässt sich auch der Effekt der Flottengröße beobachten, mit einem weiteren Fahrzeug können kürzere Wartezeiten erzielt werden.

In Szenarien mit Flottengröße 1 war die durchschnittlich zurückgelegte Strecke höher, was andeutet, dass ein effektiverer Service mit mehr Shuttles möglich sein könnte, selbst wenn weniger (oder keine) abgelehnte Anfragen vorliegen. Verschiedene Betriebsarten haben nahezu die gleichen durchschnittlichen Werte, dies kann jedoch an der Anzahl der bedienten Anfragen liegen. Beispielsweise wurden in Szenario 2 drei Anfragen mehr bedient als in Szenario 1 und in Szenario 4 zwei mehr als in Szenario 3.

Zusammenfassend lässt sich sagen, dass Ridepooling im Hinblick auf die Anzahl der bedienten Anfragen, die Wartezeiten und die durchschnittliche Besetzung Vorteile gegenüber dem Ridehailing aufweist. Auch die Flottengröße spielt eine Rolle, muss jedoch sorgfältig berücksichtigt werden, da die Betriebskosten mit der Flottengröße steigen.

In dieser Fallstudie wird vor allem darauf hingewiesen, dass unterschiedliche Betriebsarten in On-Demand-Shuttle-Systemen mit unterschiedlichen Parametrisierungen potenziell durch mikroskopische Verkehrssimulation analysiert werden können. Es ist beabsichtigt, eine ausführlichere Analyse mit mehr Szenarien und unterschiedlichen Parametersätzen durchzuführen. Neben dem entwickelten Matching-Algorithmus können auch andere Algorithmen angewendet und deren Leistungen anhand unterschiedlicher Kennzahlen verglichen werden.

4 Fazit und Ausblick

Ziel dieser Studie ist es, die Möglichkeit aufzuzeigen, On-Demand Shuttle-Systeme in einer mikroskopischen Verkehrssimulation zu modellieren. Da Anwendungen in diesem Bereich eher selten sind, kann eine Forschungslücke geschlossen werden. Durch den Einsatz einer solchen Plattform können verschiedene Dispositionsalgorithmen evaluiert werden, indem auch andere Verkehrsmodi berücksichtigt werden. Auch die Interaktion mit anderen Verkehrsmitteln, Haltestellenentwürfe und das Ein-/Aussteigen von Fahrgästen lässt sich mit dieser Plattform mühelos simulieren.

Eine wesentliche Analyse im Hinblick auf Dispositionsalgorithmen ist der Vergleich von Ridehailing und Ridepooling. Zusammen mit der Flottengröße wurden diese Betriebsarten in dieser Studie untersucht. Es wurde beobachtet, dass sich sowohl die Flottengröße als auch die Betriebsart (Fahrzeugkapazität) positiv auf die Bedienquote, Wartezeiten und Besetzung auswirken. Eine detailliertere Analyse unter verschiedenen Parametrisierungen ist Aufgabe weiterer Untersuchungen, wie beispielsweise verschiedene Flottengröße, Fahrzeugkapazität, maximale Wartezeit und maximale Umwegquote.

Ein weiteres potenzielles Feld für weitere Forschung zum Thema Matching-Algorithmus ist die Verwendung von Batch-Zuweisungsstrategien anstelle von spontanen Zuweisungen, wie in [10] und [11] durchgeführt. Bei der Batch-Zuweisung werden Anfragen in bestimmten Zeiträumen -und nicht spontan- zugewiesen, wobei effizientere Zuweisungen erwartet werden, da der Suchraum dann größer ist, was wiederum einen höheren Rechenaufwand bedeutet.

In dieser Studie wurde der Anfragepool sowohl hinsichtlich der Frequenz als auch der Start-Ziel-Beziehungen zufällig generiert. Der Universitätscampus weist jedoch hinsichtlich der Verkehrsnachfrage eigene einige Besonderheiten auf. Bestimmte Start-Ziel-Beziehungen sind häufiger anzutreffen, auch abhängig von der Tageszeit. Beispielsweise ist die Nachfrage zur Mensa zur Mittagszeit sehr hoch oder die Nachfrage von den Haupttoren zum Campus in den frühen Morgenstunden hoch. Ein Thema weiterer Forschung befasst sich mit diesem Aspekt und zielt darauf ab, die tatsächliche Nachfrage des Universitätscampus zu nutzen, um eine realistischere Modellierung zu ermöglichen.

Im aktuellen Algorithmus werden die kürzesten Wege basierend auf der Distanz zwischen Knoten berechnet. Ein idealer Ansatz wäre jedoch, auch die Verkehrssituation zu berücksichtigen. Ein Vorteil des Mikrosimulationstools ist, dass die aktuelle Verkehrssituation extrahiert, analysiert und die Gewichtungen der Kanten entsprechend angepasst werden können, was beispielsweise bei Staus zu einer teureren Kante führt. Auf diese Weise kann der Dijkstra-Algorithmus gezwungen werden, weniger überlastete Routen anstelle der kürzesten zu finden, was wiederum ein Thema für weitere Forschung sein kann.

5 Danksagung

Diese Forschungsarbeit wird durch dtec.bw – Zentrum für Digitalisierungs- und Technologieforschung der Bundeswehr gefördert. dtec.bw wird von der Europäischen Union – NextGenerationEU finanziert.

6 Literatur

[1]    H. Kloth, S. Mehler. (2018). Nachfragegesteuerte Verkehre oder On-Demand-Ridepooling? In Nahverkehr 06/2018, pp 36-39.

[2]    M. Kümmel. (2016). Taxis, Passengers and Stable Marriage – Stable simultaneous assignment of taxis to passenger booking requests. Dissertation in Technische Universität München.

[3]    F. Dandl, B. Bracher, K. Bogenberger. (2017). Microsimulation of an autonomous taxi-system in Munich. In 5th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), pp. 833–838.

[4]    O. Arslan, M. Reichert, A. Sellaouti, S. Hoffmann. (2021). Investigation of Personal Rapid Transit Station Capacities using Microscopic Traffic Simulation. In 7th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), pp. 191-196.

[5]    PTV AG. (2023). VISSIM Version 2023. Karlsruhe: PTV AG. Available at https://www.ptvgroup.com/de/loesungen/produkte/ptv-vissim/.

[6]    J.-F. Cordeau, G. Laporte. (2007). The dial-a-ride problem (DARP): Models and algorithms. Annals OR, vol. 153, pp. 29–46.

[7]    M.-G. Armellini. (2021). A Tool for Simulating Demand Responsive Transport System in SUMO. In 7th IEEE International Conference on Models and Technologies for Intelligent Transportation Systems (MT-ITS), pp. 425-429.

[8]    G. Wilkes, T. Hilgert, L. Briem, M. Kagerbauer, P. Vortisch. (2021). Mikroskopische Abbildung von Mobility on Demand im Verkehrsnachfragemodell mobiTopp. In HEUREKA –Optimierung im Verkehr und Transport.

[9]    K. Gkiotsalitis. (2022). Public Transport Optimization. ISBN 978-3-031-12443-3. Springer Publications, Switzerland.

[10] J. Alonso-Mora, S. Samaranayake, A. Wallar, E. Frazzoli, D. Rus. (2017). On-Demand High-Capacity Ride-Sharing via Dynamic Trip-Vehicle Assignment. Proceedings of the National Academy of Sciences, vol. 114, no. 3, p. 462–467.

[11] R. Engelhardt, F. Dandl, K. Bogenberger. (2020). Speed-up Heuristic for an On-Demand Ride-Pooling Algorithm. Available at https://arxiv.org/pdf/2007.14877v1.pdf.