zbMATH — the first resource for mathematics

Symmetry for periodic railway timetables. (English) Zbl 1271.90014
Gerards, B. (ed.), Proceedings of the ATMOS workshop on algorithmic approaches for transportation modeling, optimization, and systems 2003, Budapest, Hungary, September 15–20, 2003. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 92, 34-51 (2004).
Summary: 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. 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\(^{\copyright}\) to terminate earlier with good solutions.
For the entire collection see [Zbl 1271.90006].

90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
PDF BibTeX Cite
Full Text: Link