von Lorenz Saathoff (Gewinner Masterpreis 2023)
Neuartige Konzepte des bedarfsorientierten Nahverkehrs (engl. Demand-Responsive Transport) werden im Sinne der Verkehrswende als vielversprechende Lösungsansätze für notwendige Veränderungen im Mobilitätssektor diskutiert. Zusätzlich zum Ausbau des ÖPNV muss dessen Attraktivität gesteigert werden, um Anreize für den Umstieg zu setzen und damit den Anteil des Umweltverbunds am Modal Split zu erhöhen. Die Ergebnisse der Studie [1] in Bezug auf die Einflüsse von Anreizen für einen Wechsel zeigen, dass eine bessere Anbindung im Sinne hoher Pünktlichkeit, Taktung und Flexibilität den größten Einfluss aufweist. Bei der Verbesserung des Anschlusses bisher noch nicht ausreichend erschlossener Gebiete können Dial-a-Ride-Services (DARS) einen wichtigen Beitrag leisten, welche in der mit dem Masterarbeitspreis der GOR ausgezeichneten Arbeit [2] näher betrachtet werden.
Solche bedarfsorientierten Verkehrsmittel zeichnen sich dadurch aus, dass Fahrgäste auf Basis mobiler Applikationen die Möglichkeit erhalten, Fahrten innerhalb des Geschäftsgebiets kurzfristig online zu buchen. Die Anbieter versuchen, die angefragten Fahrten möglichst zu bündeln, um eine optimale Auslastung der Fahrzeuge (zumeist Minibusse) zu gewährleisten, ohne den Reisenden zu starke Unannehmlichkeiten in Form von Umwegen und Wartezeiten zu bereiten. Anbieter solcher Dienste sehen sich mit dem in der Wissenschaft als Dial-a-Ride-Problem (DARP) bezeichneten Planungsproblem konfrontiert. In dessen Rahmen gilt es, zu entscheiden, welche Fahrtanfrage welchem Fahrzeug zugeordnet wird und in welcher Reihenfolge die Wagen die Fahrgäste bedienen sollten. Aufgrund operativer Einschränkungen und anderer Vorgaben, die das Finden einer im Sinne eines Ziels oder mehrerer Ziele optimalen Lösung erschweren, handelt es sich hierbei um ein komplexes Entscheidungsproblem.
Dienste als Zubringerverkehr zum klassischen ÖPNV bieten die Möglichkeit, Fahrgäste von ihrem Wunschort zu einer Anschlussstation des ÖPNV-Systems zu befördern und in umgekehrter Richtung, sodass die „letzte Meile“ komfortabel überwunden werden kann und die Fahrzeuge eine höhere Auslastung aufweisen als bspw. Linienbusse am Stadtrand.
Ein beispielhafter Routenausschnitt mit fünf Fahrtanfragen findet sich in Abbildung 1. Die Fahrgäste der Fahrtanfragen 1, 2 und 4 steigen an der Station S in das Fahrzeug und im Bediengebiet an ihren Wunschorten aus. Die Personen der Fahrtanfragen 3 und 5 hingegen werden unterwegs an den von ihnen spezifizierten Orten eingesammelt und steigen beim nächsten Erreichen der Station aus dem Fahrzeug. Dieses steht anschließend für die nächsten Fahrgäste bereit. In dem hier dargestellten Fall müssen alle Fahrten entweder an der Station beginnen oder enden, was ein in den ÖPNV integriertes System auszeichnet. Die Fahrtanfragen werden als multimodale Anfragen verstanden, d.h. die gesamte Route inkl. ÖPNV-Anteil wird angefragt. Damit steht ebenfalls die gewünschte Zeit für die Abholung von bzw. Ankunft bei der Station durch die Anschlussverbindung fest. Auf Basis dieser Informationen ergibt sich das Planungsproblem für das integrierte DARP, bei dem die Fahrplandaten für die Anschlüsse an der Station explizit berücksichtigt werden, um eine abgestimmte Reisekette zu bieten.
In der Masterarbeit wird zunächst die Literatur zu bestehenden Ansätzen und Problemformulierungen untersucht und in Bezug auf die in der Forschung hauptsächlich betrachteten Problemarten analysiert. Diese Betrachtung zeigt den Schwerpunkt der bisherigen Forschung auf. Viele Autorinnen und Autoren stellen neue oder adaptierte, exakte oder heuristische Lösungsmethoden für das DARP vor und bilden dabei viele reale Problematiken in den Modellen ab. Hierzu zählen zum Beispiel die Berücksichtigung von Zeitpräferenzen der Kundschaft, Zeitobergrenzen für Fahrzeiten und Kapazitätsbeschränkungen. Erstaunlich selten werden jedoch Services mit ÖPNV-Integration betrachtet, genauso wie Ansätze unter Berücksichtigung von Dynamik und Stochastik bei den Eingabedaten.
Weiterhin werden in der Arbeit die Ergebnisse einer Online-Recherche zu real existierenden DARS präsentiert. Der Fokus liegt hierbei darauf, die Gegebenheiten und Herausforderungen im Realbetrieb solcher Dienste herauszuarbeiten. Dafür wird ein Schema für die Klassifikation der Anwendungsbeispiele erarbeitet und die Klassifizierung vorgenommen. Die dabei berücksichtigten Merkmale sind die Betriebsgrundlage (privat oder mit öffentlichem Auftrag), die Ziele des Betriebs, die Art des Betriebsgebiets, der Grad der ÖPNV-Integration, die Art der Routenführung sowie die Verfügbarkeit von Buchungsmöglichkeiten im Voraus. Generell ist eine Mehrfachauswahl möglich, insofern diese sich inhaltlich nicht widersprechen.
Im Zuge der Recherche werden 45 Anbieter betrachtet, wobei die folgenden Kategorien pro Merkmal am häufigsten vorkommen. Zumeist operieren die Dienste mit einer öffentlichen Betriebsgrundlage und haben zum Ziel, eine Ergänzung zum bestehenden ÖPNV-System darzustellen, ohne dieses zu ersetzen. Viele der betrachteten Services begreifen sich als Pilotprojekte und sollen dazu beitragen, ein attraktives Gesamtangebot an Mobilitätsdienstleistungen zu schaffen. Die am häufigsten auftretenden Anwendungsgebiete sind Vororte gefolgt von Großstädten. Knapp die Hälfte der betrachteten Services sind sowohl auf Tarif- als auch anderen Ebenen mit dem bestehenden ÖPNV-System verknüpft. Lediglich 17 Services weisen keine Integration auf, wovon etwa die Hälfte auf privatwirtschaftlicher Basis betrieben wird und weitere drei auf Paratransit-Dienste fallen, welche als barrierefreie Alternative zum ÖPNV verstanden werden können und daher eine Integration nicht sinnvoll erscheint. Die meisten Anbieter stellen eine Möglichkeit für Buchungen im Voraus zur Verfügung.
Auf Grundlage der durchgeführten Untersuchungen wird ein fundierter Abgleich zwischen der Problembetrachtung in der Wissenschaft und den Bedürfnissen der Anbieter in der Praxis durchgeführt. Hierbei zeigt sich, dass in der Wissenschaft zumeist nur einzelne praxisnahe Aspekte bei den Modellierungen berücksichtigt werden, die Anbieter sich in der Praxis jedoch mit viel komplexeren Problemen konfrontiert sehen. Hieraus wird die Forderung abgeleitet, dass die Wissenschaft ihren Fokus auf den Praxisbezug vertiefen sollte, um den Bedürfnissen der Praxisanwendungen gerecht zu werden und die Unterschiede zwischen Modellen und Realität zu minimieren. Weiterhin wird eine große Diskrepanz bei der Betrachtung multimodaler Fahrten (z.B. Ridepooling + ÖPNV) in der Wissenschaft und deren Vorkommen in der Praxis identifiziert. Viele der DARS sind als Ergänzung zum ÖPNV konzipiert und werden oftmals auch von Verkehrsunternehmen betrieben. Sie sehen sich daher mit spezifischen Problemstellungen wie zum Beispiel der Abstimmung dynamisch agierender DARS mit nach statischen Fahrplänen operierenden Verkehrsmitteln des herkömmlichen Nahverkehrs konfrontiert. Wie bereits erwähnt wurde die Integration in den ÖPNV bisher kaum wissenschaftlich untersucht.
Vor dem Hintergrund der Erkenntnisse dieses Abgleichs und der Verbesserungsmöglichkeiten im Bereich des ÖPNV-Angebots wird in der Masterarbeit ein Modell für das DARP mit ÖPNV-Integration vorgestellt, das auf dem in [3] präsentierten aufbaut. Der verwendete realistische Anwendungsfall stellt einen Zubringerverkehr im Einzugsgebiet einer Bahnstation unter Berücksichtigung der relevanten Fahrplandaten des Schienenverkehrs dar. Als Zielstellung wird die Summe der Wartezeiten aller Fahrgäste minimiert. Für deren Bestimmung werden sowohl Umwege im Vergleich zur direkten Fahrt als auch Wartezeiten an der Station für jede Fahrtanfrage einbezogen und mit der Anzahl an Reisenden gewichtet. Das Modell kann mit einem Standardsolver zumindest für kleine Instanzen optimal gelöst werden. Aufgrund der hohen Problemkomplexität können größere Instanzen bisher nicht in vertretbarer Zeit optimal gelöst werden, sodass für diese ein auf der Idee des Simulated Annealing basierendes heuristisches Lösungsverfahren präsentiert wird. Mit letzterem können gute Lösungen in kurzer Zeit ermittelt werden. Für die durchgeführte Rechenstudie werden je 30 Beispieldatensätze für 14 Kombinationen aus verschiedenen Fahrzeug- und Fahrtanfragenanzahlen (k, n) zufällig erstellt. Diese basieren auf einem real existierenden potentiellen Bediengebiet um eine suburban gelegene S-Bahn-Haltestelle in den Hamburger Stadtteilen Lurup und Eidelstedt. Auf Basis der gefundenen Lösungen und der Plausibilitätsprüfungen kann festgestellt werden, dass die Modellformulierung geeignet ist, die beschriebene Problematik abzubilden und die Lösungen grundsätzlich auf die Realität übertragbar wären.
Mittels gemischt-ganzzahliger Optimierung können im direkten Vergleich zur Heuristik zwar teilweise Lösungen mit geringeren Zielfunktionswerten ermittelt werden, jedoch kann dieses Verfahren nur für einige Instanzen sehr geringer Größe überhaupt zulässige Lösungen in einem Zeitraum von zehn Minuten finden. Das exakte Verfahren erweist sich aufgrund dessen als eher untauglich im Sinne des Praxisbezugs. Die durch Anwendung des heuristischen Vorgehens erlangten Ergebnisse sind trotz etwas höherer Zielfunktionswerte im Kontext des realen Problems als gut anzusehen, da auch bei diesen nur geringe durchschnittliche und maximale Wartezeiten für die beförderten Personen auftreten. Die relative Variation der Zeiten innerhalb der Gruppe einer Parameterkombination ist geringer als bei den exakten Lösungen.
In Abbildung 2 sind die Mittelwerte der durchschnittlichen Wartezeit pro Person für jede getestete Parameterkombination (kk_nn) inkl. Standardabweichung dargestellt. Parameterkombinationen ohne vorhandene Lösung sind mit einem „–“ gekennzeichnet. Die durchschnittliche Poolingrate ist bei den Lösungen des heuristischen Verfahrens in jedem Fall höher, was für eine bessere Auslastung der Fahrzeuge spricht. Insgesamt kann das heuristische Vorgehen für jeden Datensatz zuverlässig ein gutes Ergebnis liefern, in einer quasi-vorhersagbaren Rechenzeit. Das exakte Verfahren kann Lösungen nur unzuverlässig bereitstellen. Zudem sind im Vergleich zur Heuristik die Rechenzeiten sowie die benötigten Rechenkapazitäten zumeist um ein Vielfaches höher. Aufgrund der Abwägung des jeweiligen Aufwands und Nutzens beider Verfahren wird für den tatsächlichen Betrieb eines solchen Dial-a-Ride-Dienstes für die Nutzung dieses oder eines anderen heuristischen Verfahrens plädiert, um zuverlässig und schnell Ergebnisse für die Planung zu erhalten.
Eine verbesserte Modellformulierung sowie das Entwickeln ausgefeilter heuristischer Ansätze ist vielversprechend und sollte künftig verfolgt werden. Wir arbeiten aktuell daran, für den hier aufgezeigten Anwendungsfall eine auf Events basierte Formulierung ausgehend von der in [4] vorgestellten zu entwickeln, mithilfe der auch größere Instanzen potentiell optimal gelöst werden können.
Abschließend bedanke ich mich bei der GOR und dem Komitee für die Auszeichnung sowie bei Arne Schulz und Malte Fliedner für die hervorragende Betreuung der Arbeit.
Literatur
- Römer, D. & Salzgeber, J. (2022). Verkehrswende in Deutschland braucht differenzierte Ansätze in Stadt und Land. Online verfügbar unter: https://www.kfw.de/PDF/Download-Center/Konzernthemen/Research/PDF-Dokumente-Fokus-Volkswirtschaft/Fokus-2022/Fokus-Nr.-363-Januar-2022-Verkehrswende.pdf (zuletzt geprüft: 17.08.2023 um 12:20 Uhr).
- Saathoff, L. A. (2022). Das Dial-a-Ride-Problem in Wissenschaft und Praxis: Analyse von Anwendungen als Ergänzung zum ÖPNV [Masterarbeit]. Universität Hamburg.
- Ropke, S., Cordeau, J.-F. & Laporte G. (2007). Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks 49(4):258–272.
- Gaul, D., Klamroth, K., Pfeiffer, C., Schulz, A. & Stiglmayr, M. (2023). A Tight Formulation for the Dial-a-Ride Problem. [Unveröffentlichtes Manuskript in Vorbereitung]. DOI: 10.48550/arXiv.2308.11285.
Kontakt: Lorenz Alexander Saathoff, Universität Hamburg, lorenz.alexander.saathoff@uni-hamburg.de