Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität.

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

1 Einleitung

In modernen Nahverkehrssystemen stehen den Fahrgästen Routenplanungssysteme mit Echt- zeitinformationen zur Verfügung, mit denen jederzeit, sogar während der Fahrt, die beste Ver- bindung bestimmt werden kann. Man kann deshalb davon ausgehen, dass die Nutzer ihre Fahrtrouten in Abhängigkeit vom Fahrplan bestimmen, um die Reisezeit und die Umsteigevorgänge zu optimieren. Das gilt auch für vertaktete Systeme. Dort muss man nach einem knapp verpassten Anschluss sogar immer die ganze Taktzeit warten, bis das nächste Fahrzeug kommt – ärgerlich. Wenn ein Fahrplan zu einem solchen “schlechten Anschluss” führt, wird ein Fahrgast auch einen längeren Fahrweg in Kauf nehmen, um trotzdem insgesamt schneller ans Ziel zu kommen.

In der Routing-Literatur zum öffentlichen Nahverkehr wird aus diesem Grund das Verhalten von Passagieren auf einer detaillierten Ebene umfassend untersucht, siehe den Übersichtsartikel von Fu, Liu & Hess (2012) [1], und es gibt heute Modelle, mit denen sich die Routenwahl sehr gut vorhersagen lässt [14].

In der Optimierungsliteratur zur periodischen Taktfahrplanung ist das anders. Bis in die jüngste Zeit wurden nur statische Modelle betrachtet. Diese basieren auf der Annahme, dass die Passagiere auf festen, vom Fahrplan unabhängigen Fahrtrouten reisen [8, 7, 5, 4]. Realistischere Lösungen können mit iterativen Verfahren bestimmt werden [10], bei denen ein (statisches) Fahrplanungserfahren mit einem Routing-Verfahren kombiniert wird. Die vollständige Integration des Passagierroutings in die Fahrplanung wird erst seit kurzem betrachtet. Schmidt & Schöbel (2014) [9] bestimmen die Komplexität im aperiodischen Fall und entwickeln ein Lösungsverfahren für eine Variante, in der die erste und letzte Fahrt eines Passagiers fest vorgegeben ist. Für den periodischen Fall schlägt Lübbe (2009) [6] ein quadratisches Modell vor, das er linearisiert. Siebert & Goerigk (2013) [12] vergleichen einen integrierten und einen iterativen Ansatz und geben Fehlerschranken an. Laumanns, Szabo & Voegeli (2016) [3] schlagen ein Bilevel-Modell vor, das sie mit einer direkten MIP-Formulierung vergleichen. Wir [2] haben gezeigt, dass eine Nichtbeachtung und auch eine iterierte Behandlung des Passagierverhaltens im Vergleich zu einer integrierten Vorgehensweise theoretisch zu beliebig schlechten Lösungen führen kann.

Bild 1: Ausschnitt aus dem Nahverkehrsnetz von Wuppertal nahe des Hauptbahnhofs: Buslinien 622 und 628 und S-Bahn Linie 9

Wir stellen in dieser Arbeit einen Ansatz zur periodischen Taktfahrplanung mit integriertem Passagierrouting vor, der auf gemischt ganzzahliger Programmierung beruht. Wir zeigen anhand des Nahverkehrsnetzes der Stadt Wuppertal, dass sich damit erhebliche Reisezeitgewinne erzielen lassen. Insbesondere kann die Umsteigewartezeit, die von den Passagieren als besonders negativ empfunden wird, bei typischen Annahmen über das Nutzerverhalten um knapp 9% reduziert werden. In einer Analyse wichtiger System- und Verhaltensparameter zeigen wir am gleichen Anwendungsbeispiel, dass die Mindestumsteigezeit von besonderer Bedeutung ist und dass man mit gebotener Sorgfalt einen Fahrplan bestimmen kann, der die Beförderungsqualität für die Mehrheit der Nutzer verbessert.

2 Beispiel

Die Bilder 1–3 illustrieren den Nutzen einer integrierten Betrachtung von Fahrplankonstruktion und Passagierverhalten anhand eines realen Beispiels.

Bild 1 zeigt einen Ausschnitt aus dem Nahverkehrsnetz der Stadt Wuppertal mit zwei Bus- und einer S-Bahn-Linie nahe des Hauptbahnhofs. Der Netzausschnitt ist schematisch als Graph dargestellt. Die Knoten repräsentieren Haltestellen, die durchgezogenen Kanten sind direkte Verbindungen zwischen Haltestellen, die gestrichelten Kanten stellen Umsteigemöglichkeiten zwischen zwei Linien an einer Haltestelle dar. Die Zahlen an den Kanten geben Fahr- bzw. Wegezeiten an. Alle drei Linien verkehren im 20-Minuten-Takt (T = 20). Wir betrachten zwei Fahrgäste. Der erste Fahrgast möchte vom Hauptbahnhof zur Schützenstraße fahren, der zweite von der Greifswalder Straße nach Langerfeld.

Bild 2: Periodischer Taktfahrplan 1: Umsteigen in Barmen

Bild 3: Periodischer Taktfahrplan 2: Umsteigen am Hauptbahnhof

Bild 2 zeigt einen Fahrplan, der auf den ersten (blauen) Fahrgast zugeschnitten ist; die Ankunfts- und Abfahrtszeiten (im Beispiel gleich) sind dabei in den Knoten notiert. Wenn die Buslinie 628 zu Minute 11 in Barmen ankommt und die Buslinie 628 zu Minute 16, kann der blaue Fahrgast bestmöglich in 5 Minuten umsteigen, um in nur 17 Minuten zur Schützenstraße zu kommen. Der zweite (rote) Fahrgast muss beim Umsteigen in die S-Bahn immer lange warten. Noch am besten ist der Umstieg in Barmen in 15 Minuten. Er braucht trotzdem geschlagene 55 Minuten ans Ziel. Beide Passagiere zusammen reisen 72 Minuten. Man kann sich überlegen, dass dieser Fahrplan bestmöglich ist, wenn die Reisewege für beide Passagiere wie im Beispiel fixiert werden. Einmal eingeführt, würde sich dieser Fahrplan bei statischer und auch bei iterierter Planung verfestigen. Trotzdem ist er nicht global optimal.

Bild 3 zeigt einen besseren Fahrplan. Dieser ist auf den roten Passagier zugeschnitten, der jetzt im Hauptbahnhof bestmöglich in 13 Minuten vom Bus 628 auf die S9 umsteigen kann. Er braucht dann nur noch 36 Minuten bis nach Langerfeld. Der blaue Passagier wählt bei diesem Fahrplan den Bus 622 und fährt in 20 Minuten zur Schützenstraße, drei Minuten langsamer als vorher. Beide Passagiere zusammen benötigen nur noch 56 Minuten, insgesamt wesentlich weniger als vorher. Auch dieser Fahrplan ist bei fixierter Routenwahl bestmöglich.
Das Beispiel zeigt, dass bei falscher Einschätzung des Routenwahlverhaltens auch in realen Nahverkehrsnetzen bei der Fahrplanung erhebliche Fehler entstehen können. Diese können zu großen Reisezeitverlusten der Passagiere führen. Fahrplanung und Routenwahl der Passagiere sollten deshalb integriert betrachtet und optimiert werden.

3 Mathematisches Modell

Die periodische Taktfahrplanung (bei festem Passagierrouting) wird nach Serafini & Ukovich (1989) [11] klassisch als Periodic Event Scheduling Problem (PESP) modelliert. Dazu wird ein Ereignis-Aktivitäts-Netzwerk N = (V, A) konstruiert, dessen Knoten Ankünften und Abfahrten von Fahrzeugen entsprechen, während die Kanten Aktivitäten wie Fahren, Warten, Gehen, Umsteigen etc. modellieren. Ein periodischer Taktfahrplan ordnet dann jedem Knoten v ∈ V eine Zeit zu, wobei T eine Taktzeit oder Periode ist, nach der sich der Fahrplan wiederholt. Der Fahrplan ist zulässig, wenn für die Länge xa jeder Kante a = (u, v ) ∈ A die periodischen Intervallbedingungen

Formel (1) siehe PDF.

wobei fa und ua untere und obere Schranken für die Dauer einer Aktivität darstellen. Die Dauern der Aktivitäten summieren sich entlang eines Kreises in N immer zu einem Vielfachen der Taktzeit auf, so dass das System (1) mit Hilfe einer geeigneten Kreisbasis Γ in der Form

Formel (2) siehe PDF.

geschrieben werden kann. Die Nachfrage ist üblicherweise als “Quelle-Ziel-Matrix” (OD-Matrix) gegeben; wir definieren als D die Menge aller Quelle-Ziel-Knoten mit positiver Nachfrage, d.h.. Wird der Passagierfluss mit Hilfe von Pfadvariablen y auf einer Pfadmenge ausgedrückt, kann das integrierte Fahrplanungs- und Passagierrouting-Problem (TTP) wie folgt formuliert werden:

Formel siehe PDF.

Das TTP ist ein modulares ganzzahliges Programm mit bilinearer Zielfunktion, das durch eine Zeitexpansion in ein ganzzahliges lineares Programm transformiert werden kann. Dazu wird ein zeitexpandiertes Ereignis-Aktivitäts-Netzwerk betrachtet, in dem für jeden Knoten/jedes Ereignis v ∈ V insgesamt T Kopien erzeugt werden. Jede Kopie steht für einen eindeutigen Ereigniszeitpunkt, d.h.

Formel siehe PDF.

Bild 4: Unterschiedliche Modellierung einer Station mit zwei Linien (blau und rot). Passagie-re können zwischen den Linien Umsteigen

Für jede Aktivität a ∈ A enthält das zeitexpandierte Netzwerk je eine Kante zwischen allen zeitbezogenen Ereignis-Knoten, die die periodischen Intervallbedingungen (1) erfüllen, d.h.
Für jede Aktivität ergibt sich die Dauer als. Die Dauer für einen (Passagierreise-)Pfad ergibt sich dann als

Formel siehe PDF.

Abbildung 4(a) zeigt einen Ausschnitt aus einem Ereignis-Aktivitäts-Netzwerk N, 4(b) zeigt das entsprechende zeitexpandierte Ereignis-Aktivitäts-Netzwerk für T = 4. Die Festlegung der Ankunfts- und Abfahrtszeitpunkte auf einer Linienroute r ∈ R entspricht der Auswahl eines Pfades in diesem zeitexpandierten Graphen. Im Beispiel in Abbildung 4(b) stellen die dicken roten und blauen Kanten mg¨liche Orts-Zeit-Pfade für die rote bzw. blaue Linie dar. Formal sei v (r , 1) ∈ V der Startknoten für Linienroute die Menge aller zugehörigen zeitexpandierten Knoten/Ereignisse und deren Vereinigung über alle Linienrouten. Außerdem bezeichnen wir mit alle Linienaktivitäten, d.h. alle Aktivitäten bis auf das Umsteigen. Ein zeit-expandiertes Modell (XTTP) für das integrierte Fahrplanungs- und Passagierrouting-Problem kann dann wie folgt formuliert werden:

Formel (3) bis (8) siehe PDF.

Ungleichungen (3) und (4) beschreiben einen Fluss von Linienrouten, Ungleichungen (6) den Passagierfluss. Die Kopplungs-Ungleichungen (5) stellen sicher, dass die Passagierrouten nur die Aktivitäten benutzen, die von Linienrouten überdeckt sind. Die Passagierflussvariablen können dynamisch mit Hilfe eines Spaltenerzeugungsalgorithmus generiert werden.

Falls für die obere und untere Schranke einer Aktivität gilt, so enthält das zeitexpandierte Netzwerk für diese Aktivität viele Kanten. Dies gilt zum Beispiel für alle Umsteige-Aktivitäten, die keine echte obere Schranke besitzen. Durch die Verwendung von Warteknoten und Wartekanten, kann die Anzahl der benötigten Kanten aber auf eine lineare Anzahl von 3T reduziert werden, siehe dazu Abbildung 4(c).

4 Optimierung Wuppertal

In diesem Abschnitt vergleichen wir zwei Taktfahrpläne für den Kern des Nahverkehrsnetzes 2013 von Wuppertal, um den Effekt einer integrierten Betrachtung von Fahrplanung und Passagierrouting zu quantifizieren. Der erste Fahrplan, der Referenzfall, wurde auf Basis eines festen Passagierroutings berechnet (siehe unten). Der zweite Fahrplan wurde mit Hilfe unseres integrierten Taktfahrplanungs- und Passagierrouting-Modells XTTP berechnet.

Das Kernnetz der Wuppertaler Stadtwerke (WSW) beinhaltet 158 Stationsknoten, 229 OD-Knoten und 460 gerichtete Kanten. Es gibt insgesamt 71 Linien: 67 Buslinien, drei Regionalzüge und die berühmte Schwebebahn. Die Linien werden mit unterschiedlichen Taktfrequenzen betrieben: sie fahren alle 10, 15, 20, 30 oder 60 Minuten. Die Ankunfts- und Abfahrzeiten der Regionalzüge sind gegeben und werden fixiert. Damit können sie bei der Berechnung von Umsteigezeiten berücksichtigt werden.

Wir fixieren außerdem die Haltezeiten der Linien an den Stationen und die Fahrzeiten der Linien zwischen den Stationen. Damit hat die Gestalt des Taktfahrplanes nur einen Einfluss auf Passagiere, die umsteigen müssen. Wir können daher alle Quelle-Ziel-Paare (OD-Paare) mit einer direkten Verbindung, die gleichzeitig schnellstmöglich ist, entfernen. Es verbleiben dann noch 40 793 OD-Paare mit einer positiven Nachfrage. Uns stehen noch keine detailierten Daten über Mindestumsteigezeiten zur Verfügung. Daher nehmen wir pauschal für einen Umstieg eine Mindestdauer von 4 Minuten an, d.h., es können nur Anschlüsse von Linien erreicht werden, die mindestens 4 Minuten später abfahren. Gleichzeitig bestrafen wir einen Umstieg ähnlich wie in den Vorgaben der standardisierten Bewertung [13] mit 8 zusätzlichen Minuten (wir verzichten auf eine weitere zusätzliche Bestrafung in Abhängigkeit von einer Teilwegezeit).

Aus dem Kernnetz von Wuppertal konstruieren wir ein zeitexpandiertes Ereignis-Aktivitäts-Netzwerk mit 1 927 120 Ereignissen und 4 416 008 Aktivitäten. Das zugehörige ganzzahlige Programm hat 4 018 binäre Linienvariablen, die den Taktfahrplan modellieren. Für den Referenzfall fixieren wir die Fahrtrouten der Passagiere auf die kürzesten Pfade bezüglich des Taktfahrplans der WSW aus dem Jahr 2013 (WSW2013). Im integrierten Fall werden die Pfadvariablen für den Passagierfluss dynamisch mit Hilfe eines Spaltengenerierungsalgorithmus bestimmt, welcher im Pricing-Schritt ein kürzeste-Wege-Problem löst. Die Zielfunktion ist für beide Modelle die Minimierung der gewichteten Gesamtreisezeit aller Passagiere. Für die Rechnungen setzen wir ein Zeitlimit von 12 Stunden.

Der Referenz-Taktfahrplan WSW2013 liefert für die von uns gewählten Parameter eine gewichtete Gesamtreisezeit von knapp 4.207 Mio Minuten und eine gewichtete Umsteigewartezeit von 652 Tausend Minuten. Bild 5 stellt links die Umsteigewartezeiten an den Haltestellen des Kernnetzes dar. Die Fläche der Kreise ist proportional zur Anzahl der Umsteiger, die Farbe illustriert die Wartezeit, wobei dunkelgrün gering und rot hoch ist. Der von uns berechnete Taktfahrplan hat eine gewichtete Gesamtreisezeit von ca. 4.119 Mio Minuten und eine gewichtete Umsteigewartezeit von 594 Tausend Minuten (die Lösung hat eine Dualitätslücke von etwa 6.5%.). Das entspricht einer Verbesserung von 2.1% in Bezug auf die Reisezeit und von 8.9% in Bezug auf die Umsteigewartezeit. Diese Lösung ist in Abbildung 5 rechts dargestellt. Die meisten Umsteigevorgänge finden am Hauptbahnhof statt. Abbildung 6 zeigt die Umsteigebeziehungen zwischen den einzelnen Linien am Hauptbahnhof etwas detaillierter, und zwar links für den Referenzplan und rechts für den integriert optimierten Plan. Hierbei sind die Linien sowohl links als auch rechts in jeder Abbildung als kleine Knoten dargestellt. Es gibt eine Verbindung zwischen einer Linie links zu einer Linie rechts, wenn Passagiere von nach umsteigen. Die Dicke der Verbindung entspricht der Anzahl umsteigender Passagiere, die Farbe wieder der Umsteigewartezeit, wobei dunkelgrün der geringsten Wartezeit entspricht und rot der höchsten. Neben einer Farbveränderung zu mehr dunkelgrün für den optimierten Fahrplan kann man auch Verstärkungen auf einigen Umsteigebeziehungen erkennen, und zwar sowohl im Sinne einer Bündelung auf wichtigen Umsteigebeziehungen, als auch in Bezug auf die Ge- samtanzahl. In der Tat gibt es im Referenzplan 58 969 Umsteigevorgänge und im optimierten Fahrplan 59 741; dies entspricht einer Erhöhung von ca 1.3%. Diese Steigerung lässt sich damit erklären, dass bei einer Taktfahrplanoptimierung gerade die Umsteigewartezeiten optimiert werden und Umstiege damit wieder etwas attraktiver werden.

Bild 5: Umsteigewartezeiten in Wuppertal: Optimierter Taktfahrplan bei festem (links) und integriertem (rechts) Passagierrouting. Die Umsteigewartezeit verringert sich umknapp 9%

Insgesamt bestätigt sich am Beispiel des Kernnetzes von Wuppertal der erhebliche Einfluss des Taktfahrplans auf das Routenwahlverhalten der Passagiere. Das Potential einer integrierten Optimierung ist erheblich: Allein durch eine Verschiebung der Taktanfangszeiten der Linien lässt sich die Umsteigewartezeit um fast 9% reduzieren.

Bild 6: Detailierte Umsteigebeziehungen zwischen den einzelnen Linien am HauptbahnhofWuppertal für den Referenzplan (links) und den optimierten Taktfahrplan (rechts)

5 Systemparameter und Nutzerverhalten

Die Ergebnisse einer Taktfahrplanoptimierung hängen von verschiedenen Parametern ab, insbesondere von den unteren und oberen Schranken an die Dauern von Aktivitäten wie Fahren, Warten, Umsteigen. Diese Parameter wollen wir in diesem Abschnitt genauer untersuchen.

Während die Schranken an die Linienfahrzeiten zwischen zwei Stationen im Allgemeinen von der Länge der Strecke und der Geschwindigkeit des Fahrzeugtyps abhängen und damit recht einfach als technische Parameter bestimmt werden können, sind die unteren Schranken an die Umsteigezeiten problematischer zu ermitteln, da sie von Präferenzen verschiedener Nutzergruppen abhängen. Wenn Bahnsteige gewechselt und Treppen überwunden werden müssen, kann die Mindestumsteigezeit für verschiedene Passagiere sehr unterschiedlich sein. Hinzu kommen noch die persönlichen Vorlieben in Bezug auf zuverlässige Anschlüsse mit mehr oder weniger Puffer zum Ausgleich möglicher Verspätungen.

Wäre im Eingangs gezeigten Beispiel die untere Schranke an die Umsteigezeit im Hauptbahnhof 12 Min, so würde der rote Passagier im Taktfahrplan 1 (Abbildung 2) die Route über den Hauptbahnhof wählen und wäre in 35 Minuten am Ziel. Sowohl der rote als auch der blaue Passagier reisten dann im Taktfahrplan 1 auf bestmöglichen Routen; dies war vorher nicht der Fall. Bereits dieses einfache Beispiel zeigt, dass die untere Schranke an die Umsteigedauer (für alle Umsteigeaktivitäten) einen großen Einfluss auf den Fahrplan haben kann und damit einen ersten wichtigen Parameter darstellt.
Für die Berechnungen in Abschnitt 4 haben wir als zweiten Parameter eine pauschale Umsteigestrafe von 8 = b ≥ 0 Min pro Umstieg veranschlagt. Je höher diese Strafe, desto unattraktiver werden Verbindungen mit Umstiegen.

Neben einer pauschalen Strafe (und alternativ, aber ähnlicher zur standardisierten Bewertung) könnte man die Umsteigestrafe auch abhängig von der Gesamtdauer des Umsteigevorgangs machen. Die Idee dabei ist, dass ein Umstieg, der lange dauert, weil z.B. der Anschluss nicht gut klappt, besonders schlecht bewertet werden soll. Dazu kann man die Umsteigezeit mit einem Faktor β ≥ 1 gewichten; diesen Faktor wollen wir als dritten Parameter betrachten.

Die Zeitdauer einer Umsteigekante ergibt sich mit diesen drei Parametern f, b und β wie folgt:

Formel siehe PDF.

Im folgenden wollen wir den Einfluss von f, b und β auf die Taktfahrplanoptimierung genauer untersuchen. Dazu betrachten wir drei Untersuchungsfälle, in denen immer nur einer der drei Parameter variiert wird:

- In Fall (A) berechnen wir optimale Taktfahrpläne für verschiedene Werte an eine gemeinsame untere Schranke f für alle Umsteigekanten; dieser Wert entspricht der minimal möglichen Umsteigezeit. Der Bestrafungsparameter für einen Umstieg b und der Gewichtungs- faktor für die Gesamtumsteigezeit β bleiben dabei konstant. Die genauen Werte der Parameter sind.

- In Fall (B) berechnen wir optimale Taktfahrpläne für verschiedene Werte an die pauschale Umsteigestrafe b. Die anderen beiden Parameter bleiben dabei konstant. Die genauen Werte der Parameter sind.

- In Fall (C) berechnen wir optimale Taktfahrpläne für verschiedene Werte an den Gewichtungsfaktor für die Gesamtumsteigezeit β. Die anderen beiden Parameter bleiben dabei konstant. Die genauen Werte der Parameter sind β ∈ {0, 1.05, 1.1, 1.15, 1.2, 1.25, 1.3, 1.4,
1.5, 2}, f = 4 und b = 8.

Tabelle 1: Gesamtreisezeit für verschiedene untere Schranken an die Umsteigedauer

Tabelle 2: Gewichtete Anzahl an Gesamtumstiegen für verschiedene untere Schranken an die Umsteigedauer

Für jeden der Untersuchungsfälle können wir aus theoretischer Sicht genauso viele verschie- dene (optimale) Taktfahrpläne erhalten wie es verschiedene Parameter gibt. Im Fall (A) wären das maximal 11, im Fall (B) 9 und im Fall (C) 10 verschiedene optimale Taktfahrpläne.

Für Fall (A) haben wir in der Tat 11 verschiedene Taktfahrpläne berechnet. Jeder dieser Taktfahrpläne realisiert für eine feste minimale Umsteigedauer eine beste Gesamtfahrzeit unter der Annahme, dass die Mindestumsteigezeit tatsächlich die Mindestumsteigezeit für alle Passagiere darstellt. Falls dies für alle oder auch nur einige Gruppen von Passagieren nicht der Fall ist (in der Praxis ist das natürlich der Fall), verschlechtert sich das Ergebnis. Im Extremfall stünde sogar die Validität des Optimierungsansatzes an sich in Frage. Denn wenn eine Optimierung für eine Nutzergruppe alle anderen Nutzer unverhältnismäßig benachteiligen würde, sollte man eher einen Minimax-Ansatz wählen.

Um diesen Fehler zu quantifizieren, haben wir jeden der 11 optimierten Taktfahrpläne bewertet, indem wir 11 Passagierroutings auf Basis aller 11 möglichen Werte für die Minimaldauer eines Umsteigevorgangs berechnen, d.h., wir optimieren den Taktfahrplan für eine bestimmte Mindestumsteigezeit und bewerten diesen Plan, indem wir optimale Passagierrouten für alle anderen Mindestumsteigezeiten berechnen. Auf diese Weise können wir herausfinden, welcher Fehler entsteht, wenn man falsche Annahmen in Bezug auf die Mindestumsteigezeiten macht.

Einen Auszug von Ergebnissen dieser Berechnungen zeigen die Tabellen 1 in Bezug auf die Gesamtreisezeit und 2 in Bezug auf die Umsteigehäufigkeiten. Jede Zeile entspricht einem Taktfahrplan, der für die Mindestumsteigezeit in der jeweils ersten Spalte optimiert wurde. Jede Spalte entspricht einer Bewertung verschiedener Taktfahrpläne in Bezug auf die Mindestumsteigezeit, die jeweils in der ersten Zeile angegeben ist.

Bild 7: Gesamtfahrzeit (links) und Anzahl an Gesamtumstiegen (rechts) für verschiedene untere Schranken an die Umsteigedauer. Hierbei repräsentiert jede Farbe einen Fahrplan, der für eine bestimmte untere Schranke an die Umsteigedauer optimiert wurde

In Tabelle 1 sind die Diagonalelemente minimal (blau), d.h., die Gesamtreisezeit ist minimal, wenn die Bewertung mit der gleichen Mindestumsteigezeit erfolgt, mit der der Taktfahrplan optimiert wurde. Auffällig ist auch, dass in der zweiten Tabelle 2 die Diagonalelemente jeweils die größten Werte (rot) in ihrer jeweiligen Spalte annehmen, d.h., im optimierten Plan steigen auch die meisten Fahrgäste um. Dies ist (zumindest auf den zweiten Blick) aber logisch, denn bei der Optimierung von Taktfahrplänen wird ja gerade versucht, eine minimale Umsteigezeit zu erreichen. Ein Fahrplan, der für eine bestimmte minimale Umsteigezeit optimiert wurde, enthält daher möglichst viele Verbindungen, die diese minimale Umsteigezeit auch realisieren. Ein Fahrplan, der für eine höhere oder niedrigere minimale Umsteigezeit optimiert wurde, hat auf diesen Verbindungen zuviel Zeit eingeplant oder die Anschlüsse sind zu knapp, können nicht erreicht werden und beinhalten daher ebenfalls eine zusätzliche Wartezeit. Dadurch werden Verbindungen mit weniger Umstiegen wieder attraktiver, insgesamt steigt aber die Gesamtreisezeit.

In Abbildung 7 sind die Ergebnisse zum Untersuchungsfall (A) für alle Parameterkombinationen grafisch dargestellt. Die Kurve für den Fahrplan, der für f = 8 optimiert wurde, ist etwas hervorgehoben. Man kann gut erkennen, dass beide Kurven (für Gesamtfahrzeit und Gesamtumstiege) bei der Bewertung für f = 8 einen Knick haben, der die minimale Gesamtfahrzeit bzw. die höchsten Gesamtumstiege anzeigt. Die Kurven für alle anderen Parameterwerte sind ähnlich: Die Bewertung eines Fahrplans mit der gleichen Mindestumsteigezeit, mit der er auch berechnet wurde, liefert die minimale Gesamtreisezeit und die maximale Umsteigehäufigkeit. Mit steigender unterer Schranke an die Umsteigedauer nehmen die Umsteigehäufigkeiten ab.

Die Kurven liegen alle relativ nahe beieinander. Man kann allerdings erkennen, dass gerade dann der Fehler am größten ist, wenn die Mindestumsteigedauer knapp zu tief angesetzt wurde, d.h., wenn z.B. der Taktfahrplan mit f = 8 optimiert wurde, aber die Bewertung mit f = 10 erfolgt. Anders ist das bei der Bewertung mit f = 6. Ein für f = 8 optimierter Fahrplan ist prinzipiell auch gut für Nutzer, die etwas zügiger umsteigen. Man sollte daher die Mindestumsteigezeit bei der Optimierung lieber etwas überschätzen anstatt unterschätzen. Dies ist auch intuitiv klar, da man bei einer Mindestumsteigezeit, die in der Bewertung knapp über dem Wert für die Fahrplanoptimierung liegt, mit den meisten ganz knapp verpassten Anschlüssen rechnen muss, nach denen man besonders lange warten muss.

Bild 8: Gesamtfahrzeit (links) und Anzahl an Gesamtumstiegen (rechts) für verschiedene (zusätzliche) pauschale Strafzeiten pro Umstieg

Bild 9: Auswertung der Gesamtfahrzeit (links) und der Anzahl an Gesamtumstiegen (rechts) für verschiedene Gewichtungsfaktoren an die Umsteigezeiten

Für Fall (B) haben wir in unseren Berechnungen trotz der neun verschiedenen Parameterwerte nur zwei verschiedene Taktfahrpläne erhalten; der eine liefert für die Werte an die pauschale Umsteigestrafe die besten Gesamtfahrzeiten, der andere für die restlichen Werte. Wir haben wieder beide Taktfahrpläne für alle anderen Parameterwerte ausgewertet. Abbildung 8 zeigt die Ergebnisse in Bezug auf die Gesamtfahrzeit und die Umsteigehäufigkeit. Im Gegensatz zur minimalen Umsteigedauer ergibt die Auswertung der pauschalen Umsteigestrafe einen ziemlich linearen Verlauf für die Gesamtreisezeit. Außerdem sind die Kurvenverläufe für die Gesamtfahrzeit für die zwei Taktfahrpläne fast deckungsgleich. Diese Beobachtungen zeigen, dass die Taktfahrplanoptimierung in Bezug auf pauschale Umsteigestrafen nicht sehr sensitiv ist. Den Fehler, den man macht, wenn man in der Optimierung einen anderen Wert an die pauschale Umsteigestrafe annimmt, als in der Bewertung eines Fahrplans, kann man vernachlässigen. Allerdings zeigt die rechte Abbildung 8, dass die Anzahl der Umstiege insgesamt etwas reduziert werden kann, wenn eine höhere Umsteigestrafe angenommen wird.

Bild 10: Vergleich von Gesamtfahrzeit und Umsteigewartezeit zwischen berechneten Taktfahrplan aus Abschnitt 4 und Referenzplan für verschiedene Parameter an pauschaler Umsteigestrafe (links) und minimaler Umsteigedauer (rechts). Die Säulen geben die Verbesserung/Verschlechterung des berechneten Fahrplans gegenüber dem Referenzplan an.

Im Untersuchungsfall (C) sind die Ergebnisse ähnlich wie im Fall (B). Hier haben wir sogar nur einen Fahrplan erhalten, der für alle Parameterwerte die minimale Gesamtfahrzeit liefert. Abbildung 9 zeigt die Ergebnisse. Auch hier ist der Kurvenverlauf für die Gesamtreisezeit linear. Die Taktfahrplanoptimierung ist bzgl. eines Gewichtungsfaktors für die Gesamtumsteigezeit ebenfalls nicht sensitiv.

Aus den Ergebnissen für die drei Untersuchungsfälle lässt sich ableiten, dass die Wahl einer pauschalen Umsteigestrafe und/oder eines Gewichtungsfaktors für die Gesamtumsteigezeit den optimalen Taktfahrplan eher wenig beeinflusst. Die minimale Umsteigezeit dagegen beeinflusst den optimalen Taktfahrplan sehr stark. Dabei ist es besser eine Mindestumsteigezeit anzunehmen, die etwas zu hoch gegriffen ist, als eine Umsteigezeit, die etwas zu niedrig ist.

Dies zeigt auch nochmal eine vergleichende Bewertung des Referenzfahrplans und des optimierten Fahrplans. Wir haben dazu sowohl den Taktfahrplan aus Abschnitt 4, den wir für f = 4 und b = 8 berechnet haben, als auch den Referenzplan für ausgewertet und miteinander verglichen.

Abbildung 10 links zeigt die prozentuale Verbesserung des optimierten Plans im Vergleich zum Referenzplan bzgl. Gesamtfahrzeiten und Umsteigewartezeiten, wenn beide Fahrpläne für die Umsteigestrafen ausgewertet werden; die Mindestumsteigedauer ist bei der Auswertung auf 4 fixiert. Die prozentuale Verbesserung, insbesondere für die Umsteigewartezeiten, ist nicht für den optimierten Parameter am höchsten, sondern sie ist umso höher je niedriger die Umsteigestrafe ist. Je nach Parameterwahl ergibt sich eine Verbesserung von 25% (bei 1 Minute Umsteigestrafe) bis 6% (bei 10 Minuten). D.h., die Umsteigestrafe beeinflusst vor allen Dingen die Bewertung des (optimierten) Fahrplans gegenüber dem Referenzplan. Generell verspüren damit diejenigen Passagiere, die Umstiege am wenigsten unangenehm empfinden, die größte Verbesserung bei einer Taktfahrplanoptimierung.

Bild 11: Periodischer Taktfahrplan 3: Umsteigen in Barmen und am Hauptbahnhof

Die Wahl der Mindestumsteigedauer wirkt sich dagegen direkt auf die Qualität des Fahrplans aus. Abbildung 10 rechts zeigt die prozentuale Verbesserung des optimierten Plans im Ver- gleich zum Referenzplan bzgl. Gesamtfahrzeiten und Umsteigewartezeiten, wenn beide Fahrpläne für die unteren Schranken ausgewertet werden; die pauschale Umsteigestrafe ist auf 8 fixiert. Hier ist die prozentuale Verbesserung für den optimierten Parameter am höchsten, d.h., die Passagiere, deren Umsteigezeit mit dem Wert übereinstimmt, mit dem der Taktfahrplan optmiert wurde, haben den größten Nutzen. Auch Passagiere, die etwas schneller beim Umsteigen sind, profitieren noch von der optimierten Lösung. Brauchen die Passagiere aber etwas länger für einen Umstieg, als in der Optimierung angenommen, kann es sogar sein, dass sie den optimierten Fahrplan als schlechter empfinden. Daher ist es wichtig, die Mindestumsteigedauer so zu wählen, dass eine deutliche Mehrheit der Passagiere diese Zeit schaffen kann. Natürlich sollte dabei die Mindestumsteigedauer für jede Umsteigestation individuell ermittelt werden. In vielen Fällen (z.B. innerhalb eines Busnetzes) müssen keine großen Strecken beim Umsteigen überwunden werden, so dass die Präferenzen an die Mindestumsteigedauer nicht zu stark voneinander abweichen. In diesen Fällen wird man recht gut eine Mindestumsteigedauer finden, die nahezu allen Passagieren gerecht wird.

Für große Umsteigebahnhöfen, z.B. am Hauptbahnhof, ist es sinnvoll einen Kompromiss zu verwenden, z.B. eine Umsteigedauer, die von 80-90% der Passagiere mindestens erreicht wird, da nicht alle Passagiere gleichzeitig ihre Wunschverbindungen bekommen können. Betrachten wir dazu noch einmal das Beispiel vom Anfang (Abbildung 1) und nehmen an, dass es 10 rote Passagiere gibt, die von Greifswalder Str. nach Langerfeld wollen. Zunächst nehmen wir an, dass 9 Passagiere den Umstieg am Hauptbahnhof in 5 Minuten schaffen, ein Passa- gier benötigt dafür mindestens 13 Minuten; alle anderen Zeiten bleiben gleich. Dann liefert der Taktfahrplan aus Abbildung 11 eine Gesamtfahrzeit von 9 · 28 + 1 · 48 = 300 Minuten; 9 Passagiere steigen am Hauptbahnhof um, 1 Passagier in Barmen. Im Taktfahrplan aus Abbildung 3 steigen alle am Hauptbahnhof um mit einer Gesamtfahrzeit von 10 · 36 = 360 Minuten. Nun nehmen wir den umgekehrten Fall an, 9 Passagiere benötigen 13 Minuten am Hauptbahnhof und 1 Passagier 5 Minuten. Dann würde der Taktfahrplan aus Abbildung 11 eine Gesamtfahrzeit von 1 · 28 + 9 · 48 = 460 liefern. Die Gesamtfahrzeit des Taktfahrplans aus Abbildung 3 bleibt bei 360 Minuten. In beiden Fällen ist es am besten, die Mindestumsteigezeit zu nehmen, die für die Mehrheit passt; im Zweifel aber sollte man die Mindestumsteigedauer lieber ein wenig höher ansetzen und erhält damit gleich noch einen kleinen Puffer für eventuelle Verspätungen.

Literatur

[1] Fu, Q.; Liu, R.; Hess, S. A review on transit assignment modelling approaches to conges- ted networks: a new perspective. Procedia – Soical and Behavioral Sciences, 54:1145 – 1155, 2012.

[2] Hoppmann, H.; Borndörfer, R.; Karbstein, M. Timetabling and passenger routing in public transport. In Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015), 2015.

[3] Laumanns, M.; Szabo, J.; Voegeli, M. Integrating passenger assigment and timetabling for capacitated public transit networks. Talk at the 28th European Conference on Operational Research (EURO 2016), 2016.

[4] Liebchen, C. Periodic timetable optimization in public transport. Dissertation, Technische Universtität Berlin, 2006.

[5] Lindner, T. Train Schedule Optimization in Public Rail Transport. Dissertation, Technische Universtität Braunschweig, 2000.

[6] Lübbe, J. Passagierrouting und taktfahrplanoptimierung. Diploma thesis, Technische Uni- verstität Berlin, 2009.

[7] Nachtigall, K. Periodic Network Optimization and Fixed Interval Timetables. Dissertation, Deutsches Zentrum für Luft- und Raumfahrt, Institut für Flugführung, Braunschweig, 1998.

[8] Odijk, M. A. Construction of periodic timetables, part 1: A cutting plane algorithm. Technical Report 94-61, TU Delft, 1994.

[9] Schmidt, M.; Schöbel, A. Timetabling with passenger routing. OR Spectrum, S.1–23, 2014.

[10] Sels, P.; Dewilde, T.; Cattrysse, D.; Vansteenwegen, P. Reducing the passenger travel time in practice by the automated construction of a robust railway timetable. Transportation Research Part B: Methodological, 84:124 – 156, 2016.

[11] Serafini, P.; Ukovich, W. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550–581, 1989.

[12] Siebert, M.; Goerigk, M. An experimental comparison of periodic timetabling models. Com- puters & Operations Research, 40(10):2251–2259, 2013.

[13] Standardisierte Bewertung von Verkehrswegeinvestitionen des ÖPNV und Folgekosten- rechnung, Version 2006. Im Auftrag des Bundesministers für Verkehr Bau und Stadtent- wicklung.

[14] van der Hurk, E.; Kroon, L.; Maróti, G.; Vervest, P. Deduction of passengers’ route choice from smart card data. In Intelligent Transportation Systems - (ITSC), 2013 16th Internatio- nal IEEE Conference on, S.797–802, Oct 2013.