Optimisation of train schedules to minimise transit time and maximise reliability

The overall performance of a train schedule is measured in terms of the mean and variance of train lateness (reliability) as well as the travel time of individual trains. The concept is a critical performance measure for both urban and non-urban rail passenger services, as well as rail freight transportation. This thesis deals with the scheduling of trains on single track corridors, so as to minimise train trip times and maximise reliability of train arrival times. A method to quantify the amount of risk of delay associated with each train, each track segment, and the schedule as a whole, is put forward and used as the reliability component of the constrained optimisation model. As well as for schedule optimisation, the risk of delay model can be applied to the prioritisation of investment projects designed to improve timetable reliability. Comparisons can be made between track, terminal and rolling stock projects, in terms of their likely impact on timetable reliability. The thesis also describes a number of solution techniques for the scheduling problem. New lower bounds for the branch and bound technique are presented which allow solutions for reasonable size train scheduling problems to be determined efficiently. Three solution heuristic techniques are applied to the train scheduling problem, namely: a local search heuristic with an improved neighbourhood structure; genetic algorithms with an efficient string representation; and tabu search. Comparisons in terms of the number of calculations and solution quality are made between the heuristic and branch and bound techniques. The branch and bound technique with the best lower bound out performed genetic algorithms and tabu search for all except the largest size problems