TY - JOUR A1 - Riedmüller, Stephanie A1 - Lindner, Niels T1 - Column Generation for Periodic Timetabling N2 - Periodic timetabling for public transportation networks is typically modelled as a Periodic Event Scheduling Problem (PESP). Solving instances of the benchmark library PESPlib to optimality continues to pose a challenge. As a further approach towards this goal, we remodel the problem by a time discretization of the underlying graph and consider arc-based as well as path-based integer programming formulations. For the path-based case, we use cycles on the graph expansion of the operational lines as variables and, therefore, include more of the problem inherent structure into the model. A consequence is the validity of several known inequalities and a lower bound on the LP-relaxation, that is the best known to date. As an extension we integrate passenger routing into the new model. The proposed models have an advantage in the linear programming relaxation, on the one hand, but have an increased problem size, on the other hand. We define the corresponding pricing problems for the use of column generation to handle the size. Both models are practically tested on different problem instances. Y1 - 2025 ER - TY - CHAP A1 - Löbel, Fabian A1 - Lindner, Niels ED - Sauer, Jonas ED - Schmidt, Marie T1 - A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing T2 - 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025) N2 - We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known. KW - Periodic Timetabling KW - Passenger Routing KW - Polyhedral Complexes Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-247580 SN - 978-3-95977-404-8 SN - 2190-6807 VL - 137 SP - 2:1 EP - 2:19 PB - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik CY - Dagstuhl, Germany ER -