Symmetry for Periodic Railway Timetables

AbstractPeriodic 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. However, we provide examples showing that symmetry leads to suboptimality.To integrate symmetry into the graph model of the PESP, there are many obstacles to overcome. Nevertheless, adding symmetry requirements to mixed-integer programming formulations explicitly, enables MIP solvers such as CPLEX© to terminate earlier with good solutions