• search hit 3 of 12
Back to Result List

Performance of Algorithms for Periodic Timetable Optimization

Please always quote using this URN:urn:nbn:de:0296-matheon-1612
  • 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 five conceptually different solution approaches. On rather small instances, an arc-based MIP formulation behaves best, when refined 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 first automated timetable optimization software in use.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christian Liebchen, Mark Proksch, Frank H. Wagner
URN:urn:nbn:de:0296-matheon-1612
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2004/08/09
Release Date:2004/07/09
Institute:Technische Universität Berlin
Preprint Number:148
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.