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.
