A CONSTRAINT GENERATION ALGORITHM FOR THE CONSTRUCTION OF PERIODIC RAILWAY TIMETABLES
mode - rail
Train operation, Train handling, Timetables, Constraints, Arrivals and departures, Algorithms
This paper addresses the problem of constructing periodic timetables for train operations. The author uses a mathematical model consisting of periodic time window constraints by means of which arrival and departure times can be related pairwise on a clock, rather than on a linear time axis. Constructing a timetable, then, means solving a set of such constraints. This problem is known to be hard, i.e., it is NP-complete. The author describes a new algorithm to solve the problem based on constraint generation and work out a real-life example. It appears that, for problem instances of modest, yet non-trivial, size, the algorithm performs very well, which opens a way to thorough performance analysis of railway systems by studying a large number of possible future timetables.
Odijk, M, (1996). A CONSTRAINT GENERATION ALGORITHM FOR THE CONSTRUCTION OF PERIODIC RAILWAY TIMETABLES. Transportation Research Part B: Methodological, Volume 30, Issue 6, p. 455-464.