Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Column Generation for Periodic Timetabling

under review
  • 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.

Export metadata

Additional Services

Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Stephanie RiedmüllerORCiD, Niels LindnerORCiD
Document Type:Article
Year of first publication:2025
ArXiv Id:http://arxiv.org/abs/2510.12466
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.