A Two-Stage Hybrid Heuristic Algorithm for Chance-Constrained Robust Railway Trains Timetable Rescheduling Considering Uncertain Section Running Times

In railway transportation systems, train section running times are usually uncertain due to the influence of various complex factors, making rescheduled timetables difficult to use continually, and rescheduling has to be repeated. When acceptable, rescheduled timetables should have a certain degree of robustness against such uncertainty. We use the empirical statistical distribution of the deviation between actual and scheduled train arrival times to capture this uncertainty. To equip timetables with acceptable robustness, a chance-constrained programming model is established for the robust rescheduling problem. We design a two-stage hybrid heuristic algorithm to solve the proposed model. In the first stage, a hybrid intelligent algorithm combining ant colony optimization and Monte Carlo simulations is used to solve the model initially, and bisection method is embedded into it to improve solving efficiency. Then, the chance-constrained programming model is transformed into its deterministic equivalent form to generate a better solution by utilizing the solution result of the hybrid intelligent algorithm. Finally, we test our method on the realistic dataset of Elizabeth Line to verify its effectiveness and robustness. Compared to the deterministic rescheduling method, our algorithm, with a confidence level of 0.6-0.7, reduces the number of rescheduling times by 22.2%-100% while only increasing delays by 0.5%-3.7%. The experimental results demonstrate that we propose an effective and adjustable method to enhance the robustness of timetables, allowing operators to formulate an ideal timetable with acceptable robustness while minimizing adverse effects on punctuality.