A delay propagation algorithm for large-scale railway traffic networks

Document Type

Journal Article

Publication Date


Subject Area

mode - rail, operations - performance, operations - reliability, operations - scheduling


Railway timetable, Railway traffic, Train delay, Max-plus algebra, Timed event graph


In scheduled railway traffic networks a single delayed train may cause a domino effect of secondary delays over the entire network, which is a main concern to planners and dispatchers. This paper presents a model and an algorithm to compute the propagation of initial delays over a periodic railway timetable. The railway system is modelled as a linear system in max-plus algebra including zero-order dynamics corresponding to delay propagation within a timetable period. A timed event graph representation is exploited in an effective graph algorithm that computes the propagation of train delays using a bucket implementation to store the propagated delays. The behaviour of the delay propagation and the convergence of the algorithm is analysed depending on timetable properties such as realisability and stability. Different types of delays and delay behaviour are discussed, including primary and secondary delays, structural delays, periodic delay regimes, and delay explosion. A decomposition method based on linearity is introduced to deal with structural and initial delays separately. The algorithm can be applied to large-scale scheduled railway traffic networks in real-time applications such as interactive timetable stability analysis and decision support systems to assist train dispatchers.


Permission to publish abstract given by Elsevier, copyright remains with them.


Transportation Research Part C Home Page: http://www.sciencedirect.com/science/journal/0968090X