Vera Grafe

• An important aspect of optimising public transport is finding a good timetable. On the one hand, short travel times are important from the passengers' point of view. On the other hand, tight timetables without buffer times are prone to delays, which are inevitable in practice and highly dissatisfactory for the passengers. Hence, a good timetable should also have some degree of delay resistance. Often a periodic timetable is desirable, i.e. a timetable which repeats in a regular pattern (e.g. every hour). However, delays do in general not occur periodically, so many robust timetable models only consider aperiodic timetables. In our work we analyse different robustness concepts in the context of periodic timetabling, where we allow aperiodic delays. The main focus lies on recoverable robustness, which in our context leads to the integration of the Periodic Event Scheduling Problem (PESP) and Delay Management (DM). These two problems are usually considered in two different networks: while PESP is formulated in a periodic network, DM is considered in an aperiodic network, whose construction uses the timetable as input. Hence, a first challenge when integrating these two problems is to bridge the gap between periodicity and aperiodicity by solving PESP also in the aperiodic network. For this purpose we develop a new timetabling model -- Periodic Timetabling in Aperiodic Network (PTTA) -- which finds a periodic timetable using the aperiodic network. Using this preparatory work, we then develop the Recoverable Robust Periodic Timetabling Problem (RRPT), which is the first one to consider periodic timetables with aperiodic delays. Since we have multiple objective functions, namely the travel time and the worst-case delay, we consider several variants of the problem. Furthermore, we present three equivalent formulations for RRPT, compare their performance in a computational study and identify some properties of recoverable robust timetables. Due to the high complexity of the problem, which is due to both PESP and DM being NP-complete, solving RRPT to optimality on large networks is an unrealistic goal. Hence, we develop several heuristics for finding feasible and ``good" solutions. By modifying the heuristics and testing them for different parameter choices, we identify the most promising variants. Apart from recoverable robustness, many other robustness concepts exist in the literature, among them strict robustness, light robustness and adjustable robustness. We apply them to the problem at hand and analyse the relations between the resulting models in special cases. Furthermore, we compare them with respect to the real travel time, which is the sum of the travel time in the undisturbed setting and the worst-case delay, and discuss for which of these concepts considering aperiodic delays is actually equivalent to only considering periodic delays, and for which it does indeed make a difference. We conclude that recoverable robust timetables are superior, but come with the disadvantage of being the most difficult to compute.
• Ein wichtiger Aspekt bei der Optimierung von öffentlichen Verkehrssystemen ist die Suche nach einem guten Fahrplan. Einerseits sind kurze Fahrzeiten aus Sicht der Fahrgäste wichtig. Andererseits sind knapp geplante Fahrpläne ohne Pufferzeiten anfällig für Verspätungen, die in der Praxis unvermeidlich und für die Fahrgäste höchst unbefriedigend sind. Daher sollte ein guter Fahrplan auch eine gewisse Verspätungsresistenz aufweisen. Oft ist ein periodischer Fahrplan wünschenswert, d.h. ein Fahrplan, der sich regelmäßig wiederholt (z.B. jede Stunde). Verspätungen treten jedoch im Allgemeinen nicht periodisch auf, sodass viele robuste Fahrplanmodelle nur aperiodische Fahrpläne betrachten. In unserer Arbeit analysieren wir verschiedene Robustheitskonzepte im Kontext periodischer Fahrplanung, wobei wir aperiodische Verspätungen zulassen. Das Hauptaugenmerk liegt dabei auf der wiederherstellenden Robustheit, was in unserem Kontext zur Integration des Periodic Event Scheduling Problems (PESP) und Delay Managements (DM) führt. Diese beiden Probleme werden normalerweise in zwei verschiedenen Netzwerken betrachtet: Während das PESP in einem periodischen Netzwerk formuliert wird, wird DM in einem aperiodischen Netz betrachtet, dessen Konstruktion den Fahrplan als Input verwendet. Daher besteht eine erste Herausforderung bei der Integration dieser beiden Probleme darin, die Lücke zwischen Periodizität und Aperiodizität zu schließen, indem das PESP auch im aperiodischen Netz gelöst wird. Zu diesem Zweck entwickeln wir ein neues Modell für die Fahrplanerstellung -- Periodic Timetabling in Aperiodic Network (PTTA) -- das einen periodischen Fahrplan unter Verwendung des aperiodischen Netzwerks findet. Anhand dieser Vorarbeiten entwickeln wir dann das Recoverable Robust Periodic Timetabling Problem (RRPT), das erstmals periodische Fahrpläne mit aperiodischen Verspätungen betrachtet. Da wir mehrere Zielfunktionen haben, nämlich die Reisezeit und die Worst-Case-Verspätung, betrachten wir mehrere Varianten des Problems. Außerdem präsentieren wir drei äquivalente Formulierungen für RRPT, vergleichen ihre Performance und identifizieren einige Eigenschaften von wiederherstellend robusten Fahrplänen. Aufgrund der hohen Komplexität des Problems, die daraus resultiert, dass sowohl PESP als auch DM NP-vollständig sind, ist die optimale Lösung von RRPT auf großen Netzen ein unrealistisches Ziel. Aus diesem Grund entwickeln wir mehrere Heuristiken, um zulässige und „gute“ Lösungen zu finden. Durch Modifizierung der Heuristiken und Testen verschiedener Parameter identifizieren wir die vielversprechendsten Varianten. Neben der wiederherstellbaren Robustheit gibt es in der Literatur noch viele andere Robustheitskonzepte, darunter strenge Robustheit, leichte Robustheit und anpassbare Robustheit. Wir wenden diese Konzepte auf das vorliegende Problem an und analysieren die Beziehungen zwischen den resultierenden Modellen in Spezialfällen. Außerdem vergleichen wir sie im Hinblick auf die reale Reisezeit, die sich aus der Summe der Reisezeit im ungestörten Zustand und der Worst-Case-Verspätung zusammensetzt, und diskutieren, für welche dieser Konzepte die Berücksichtigung aperiodischer Verspätungen tatsächlich äquivalent dazu ist, nur periodische Verspätungen zu berücksichtigen. Wir kommen zu dem Schluss, dass RRPT qualitativ überlegene Fahrpläne liefert, allerdings den Nachteil der schwierigen Berechenbarkeit mit sich bringt.