Construction of Periodic Timetables. Part 2. An Application

摘要

This report is a follow up of 'Construction of Periodic Timetables - Part I: ACutting Plane Algorithm' (PB95-215141) and addresses the problem of quickly generating many periodic timetables for train arrivals and departures at railway stations. With these timetables, then, the performance of a railway station track layout design can be evaluated by means of simulation. We describe a mathematical model for a timetable structure from which a number of timetables should be generated. It can be shown that this is far from trivial, i.e. the generation problem is NP-complete. Still, a cutting plane algorithm can be formulated that is efficient from computational point of view. A large part of this report is devoted to the description of a case study that shows that despite the complexity of the problem the algorithm can sample many timetables from a timetable structure very efficiently, thus allowing for effective analysis of a track layout design.