A comparison of algorithms for minimising delay costs in disturbed railway traffic scenarios

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.

► We applied eight railway timetable rescheduling algorithms at the same junction with four different scenarios.
► We examine the algorithms in delay cost and computation time.
► First-come-first-served should be primarily used as an initial solution to initiate other methods.
► Decision tree based elimination and tabu perform well in complex scenarios where little computation time is available.
► Genetic algorithm, simulated annealing and ant colony algorithm all perform comparably well.
► ACO provides close to optimum solutions with practical computation times for the scenarios considered.