8973
eng
reportzib
0
--
2023-01-31
--
Forward and Line-Based Cycle Bases for Periodic Timetabling
The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks, and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.
1438-0064
urn:nbn:de:0297-zib-89731
publish
Berenike Masing
Niels Lindner
Niels Lindner
Patricia Ebert
ZIB-Report
23-05
Mathematics of Computing
Computer Applications
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
MODAL-Gesamt
Lindner, Niels
Network Optimization
Masing, Berenike
MODAL-MobilityLab
MathPlus-AA3-8
https://opus4.kobv.de/opus4-zib/files/8973/ZR-23-05.pdf