Interactive scheduling and re-scheduling of trains

Project title:  Interactive scheduling and re-scheduling of trains for major stations & junctions

Project duration:  Three years (1992 - 1995).

Project staff:    Principal Investigator : Professor Malachy Carey

                        Research Assistant:  Sinead Carville (now Armstrong)

EPSRC grant number: GR/H/48033.

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

This project employed one Research Assistant (Sinead Carville) for 36 months.  The objectives were:

[A-B].  Determine how train planners currently plan and replan train movements through busy stations (platforming), and formalize, revise and extend this into rules and models.

[C].  Develop computer based models and systems to generate train running plans from the rules and models in A-B.

[D]. Develop operational computable measures of reliability and robustness of train plans such as generated in C

[E].  Link C and D, so as to evaluate and improve the results (plans) from C.

We achieved the above objectives.  Some of the main contributions can be summarized as follows.

(A-B).  From expert train planners we elicited the various rules and strategies they use to plan train assignment to platforms at busy stations and junctions.  We did this for a few of large busy stations reflecting all types of platforming complexity and all types of train, platform and line conflicts.  We formalised the train platforming process into sets of rules and algorithms.   For these stations we also gathered the data required for train platforming, e.g., tables of minimum headways, dwell times, turnaround times, etc., maps of station layout and line conflicts, etc.

(C).  We developed computer packages to implement these platforming rules and algorithms.  For large stations the platforming programs initially took some hours to run, but by successive refinements of the algorithmic and computing methods we got this down to minutes and then seconds.  The programmes now take only a few seconds on a medium PC to assign all (500) trains from scratch for one of the largest most complex stations in Britain, with over 30 sub-platforms, huge numbers of potential conflicts, multiple train types, lines, origins and destinations.  This compares with taking days using current manual methods, and allows far more options to be considered, and includes additional objectives and constraints which are not practicable with current methods. 

 (D).  To test the reliability of train platforming plans, we developed two types of measures.   The first measures are based on extensive Monte Carlo simulation, simulating using the platforming plan for several thousand days, with typical random disturbances added to the timetable, and with or without allowing platform changes.  We analyse the results and compute means, confidence intervals, etc., for the resulting knock-on delays, etc.  Using these measures we found our computer generated platforming plans compared favourably with those produced by Railtrack.

 The second types of reliability or robustness measures we developed are based on fast heuristics rather than simulation: For example, the number of potential conflicts for arriving/ departing trains.  Though these measures are less accurate than simulation, they are designed to be easy to apply while generating train plans. 

 (E).  We used the above heuristic measures, together with other measures of platform desirability, to guide the choice of platform when constructing the timetable.  We tested the resulting timetables using Monte Carlo simulation as above, and found that the heuristic reliability rules did indeed improve reliability, and produced timetables more reliable than current timetables.

The platforming and reliability software is written in C and has been tested under several systems, including MS Dos, Windows 3.1, Windows NT, and a Vax.  It can handle unlimited numbers of trains - far in excess of the numbers possible at any station.

Key words: Rail transportation. Train platforming. Train timetabling. Train scheduling. Timetable design. Reliability