Portal de Periódicos da CAPES

A constraint generation algorithm for the construction of periodic railway timetables

1996; Elsevier BV; Volume: 30; Issue: 6 Linguagem: Inglês

10.1016/0191-2615(96)00005-7

1879-2367

Michiel A. Odijk,

Transportation Planning and Optimization

This paper addresses the problem of constructing periodic timetables for train operations. We use 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. We describe 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.