Fahrplanung und Umlaufplanung sind nach der Linienplanung zwei wichtige Planungsschritte bei der Angebotsplanung im öffentlichen Verkehr. Beide sind in der algorithmischen Literatur gut untersucht. Das Ziel der Fahrplanung besteht darin, den Passagieren gute Anschlüsse und damit gute Umstiegsverbindungen zu ermöglichen. Bei der Umlaufplanung sollen die Anzahl der benötigten Fahrzeuge, die Dauer der Umläufe sowie die Leerkilometer minimiert werden. Das Vorgehen in der algorithmischen Literatur ist meist sequentiell. Zuerst wird ein passagierfreundlicher Fahrplan gesucht, auf dem dann der Umlaufplan basiert. Dagegen ist das Vorgehen in der Praxis oft umgekehrt. Um Kosten zu sparen wird basierend auf groben Vorgaben zunächst der Umlaufplan erstellt, der dann die Zeiten für den Fahrplan bestimmt. Neben dem klassischen sequentiellen Ansatz werden in jüngerer Zeit auch integrierte Herangehensweisen untersucht, sowie heuristische Verfahren, die die entstehenden Kosten bereits im Fahrplanungsschritt abschätzen.

In der vorliegenden Arbeit werden beide Kriterien behandelt, also die Kosten für das Verkehrsunternehmen und die Reisezeit für die Passagiere. Wir entwickeln ein integriertes bikriterielles Optimierungsmodell, mit dem man gleichzeitig Fahrund Umlaufpläne bestimmen kann, die in beiden Kriterien möglichst gut sind. Wir nutzen dieses Modell, um experimentell zu zeigen, dass man verglichen zu dem klassischen sequentiellen algorithmischen Vorgehen (zuerst passagierorientierter Fahrplan, dann kostenorientierter Umlaufplan) signifikant Kosten sparen kann. Das Vorgehen wird an einem kleinen Beispiel, an dem Demonstrator Grid und an der Planung des deutschen Schienen-Fernverkehrs illustriert.

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

1 Sequentielle Planung von Fahrplan und Umlaufplan

In der algorithmischen Literatur wird ein sequentieller Ablauf der Angebotsplanung im öffentlichen Verkehr beschrieben. Nach der Planung der Infrastruktur werden zunächst ein Linienplan und die Frequenzen der einzelnen Linien festgelegt. Basierend auf dem Linienplan mit den Frequenzen wird anschließend ein Fahrplan bestimmt. Wiederum basierend auf dem Fahrplan können die Umläufe gebildet werden, sodass anschließend die Personalplanung stattfinden kann. Das Vorgehen ist auch in verkehrsplanerischer Software wie z.B. PTV VISUM [39] abgebildet und wurde u.a. in [29, 8] beschrieben.

In dieser Arbeit beschäftigen wir uns mit den beiden Planungsschritten Fahrplanung und Umlaufplanung, die beide gut erforscht sind. In der passagierorientierten Fahrplanung ist das Periodische Event Scheduling Problem (PESP) die Grundlage, das u.a. in [1, 37, 2] ausführlich behandelt wurde. Hier geht es um die Minimierung der empfundenen Reisezeit, die die echte Reisezeit der Passagiere zählt und Strafkosten für jeden Umstieg addiert. Neuere Arbeiten in der Fahrplanung beschäftigen sich mit Heuristiken [30, 9, 31] oder mit der Integration des Passagierroutings in die Fahrplangestaltung [10, 11, 12, 13]. Ebenso ist es möglich, mit Hilfe des PESP für spezielle Annahmen an den Umlaufplan die später entstehenden Kosten bereits im Fahrplanungsschritt zu schätzen [2, 32]. In der Umlaufplanung geht es um die Zuordnung der Fahrzeuge zu den geplanten Linienfahrten. Ziel dabei ist die Minimierung der entstehenden Kosten, die sich aus der Anzahl der Fahrzeuge, der gefahrenen Kilometer und der aufzuwendenden Zeit zusammensetzen. Wir verweisen hierfür auf den Übersichtsartikel [14], in dem verschiedene Modelle für die aperiodische Umlaufplanung vorgestellt werden. Für den vereinfachten Fall, dass nur die Anzahl der Fahrzeuge minimiert wird und kein Fahrzeugdepot betrachtet wird, ist es auch möglich, stattdessen ein kleineres periodisches Modell zu lösen, siehe [33]. Da eine Äquivalenz der beiden Modelle allerdings nur für einen sehr langen Betriebszeitraum gewährleistet werden kann, verwenden wir im Folgenden eine aperiodische Formulierung. Ein besonders detailliertes Modell, das auch in der Praxis Anwendung finden kann, wird in [38] vorgestellt.

Schon in [34] wurde die Frage nach einer möglichen Integration der Planungsschritte im öffentlichen Verkehr gestellt. Daran wird in letzter Zeit zunehmend geforscht, siehe z.B. [40, 15, 16] für die Integration von Linien und Fahrplanung und [34, 17, 32, 41, 3] zur Integration von Linien-, Fahrund Umlaufplanung. Die Integration von Fahrund Umlaufplanung wurde bisher vor allem für aperiodische Fahrplanungsprobleme betrachtet und oft mit (meta-)heuristischen Ansätzen gelöst, siehe z.B. [42, 18, 43, 19, 20, 21, 22, 23]. Ein weiterer Ansatz besteht darin, sowohl Fahrals auch Umlaufplan periodisch zu betrachten, siehe z.B. [4, 5, 35]. In der hier vorliegenden Arbeit beschäftigen wir uns allerdings mit der Integration von periodischer Fahrplanung und aperiodischer Umlaufplanung. Auch außerhalb der Verkehrsplanung wird an der integrativen Lösung von Optimierungsproblemen, die miteinander in Beziehung stehen, geforscht, siehe z.B. [24, 25].

2 Minimierung der Reisezeit oder der Kosten

In unserem Beitrag stellen wir ein Modell vor, das die beiden Planungsschritte Fahrplanung und Umlaufplanung integriert behandelt, d.h. es wird nicht zuerst ein Fahrplan bestimmt, zu dem dann ein passender Umlaufplan gesucht wird, sondern es werden beide Schritte simultan behandelt. Eine Lösung des integrierten Modells besteht entsprechend aus einem Fahrund einem Umlaufplan. Dabei stellt sich die Frage nach den Bewertungskriterien: Die Fahrplanung minimiert die (empfundene) Reisezeit für die Passagiere, die Umlaufplanung hingegen minimiert die entstehenden Kosten. Behandelt man die beiden Schritte sequentiell und beginnt wie in der algorithmischen Literatur weit verbreitet mit der passagierorientierten Fahrplanung, so erhält man einen Fahrplan mit bestmöglicher Reisezeit. Die sich ergebenden Umläufe können dann aber zu relativ hohen Kosten führen. Beginnt man wie in der Praxis vieler (kleinerer) Verkehrsunternehmen mit der Planung vernünftiger Umläufe, so erhält man eine Lösung mit geringeren Kosten, aber der darauf basierende Fahrplan weist für die Passagiere höhere Reisezeiten auf. Diese Variante ist auch als heuristischer Ansatz in der Literatur zu finden, siehe z.B. [2, 32], indem die approximierten Kosten der späteren Umläufe bereits im Fahrplanungsschritt in die Zielfunktion aufgenommen werden.

In unserem Modell können wir nun beide Schritte gleichzeitig behandeln und haben damit auch zwei (sich oft widersprechende) Bewertungskriterien, nämlich

1. minimiere die (empfundene) Passagier-Reisezeit, und

2. minimiere die Kosten des Verkehrsangebotes.

Das Ziel besteht darin, Lösungen zu finden, die sich bezüglich beider Kriterien gut verhalten (siehe dazu auch [29]).

Betrachten wir dazu zwei Lösungen A und B in Bild 1 und stellen fest, dass die Lösung A sowohl eine kleinere Reisezeit der Passagiere als auch geringere Kosten als die Lösung B aufweist, so können wir Lösung B streichen. Man sagt, dass die Lösung B von der Lösung A dominiert wird. Lösungen, die von keiner anderen Lösung dominiert werden (in unserem Beispiel sind das A, C und E) nennt man in der multikriteriellen Optimierung auch Pareto-Lösungen. Im nächsten Abschnitt stellen wir ein Modell vor, mit dem man solche Lösungen auffinden kann. Durch die Betrachtung verschiedener Pareto-Lösungen ist es möglich, neue Informationen zum TradeOff zwischen den beiden Zielfunktionen zu erhalten, die durch die sequentiellen Ansätze nicht gefunden werden konnten.

3 Ein bikriterielles Modell zur integrierten Fahr- und Umlaufplanung

Unser Modell sucht wie oben beschrieben Lösungen, die aus einem Fahrplan und einem Umlaufplan bestehen und von keiner anderen Lösung bezüglich der beiden Zielfunktionen Passagier-Reisezeit und Kosten dominiert werden.

Bild 1: Beispiel zur Verdeutlichung von Dominanz und Pareto-Lösungen

Um das periodische Fahrplanungsproblem mit Periodenlänge T zu modellieren, nutzen wir ein periodisches Ereignis-Aktivitäts-Netzwerk N = (E , A), in dem Ankunfts- und Abfahrtsereignisse von Linien an Haltestellen als Knoten E dargestellt werden. Das Fahren von Fahrzeugen zwischen verschiedenen Haltestellen, das Warten an den Haltestellen, die Umstiege von Passagieren sowie Sicherheitsabstände werden mithilfe von Kanten, den sogenannten Aktivitäten A modelliert, die die Ereignisse miteinander verbinden und somit deren Abfolge definieren. Für jede solche Aktivität a = (i, j) ∈ A gibt es eine untere und eine obere Schranke L_a, U_a an ihre Dauer, sodass für die Zeiten der Ereignisse i, j folgendes gelten muss:

L_a ≤ π_j − π_i − L_a   mod T + L_a ≤ U_a.

Um die (empfundene) Reisezeit der Passagiere zu bestimmen, werden a priori Wege im Ereignis-Aktivitäts-Netzwerk bestimmt, sodass für jede Aktivität a ∈ A die Anzahl w_a der Passagiere, die Aktivität a nutzen, festgelegt werden kann. Somit kann die mit der Anzahl der Passagiere gewichtete Summe der Aktivitätslängen zur Berechnung der Passagier-Reisezeit genutzt werden. Dabei werden sowohl bei der Bestimmung der Wege als auch bei der Berechnung der empfundenen Reisezeit Strafkosten für Umstiege berücksichtigt.

Das Umlaufplanungsproblem modellieren wir im Gegensatz zum Fahrplan als aperiodisches Problem. Hierbei gehen wir davon aus, dass für eine Menge von P Periodenwiederholungen alle Linien L von einem Fahrzeug abgedeckt werden müssen. Das Befahren von Linie l ∈ L in Periodenwiederholung p ∈ P wird dabei Trip (p, l) genannt. Die Leerfahrten zwischen den Trips müssen sich allerdings nicht in jeder Periode wiederholen. Ein Beispiel für einen Umlaufplan ist in Bild 2 dargestellt.

Bild 2: Darstellung eines möglichen Umlaufplan für zwei Linien und vier Periodenwiederholungen

Die Kosten für einen gegebenen Umlaufplan setzen sich aus folgenden Komponenten zusammen: den Kosten für die Fahrzeit (mit und ohne Passagiere), den Kosten für die Länge der Trips und der Leerfahrten sowie der Anzahl der benötigten Fahrzeuge. Da hier ein Depot betrachtet wird, die Fahrten der Fahrzeuge also alle am Depot starten und enden, müssen auch Leerfahrten vom und zum Depot betrachtet werden. Dabei beschreiben L_dep,l, L_l,dep die Fahrzeiten, die vom Depot zum Start von Linie l beziehungsweise vom Ende von Linie l zum Depot benötigt werden und D_dep,l, D_l,dep die dafür zurückgelegte Distanz. Analog beschriebt D_l1,l2  die Distanz, die auf einer Leerfahrt zwischen Linie l₁ und l₂ zurückgelegt werden muss. Da die Trips bereits a priori durch den Linienplan gegeben sind und die für Trip (p, l) zurückgelegte Distanz als lengthl bereits feststeht, muss für die Trips lediglich die variable Dauer in der Zielfunktion berücksichtigt werden. Der Vollständigkeit halber nehmen wir allerdings die Tripdistanz in die Zielfunktion auf.

Um das bikriterielle Problem zu formulieren, wählen wir analog zu den Modellen in [3, 36] in der Fahrund Umlaufplanung die folgenden Variablen:

Formel siehe PDF

Formel siehe PDF

Die Zielfunktion von (F+U) besteht aus der empfundenen Reisezeit (1) sowie den Kosten. Diese wiederum setzen sich aus Kosten für die Dauer und Länge der befahrenen Linien, (2) und (3), der Dauer und Länge der Leerfahrten, (4) und (5), sowie der Anzahl der Fahrzeuge, (6), zusammen. Die Nebenbedingungen (7) und (8) modellieren die Zulässigkeit des Fahrplans während (9) die Dauer einer Linienfahrt modelliert. In den Nebenbedingungen (10) und (11) werden die periodischen Abfahrtszeiten am Anfang der Linien und die Liniendauer kombiniert, um die aperiodischen Startund Endzeiten der Trips zu bestimmen. Die Zulässigkeit der Fahrzeugumläufe wird in Nebenbedingung (12) sichergestellt, wobei

Formel siehe PDF

ein ausreichend großer Wert für M ist. Nebenbedingungen (13) und (14) modellieren den Fluss der Fahrzeuge, während (15) und (16) die Fahrzeiten der Trips bestimmen. M' ist dabei ausreichend groß gewählt, wenn es dabei dieselbe Bedingung wie M erfüllt.

4 Ergebnisse

Bild 3: Linienkonzept für Datensatz Toy. Die Knoten repräsentieren die Haltestellen v₁ bis v₈. Die beiden Linien sind durchgezogen rot beziehungsweise gestrichelt grün dargestellt.

Bild 4: Evaluation des bikriteriellen Ansatzes auf Datensatz Toy.

Das Ergebnis findet sich in Bild 4. Die Lösung des sequentiellen Prozesses, in dem zunächst ein möglichst guter Fahrplan gesucht wird, den man dann mit einem darauf basierenden, möglichst kostengünstigen Umlaufplan ergänzt, ist mit einem Stern dargestellt. Alle anderen Lösungen ergeben sich aus dem in Abschnitt 3 beschriebenem Modell (F+U). Auch wenn man viele verschiedene Werte von β durchgeht, kommen nur die drei dargestellten Pareto-Lösungen zustande, da unterschiedliche Parameter β oft zur gleichen Lösung führen. Bild 4 zeigt folgende Ergebnisse:

∙ Zunächst sieht man, dass die sequentielle Lösung (Stern) zu einem Verkehrsangebot mit bestmöglicher Passagier-Reisezeit führt. Das ist immer so, da in der sequentiellen Optimierung die Fahrplanung durch keinerlei Bedingungen an die Umläufe eingeschränkt ist. Allerdings zeigt die Lösung für β = 100 (Dreieck), dass es auch einen anderen Fahrplanmit derselben Reisezeit gibt, für den es einen Umlaufplan mit um 4 Prozent reduzierten Kosten gibt.

∙ Es wird auch direkt klar, dass die Reihenfolge zuerst Fahrplan, dann Umlaufplan nicht zu den bestmöglichen Kosten führt. In dem angegebenen Beispiel kann man die Kosten von 656,88 auf 455,8 um bis zu 30,6 Prozent senken, wenn man in der Reihenfolge zuerst Umlaufplan, dann Fahrplan optimieren würde, siehe untere Schranke, berechnet für β = 0. Dabei erhöht sich allerdings die durchschnittliche empfundene Reisezeit von 8,83 Minuten auf 9,94 Minuten.

∙ Eine weitere mögliche Lösung zwischen den beiden eben genannten Extremen ist die Lösung für β = 0, 7 (Raute), die mit Kosten von 543,3 und einer durchschnittlichen empfundenen Reisezeit von 9,09 Minuten einen guten Kompromiss darstellt.

Wir haben unser Modell auch auf zwei weitere Beispiele angewendet: Auf eine Instanz des Demonstrators Grid [29, 46], siehe Bild 5a, und auf eine Instanz angelehnt an das SchienenFernverkehrsnetz in Deutschland [32], siehe Bild 6a, mit einem Betriebszeitraum von vier beziehungsweise acht Stunden. Die zugehörigen Modelle umfassen 8960 Variablen und 13192 Nebenbedingungen beziehungsweise 919642 Variablen und 1379328 Nebenbedingungen. Aufgrund der sich ergebenden Größe von (F+U) sind die dabei aufgefundenen Verkehrsangebote nicht die bestmöglichen, sondern nur eine heuristische Annäherung an die exakten Lösungen des Modells. Einige durch (F+U) gefundene Lösungen sind in Bild 5 und 6 dargestellt. Grundsätzlich erlauben sie aber die gleiche Schlussfolgerung wie bei dem eben vorgestellten Beispiel Toy: Man kann signifikant Kosten sparen, wenn man von der sequentiellen Reihenfolge zuerst Fahrplan, dann Umlaufplan abweicht. Sie zeigen außerdem die jeweilige Bandbreite der Kosten und der Passagier-Reisezeiten möglicher Lösungen.

Bild 5: Demonstrator Grid.

Bild 6: Fernverkehrsnetz Deutschland.

Aus den beiden größeren Instanzen wird allerdings noch etwas anderes deutlich: In dem Ergebnis für Grid in Bild 5b sieht man, dass die durch einen Stern gekennzeichnete sequentielle Lösung eine sich aus dem integrierten Modell (F+U) ergebende Lösung für β = 100 (Quadrat) dominiert. Das ist wie oben beschrieben theoretisch unmöglich und liegt daran, dass das in Abschnitt 3 vorgestellte Modell schwierig zu lösen ist. Während wir bei dem Beispiel Toy die exakten optimalen Lösungen erhalten haben, lässt sich (F+U) durch einen Solver nicht mehr so einfach lösen. Die in Bild 5b und 6b dargestellten Lösungen sind die besten bis zu einer Rechenzeit von 4 bzw. 8 Stunden gefundenen Lösungen, wobei bei dem Datensatz Grid eine Optimalitätslücke von bis zu 14% zu verzeichnen ist, bei dem Datensatz zum Fernverkehr sogar bis zu 30%. Sie bilden also nur eine Approximation der Pareto-Front. Es ist daher sogar noch mit weiterem Einsparpotential zu rechnen. Aber selbst die heuristischen Lösungen aus Bild 5b und 6b zeigen schon ein hohes Einsparpotential ohne einen großen negativen Effekt auf die Passagier-Reisezeit und bestätigen damit unsere Analyse. Es zeigt sich auch, dass effiziente Verfahren zur Lösung des in Abschnitt 3 vorgestellten Modells ein wichtiger Punkt für die zukünftige Forschung ist.

5 Schlussfolgerung

Unsere Arbeit zeigt, dass das in der algorithmischen Literatur verbreitete Vorgehen Bestimme zuerst einen guten Fahrplan, dann darauf basierend einen guten Umlaufplan zu relativ hohen Kosten für das Verkehrsangebot führt. Eine bikriterielle Optimierung zeigt die minimal erreichbaren Kosten für das Verkehrsangebot und bietet außerdem Pareto-Lösungen an, die zwischen der Passagier-Reisezeit und den Kosten abwägen. Nur für kleine Beispiele lassen sich diese Pareto-Lösungen exakt bestimmen; hier ist weitere Forschung an dem Modell und dazu passenden Algorithmen sinnvoll. Ein möglicher Ansatz besteht darin, sogenannten Repräsentationen, also eine geeignete Teilmenge der Pareto-Menge zu berechnen (vgl. [27]). Dabei können die Repräsentanten auch aus Lösungen bestehen, die selbst nicht Pareto-optimal sind (siehe [28]). Informationen über Dualitätslücken können dann helfen, die Qualität der Repräsentation zu messen.

Außerdem ist eine gezielte multikriterielle Optimierung auch für die Integration weiterer Planungsschritte ein spannendes Forschungsthema, insbesondere auch für die Integration der Linienplanung. Ansätze dazu werden in [3] vorgestellt; Experimente zu diesem Thema am Beispiel Grid finden sich unter [46].

6 Literatur

6.1 Bücher

[1] K. Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. PhD thesis, University of Hildesheim, 1998.

[2] C. Liebchen. Periodic Timetable Optimization in Public Transport. dissertation.de – Verlag im Internet, Berlin, 2006.

[3] P. Schiewe. Integrated Optimization in Public Transport Planning. PhD thesis, Universität Göttingen, 2018.

[4] T. Lindner. Train schedule optimization in public rail transport. PhD thesis, Technische Universität Braunschweig, 2000.

[5] L. Peeters. Cyclic Railway Timetabling Optimization. PhD thesis, ERIM, Rotterdam School of Management, 2003.

[6] M. Ehrgott. Multicriteria optimization, volume 491. Springer Science & Business Media, 2005.

[7] S. Ruzika. On multiple objective combinatorial optimization. Verlag Dr. Hut, 2007.

6.2 Zeitschriftenartikel

[28] P. Halffmann, S. Ruzika, C. Thielen, and D. Willems. A general approximation method for bicriteria minimization problems. Theoretical Computer Science, 695:1–15, 2017.

6.3 Beiträge aus Tagungsbänden

[29] M. Friedrich, M. Hartl, A. Schiewe, and A. Schöbel.  Angebotsplanung im öffentlichen Verkehr planerische und algorithmische Lösungen. In Heureka’17, 2017.

[30] K. Nachtigall and J. Opitz. Solving periodic timetable optimisation problems by modulo simplex calculations. In Proc. ATMOS, 2008.

[31] J. Pätzold and A. Schöbel.  A Matching Approach for Periodic Timetabling.  In ATMOS 2016, volume 54 of OpenAccess Series in Informatics (OASIcs), 2016.

[32] J. Pätzold, A. Schiewe, P. Schiewe, and A. Schöbel. Look-Ahead Approaches for Integrated Planning in Public Transportation. In ATMOS 2017, volume 59 of OpenAccess Series in Informatics (OASIcs), 2017.

[33] R. Borndörfer, M. Karbstein, C. Liebchen, and N. Lindner. A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable. In ATMOS 2018, volume 65 of OpenAccess Series in Informatics (OASIcs), 2018.

[34] C. Liebchen. Linien-, Fahrplan-, Umlaufund Dienstplanoptimierung: Wie weit können diese bereits integriert werden? In M. Friedrich, editor, Heureka’08 – Optimierung in Transport und Verkehr, Tagungsbericht. FGSV Verlag, 2008. (in German).

[35] S. Dutta, N. Rangaraj, M. Belur, S. Dangayach, and K. Singh. Construction of periodic timetables on a suburban rail network-case study from Mumbai. In RailLille 2017—7th International Conference on Railway Operations Modelling and Analysis, 2017.

[36] M.E. Lübbecke, C. Puchert, P. Schiewe, and A. Schöbel. Integrating line planning, timetabling and vehicle scheduling Integer programming formulation and analysis. In Proceedings of CASPT 2018, 2018.

6.4 Schriftenreihen

[37] L. Peeters and L. Kroon. A cycle based optimization model for the cyclic railway timetabling problem. In S. Voß and J. Daduna, editors, Computer-Aided <s