A CONSTRAINT GENERATION ALGORITHM FOR THE CONSTRUCTION OF PERIODIC RAILWAY TIMETABLES

M A. Odijk

Document Type

Journal Article

Publication Date

1996

Subject Area

mode - rail

Keywords

Train operation, Train handling, Timetables, Constraints, Arrivals and departures, Algorithms

Abstract

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.

Comments

Transportation Research Part B Home Page: http://www.sciencedirect.com/science/journal/01912615

Link to Full Text

Share

COinS