Performance of Algorithms for Periodic Timetable Optimization

Christian Liebchen (), Mark Proksch () and Frank H. Wagner ()
Additional contact information
Christian Liebchen: TU Berlin
Mark Proksch: intranetz GmbH
Frank H. Wagner: Deutsche Bahn AG

A chapter in Computer-aided Systems in Public Transport, 2008, pp 151-180 from Springer

Abstract: Abstract During the last 15 years, many solution methods for the important task of constructing periodic timetables for public transportation companies have been proposed. 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 (MIP) procedures — those using node variables and those using arc variables — genetic algorithms, simulated annealing and constraint programming. To our knowledge, this is the first comparison of five conceptually different solution approaches for periodic timetable optimization. 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.

Keywords: Minimal Span Tree; Mixed Integer Programming; Constraint Programming; Valid Inequality; Cycle Base (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations: View citations in EconPapers (9)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnechp:978-3-540-73312-6_8

Ordering information: This item can be ordered from
http://www.springer.com/9783540733126

DOI: 10.1007/978-3-540-73312-6_8

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().