Track access planning and scheduling for trains

Project title:  Track access planning and scheduling for trains.

Project duration:  Three years (1996 - 6/1999).

Project staff:    Principal Investigator: Professor Malachy Carey

                        Research Associate:  Dr Ivan Crawford

EPSRC grant number: GR/K75798.

The following is a one page summary of the Sept. 1999 final report to EPSRC on the above project/ grant.

Objectives of the research: The objectives of the research, as set out in the original RG2 application form, were:

Develop, test and demonstrate models, algorithms, data structures and computer programmes for train planning and timetabling for a busy rail network (a set of linked busy stations), including finding and resolving conflicts, and assigning platforms at busy complex stations.

Ensure the system developed takes account of the key features and problems met in practice, e.g., multiple lines, speeds, subplatforms, conflicting paths, priorities, breakdowns, etc.

Ensure the system can be used in various ways needed in practice (to design new plans and timetables, check consistency of proposed plans, find good paths for new services, re-plan when breakdowns occur, compute measures of cost and reliability).

Investigate factors affecting performance, and document methods and results.

  We achieved these objectives and other objectives implicit in the original proposal.  The project employed a research assistant for three years and 20% time of a computing/ technical assistant.

   Train planning involves constructing train timetables, and platform and line allocations for all trains on the rail network.  This requires finding and resolving the thousands of potential conflicts between thousands of trains of different speeds and types on conflicting paths using the same lines, stations and platforms.  Though computer IT packages are used to assist in train planning a major part of the process, the finding and resolving of conflicts, is still done ‘by hand’.  For the British rail network this takes hundreds of people many months to complete.

  In view of this, we have developed heuristic algorithms and computer code designed to find and resolve all types of train time, platform and line conflicts.  We started from a model and algorithms for a single station, and extended these to a series of busy complex stations linked by multiple one-way lines in each direction, traversed by trains travelling at different speeds.  The algorithms ensure minimum headways, dwell times, trip times, etc., which depend on the train types or speeds, and the platforms or lines used.  The algorithms also handle a mixture of terminal and through-platforms, multiple subplatforms, operator preferences for times, platforms or lines.  They can also be run in different modes, for example with platform allocations either prespecified or free, or scheduling all trains from scratch, or scheduling only a few while taking the others as fixed.

  We implemented the algorithms and procedures in C code, and tested them for a busy rail system of 25 multi-platform stations, each with multiple subplatforms and with several hundred train movements per day at each station.  We constructed the network and initial draft timetables so as to contain large numbers of conflicts to be resolved.  The algorithms found and resolved all conflicts very quickly.

  We experimented with and compared different versions of the algorithms, and developed computer code to analyse, measure and compare the quality of the schedules produced, so as to obtain the best schedules.  These measures include the differences between the desired times, platforms, etc. and those scheduled.  We also used the algorithms/ programmes to experiment with different train operating policies.  For example, varying the minimum required headways, dwell times or train speeds.  Further, we used the algorithms/ programmes to simulate on-the-day train running, so as to assess the reliability of the schedules produced.  An advantage of the algorithms we have developed is that, unlike present ‘by hand’ methods, they can be used in this way to explore alternative options or policies, or the impact of random disturbances.

Key words: Transport operations. Train timetabling. Train planning. Platform scheduling.