Geometric Advances and Infrastructure Awareness in Periodic Timetabling

Abstract

The Periodic Event Scheduling Problem (PESP) serves as the foundational framework for optimizing periodic timetables in public transport. We here present advances in the theoretical understanding of PESP and its underlying geometries, as well as novel ways to model and optimize timetabling with integrated infrastructure aspects in practice. First, having formulated PESP as a mixed-integer program, we study the geometric structure of the problem. In the periodic timetable space we find a collection of polytropes, tropical polytopes that are also traditionally convex, wrapped onto a torus. Instead, in the space of cycle offsets, which are auxiliary integer variables, we find a special zonotope, of high combinatorial interest. We establish connections between these two geometries, and employ these newfound insights to develop a novel local improvement heuristic for PESP, Tropical Neighbourhood Search (\tns{}), which we extensively test and evaluate with excellent computational results. In the second half of the dissertation, we focus on the challenge of properly integrating infrastructure constraints with periodic timetabling. We construct novel MIP-based modelling strategies, relevant cutting planes, and other approaches using cycle orders and perfect matchings, to ensure that found solutions are safely operable on the available infrastructure, while also optimizing the assignment of vehicles to ground resources, making full use of previously untapped track capacity. The viability and practical relevance of our models, Infrastructure-Aware PESP and its extensions, is showcased over multiple case studies on real-world public transport networks.

Das Periodic Event Scheduling Problem (PESP) dient als grundlegendes Modell für die Optimierung von Taktfahrplänen in öffentlichen Verkehr. Wir präsentieren Fortschritte im theoretischen Verständnis von PESP und den zugrundeliegenden Geometrien, und zeigen neue Modellierungs- und Optimierungsmethoden für Fahrplanung mit integrierten Infrastrukturaspekten in der Praxis. Nach einer Formulierung von PESP als gemischt-ganzzahliges Programm untersuchen wir zunächst die geometrische Struktur des Problems. Der Raum der Taktfahrpläne zerfällt in eine Menge von Polytropen – tropische Polytope, die auch im traditionellen Sinne konvex sind – und sich um einen Torus wickeln. Im Gegensatz dazu, im Raum der „Cycle Offsets“, also dem Raum der ganzzahligen Hilfsvariablen, betrachten wir ein spezielles Zonotop, das kombinatorisch von großem Interesse ist. Wir stellen Verbindungen zwischen diesen beiden Geometrien her und wenden unsere neuen Erkenntnisse an, um eine neuartige Heuristik für PESP zu entwickeln, Tropical Neighborhood Search (tns). Diese testen und evaluieren wir ausgiebig und erzielen exzellente Rechenergebnisse. Der zweite Teil der Dissertation legt den Fokus auf die Herausforderung, Infrastrukturbedingungen in die Taktfahrplanung zu integrieren. Wir entwickeln neue MIP-basierte Modellierungsansätze und zeigen, neben anderen Möglichkeiten, eine Konstruktion von relevanten Schnittebenen sowie Ansätze unter Verwendung von Zyklusordnungen und perfekten Matchings, um sicherzustellen, dass der Fahrplan auch auf der verfügbaren Infrastruktur sicher umgesetzt werden kann. Hierbei wird die Zuordnung der Fahrzeuge optimiert, sodass bisher unzureichend ausgeschöpfte Gleiskapazitäten ausgenutzt werden können. Die Umsetzbarkeit und praktische Relevanz unserer Modelle, Infrastructure-Aware PESP und dessen Erweiterungen, wird in mehreren Fallstudien anhand realer öffentlicher Verkehrsnetze demonstriert.