A constraint generation algorithm for the construction of periodic railway timetables
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.
Volume (Year): 30 (1996)
Issue (Month): 6 (December)
|Contact details of provider:|| Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description|
|Order Information:|| Postal: http://www.elsevier.com/wps/find/supportfaq.cws_home/regional|
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Serafini, Paolo & Ukovich, Walter, 1989. "A mathematical model for the fixed-time traffic control problem," European Journal of Operational Research, Elsevier, vol. 42(2), pages 152-165, September.
- Gertsbakh, Ilya & Serafini, Paolo, 1991. "Periodic transportation schedules with flexible departure times : An interactive approach based on the periodic event scheduling problem and the deficit function approach," European Journal of Operational Research, Elsevier, vol. 50(3), pages 298-309, February.