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

A two-stage model for periodic timetabling with fixed line activities

Please always quote using this URN: urn:nbn:de:0297-zib-101234
  • The timetable is a central pillar of any public transportation system. Constructing and optimizing periodic timetables in terms of passenger comfort and operational efficiency leads to NP-hard optimization problems that are also computationally challenging in applications. The Periodic Event Scheduling Problem (PESP) as standard mathematical tool benefits from its succinct formulation and rich combinatorial structure, but suffers from poor linear programming relaxations and weak dual bounds. These difficulties persist in a reduced version, where driving and dwelling activities of the lines are assumed to be fixed. In this case, fixing the initial departure time of each line fully determines the timetable, and for each pair of lines, the resulting (weighted) transfer durations can be expressed in terms of a piecewise linear non-convex function in terms of the difference of the initial times. When the number of activities between two lines is bounded, this function can be computed in polynomial time. By inserting precomputed piecewise linear functions into a mixed-integer program with the initial departure times as variables, we introduce an equivalent formulation for reduced PESP instances. The model bears analogies with quadratic semi-assignment approaches and offers alternative ways to compute primal and dual bounds. We evaluate the computational behavior of our approach on realistic benchmarking instances.

Download full text files

Export metadata

Metadaten
Author:Niels LindnerORCiD, Christian LiebchenORCiD
Document Type:ZIB-Report
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Classification:J. Computer Applications
Date of first Publication:2025/08/25
Series (Serial Number):ZIB-Report (25-14)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.