Effective train routing selection for real-time traffic management: Improved model and ACO parallel computing

The real-time Railway Traffic Management Problem (rtRTMP) is the problem of detecting and solving time overlapping conflicting requests made by multiple trains on the same track resources. This problem consists in retiming, reordering and rerouting trains in such a way that the propagation of disturbances in the railway network is minimized. The rtRTMP is an NP-complete problem and finding good strategies to simplify its solution process is paramount to obtain good quality results in a short computation time. Solving the Train Routing Selection Problem (TRSP) aims to reduce the size of rtRTMP instances by limiting the number of routing variables: during the pre-processing, the most promising routing alternatives among the available ones are selected for each train. Then, the selected alternatives are the only ones used for the rtRTMP. A first version of the TRSP has been recently proposed in the literature. This paper presents an improved TRSP model, where rolling stock re-utilization timing constraints and estimation of train delay propagation are taken into account. Additionally, a parallel Ant Colony Optimization (ACO) algorithm is proposed. We analyze the impact of the TRSP model and algorithm on the rtRTMP through a thorough computational campaign performed on a French case study with timetable disturbances and infrastructure disruptions. The presented model leads to a better correlation between TRSP and rtRTMP solutions, and the proposed ACO algorithm outperforms the state-of-the-art algorithm.