Comparison of algorithms for minimising delay costs in disturbed railway traffic scenarios at a junction

Abstract
The advent of modern railway signalling and train control technology allows the implementation of advanced real-time railway management. Optimisation algorithms can be used to: minimise the cost of delays; find solutions to recover disturbed scenarios back to the operating timetable; improve railway traffic fluidity on high capacity lines; and improve headway regulation. A number of researchers have previously considered the problem of minimising the costs of train delays and have used various optimisation algorithms for differing scenarios. However, little work has been carried out to evaluate and compare the different approaches. This paper compares and contrasts a number of optimisation approaches that have been previously used and applies them to a series of common scenarios. The approaches considered are: brute force, first-come-first-served, Tabu search, simulated annealing, genetic algorithms, ant colony optimisation, dynamic programming and decision tree based elimination. It is found that simple disturbances (i.e. one train delayed) can be managed efficiently using straightforward approaches, such as first-come-first-served. For more complex scenarios, advanced methods are found to be more appropriate. For the scenarios considered in this paper, ant colony optimisation and genetic algorithms performed well, the delay cost is decreased by 30% and 28%, respectively, compared with first-come-first-served.