direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 21-2004

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Performance of Algorithms for Periodic Timetable Optimization
Christian Liebchen, Mark Proksch, and Frank H. Wagner
In Mark Hickman, Pitu Mirchandani, and Stefan Voss (eds.): Computer-aided Systems in Public Transport (CASPT 2004), Springer LNEMS 600, 2007
primary: 90-08 Computational methods
secondary: 90C11 Mixed integer programming
90C59 Approximation methods and heuristics
periodic timetabling, mixed-integer programming, local search procedures, constraint programming
During the last 15 years, there have been proposed many solution methods for the important task of constructing periodic timetables for public transportation companies. We first point out the importance of an objective function, where we observe that in particular a linear objective function turns out to be a good compromise between essential practical requirements and computational tractability. Then, we enter into a detailed empirical analysis of various Mixed Integer Programming procedures - such using nodes variables and such using arcs variables - genetic algorithms, simulated annealing and constraint programming. To our knowledge, this is the first comparison of ve conceptually di erent solution approaches.
On rather small instances, an arc-based MIP formulation behaves best, when re ned by additional valid inequalities. On bigger instances, the solutions obtained by a genetic algorithm are competitive to the solutions CPLEX was investigating until it reached a time or memory limit. For Deutsche Bahn AG, the genetic algorithm was most convincing on their various data sets, and it will become the rst automated timetable optimization software in use.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe