Technical Report 016-2003

Title
Symmetry for Periodic Railway Timetables
Author
Christian Liebchen
Publication
in Bert Gerards and Alberto Marchetti-Spaccamela (eds.): Proceedings of ATMOS 2003 Algorithmic Methods and Models for Optimization of Railways, Electronic Notes in Theoretical Computer Science 92 No. 1, Elsevier, 2003
Source
Download as [PDF]
Classification
MSC:
primary: 90B20 Traffic problems
secondary: 05C90 Applications
90C11 Mixed integer programming
90C27 Combinatorial optimization
Keywords
not available
Abstract
Periodic timetabling for railway networks is usually modeled by the Periodic Event Scheduling Problem (PESP). This model permits to express many requirements that practitioners impose on periodic railway timetables. We discuss a requirement practitioners are asking for, but which, so far, has not been the topic of mathematical studies: the concept of symmetry.
Several motivations why symmetric timetables might seem promising will be given. Though, we provide examples proving suboptimality of symmetric timetables, in general.
There are many obstacles to overcome when trying to introduce symmetry into the graph model of the PESP. Nevertheless, adding symmetry requirements to mixed-integer programming formulations explicitly, enables MIP solvers, such as CPLEX, to terminate earlier with good solutions.