Thumbnail Image

Performance of Algorithms for Periodic Timetable Optimization

Liebchen, Christian; Proksch, Mark; Wagner, Frank H.

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

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.