direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 16-2003

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
Symmetry for Periodic Railway Timetables
Author
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
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.
Source
Download as [PDF]

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe