A CONSTRAINT GENERATION ALGORITHM FOR THE CONSTRUCTION OF PERIODIC RAILWAY TIMETABLES

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.

  • Availability:
  • Corporate Authors:

    Elsevier

    The Boulevard, Langford Lane
    Kidlington, Oxford  United Kingdom  OX5 1GB
  • Authors:
    • Odijk, M A
  • Publication Date: 1996-12

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 00728913
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Nov 12 1996 12:00AM