Solving the railway timetable rescheduling problem with graph neural networks

Abstract

This study solves the train timetable rescheduling (TTR) problem from a brand-new perspective. We assume that train traffic controllers take three main actions, i.e., adjusting dwelling times, running times, and train orders, to reschedule the timetable in real-time dispatching. To raise the interpretability of rescheduling models, we propose a graph neural network (GNN) approach to map the train timetable data into evolution graphs that fit the paradigm of train operation processes. Based on graphs, two experiments from node and edge perspectives were investigated based on train operation data, i.e., (1) node experiment: train dwelling times and running times are predicted; and (2) edge experiment: an algorithm based on evolution graph, called overtaking identification algorithm (OIA), is proposed to identify train overtaking based on the consequences of the node experiment. Timetable rescheduling solutions are obtained by integrating the GNN, OIA, and train operation constraints. Experimental results show that the proposed approach has a satisfactory predictive performance. Timetable rescheduling cases under diverse delay scenarios are examined, showing that the proposed method is superior to other three standard rule-based benchmarks regarding train delays of the disturbed train groups under the given scenarios. Additionally, the model exhibits high efficiency in the three timetable rescheduling scenarios, demonstrating the model’s applicability in real-time train dispatching.

Keywords

Timetable rescheduling / Timetable rescheduling actions / Graph neural networks / Evaluation graphs

References

[1] HuangP, LiZ, WenC, LessanJ, CormanF, FuL. Modeling train timetables as images: A cost-sensitive deep learning framework for delay propagation pattern recognition. Expert Syst Appl, 2021, 177. 114996

[2] CacchianiV, HuismanD, KiddM, KroonL, TothP, VeelenturfL, WagenaarJ. An overview of recovery models and algorithms for real-time railway rescheduling. Transp Res Part B: Methodol, 2014, 63: 15-37.

[3] HuangP, LiZ, ZhuY, WenC, CormanF. Train traffic control in merging stations: a data-driven approach. Transp Res Part C: Emerg Technol, 2023, 152. 104155

[4] BinderS, MaknoonY, BierlaireM. The multi-objective railway timetable rescheduling problem. Transp Res Part C: Emerg Technol, 2017, 78: 78-94.

[5] GeX, JiangC, QinY, HuangP. Modelling the cascading effects of train delay patterns and inter-train control actions with Bayesian networks. Int J Rail Transp, 2023, 12(3): 555-580.

[6] OnetoL, FumeoE, ClericoG, CanepaR, PapaF, DambraC, MazzinoN, AnguitaD. Dynamic delay predictions for large-scale railway networks: deep and shallow extreme learning machines tuned via thresholdout. IEEE Trans Syst, Man, Cybern: Syst, 2017, 47(10): 2754-2767.

[7] PangZ, WangL, WangS, LiL, PengQ. Dynamic train dwell time forecasting: a hybrid approach to address the influence of passenger flow fluctuations. Railway Eng Sci, 2023, 31(4): 351-369.

[8] WenC, HuangP, LiZ, LessanJ, FuL, JiangC, XuX. Train dispatching management with data-driven approaches: a comprehensive review and appraisal. IEEE Access, 2019, 7: 114547-114571.

[9] CormanF, KecmanP. Stochastic prediction of train delays in real-time using Bayesian networks. Transp Res Part C: Emerg Technol, 2018, 95: 599-615.

[10] GoverdeRM. A delay propagation algorithm for large-scale railway traffic networks. Transp Res Part C: Emerg Technol, 2010, 18(3): 269-287.

[11] WangK, HuH, ZhengZ, HeZ, ChenL. Study on power factor behavior in high-speed railways considering train timetable. IEEE Trans Transp Electrif, 2017, 4(1): 220-231.

[12] Szpigel B (1973) Optimal train scheduling on a single line railway.

[13] SharmaB, PellegriniP, RodriguezJ, ChaudharyN. A review of passenger-oriented railway rescheduling approaches. Eur Transp Res Rev, 2023, 15114.

[14] ZhanS, XieJ, WongS, ZhuY, CormanF. Handling uncertainty in train timetable rescheduling: a review of the literature and future research directions. Transp Res Part E: Logist Transp Rev, 2024, 183. 103429

[15] FengT, LusbyRM, ZhangY, PengQ. Integrating train service route design with passenger flow allocation for an urban rail transit line. Eur J Oper Res, 2024, 313(1): 146-170.

[16] HongX, MengL, D’ArianoA, VeelenturfLP, LongS, CormanF. Integrated optimization of capacitated train rescheduling and passenger reassignment under disruptions. Transp Res Part C: Emerg Technol, 2021, 125. 103025

[17] LuanX, CormanF. Passenger-oriented traffic control for rail networks: An optimization model considering crowding effects on passenger choices and train operations. Transp Res Part B: Methodol, 2022, 158: 239-272.

[18] Liu X, Zhou M, Ma J et al (2022) A two-stage stochastic programming approach for timetable rescheduling with reassignment of rolling stock under uncertain disruptions. In: 2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC). Macau, pp 4349–4354.

[19] VeelenturfLP, KroonLG, MarótiG. Passenger oriented railway disruption management by adapting timetables and rolling stock schedules. Transp Res Part C: Emerg Technol, 2017, 80: 133-147.

[20] LiuX, ZhouM, DongH, WuX, LiY, WangF-Y. ADMM-based joint rescheduling method for high-speed railway timetabling and platforming in case of uncertain perturbation. Transp Res Part C: Emerg Technol, 2023, 152. 104150

[21] PengS, YangX, DingS, WuJ, SunH. A dynamic rescheduling and speed management approach for high-speed trains with uncertain time-delay. Inf Sci, 2023, 632: 201-220.

[22] XuP, CormanF, PengQ, LuanX. A train rescheduling model integrating speed management during disruptions of high-speed traffic under a quasi-moving block system. Transp Res Part B: Methodol, 2017, 104: 638-666.

[23] ZhanS, WangP, WongS, LoS. Energy-efficient high-speed train rescheduling during a major disruption. Transp Res Part E: Logist Transp Rev, 2022, 157. 102492

[24] YuanJ, GaoY, LiS, LiuP, YangL. Integrated optimization of train timetable, rolling stock assignment and short-turning strategy for a metro line. Eur J Oper Res, 2022, 301(3): 855-874.

[25] WangP, TrivellaA, GoverdeRM, CormanF. Train trajectory optimization for improved on-time arrival under parametric uncertainty. Transp Res Part C: Emerg Technol, 2020, 119. 102680

[26] YinJ, YangL, D’ArianoA, TangT, GaoZ. Integrated backup rolling stock allocation and timetable rescheduling with uncertain time-variant passenger demand under disruptive events. INFORMS J Comput, 2022, 34(6): 3234-3258.

[27] YangL, LiK, GaoZ. Train timetable problem on a single-line railway with fuzzy passenger demand. IEEE Trans Fuzzy Syst, 2008, 17(3): 617-629.

[28] CormanF, D’ArianoA, PacciarelliD, PranzoM. A tabu search algorithm for rerouting trains during rail operations. Transp Res Part B: Methodol, 2010, 44(1): 175-192.

[29] CormanF. Interactions and equilibrium between rescheduling train traffic and routing passengers in microscopic delay management: A game theoretical study. Transp Sci, 2020, 54(3): 785-822.

[30] ShakibayifarM, HassannayebiE, JafaryH, SajedinejadA. Stochastic optimization of an urban rail timetable under time-dependent and uncertain demand. Appl Stoch Model Bus Ind, 2017, 33(6): 640-661.

[31] BinderS, MaknoonM, AzadehSS, BierlaireM. Passenger-centric timetable rescheduling: a user equilibrium approach. Transp Res Part C: Emerg Technol, 2021, 132. 103368

[32] HuangP, GuoJ, LiuS, CormanF. Explainable train delay propagation: a graph attention network approach. Transp Res Part E: Logist Transp Rev, 2024, 184. 103457

[33] CormanF, MengL. A review of online dynamic models and algorithms for railway traffic management. IEEE Trans Intell Transp Syst, 2014, 16(3): 1274-1284.

[34] ReynoldsE, MaherSJ. A data-driven, variable-speed model for the train timetable rescheduling problem. Comput Oper Res, 2022, 142. 105719

[35] ZhanS, WongS, ShangP, PengQ, XieJ, LoS. Integrated railway timetable rescheduling and dynamic passenger routing during a complete blockage. Transp Res Part B: Methodol, 2021, 143: 86-123.

[36] HongX, MengL, CormanF, D’ArianoA, VeelenturfLP, LongS. Robust capacitated train rescheduling with passenger reassignment under stochastic disruptions. Transp Res Rec, 2021, 2675(12): 214-232.

[37] NianR, LiuJ, HuangB. A review on reinforcement learning: Introduction and applications in industrial process control. Comput Chem Eng, 2020, 139. 106886

[38] ŠemrovD, MarsetičR, ŽuraM, TodorovskiL, SrdicA. Reinforcement learning approach for train rescheduling on a single-track railway. Transp Res Part B: Methodol, 2016, 86: 250-267.

[39] Zhu Y, Wang H, Goverde RM (2020) Reinforcement learning in railway timetable rescheduling. In: 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC). 20–23 September 2020, Rhodes

[40] SuB, D’ArianoA, SuS, WangX, TangT. Integrated train timetabling and rolling stock rescheduling for a disturbed metro system: a hybrid deep reinforcement learning and adaptive large neighborhood search approach. Comput Ind Eng, 2023, 186. 109742

[41] KhadilkarH. A scalable reinforcement learning algorithm for scheduling railway lines. IEEE Trans Intell Transp Syst, 2018, 20(2): 727-736.

[42] LiaoJ, YangG, ZhangS, ZhangF, GongC. A deep reinforcement learning approach for the energy-aimed train timetable rescheduling problem under disturbances. IEEE Trans Transp Electrif, 2021, 7(4): 3096-3109.

[43] LuoJ, PengQ, WenC, WenW, HuangP. Data-driven decision support for rail traffic control: a predictive approach. Expert Syst Appl, 2022, 207. 118050

[44] HuangP, WenC, FuL, PengQ, TangY. A deep learning approach for multi-attribute data: A study of train delay prediction in railway systems. Inf Sci, 2020, 516: 234-253.

[45] ShiR, XuX, LiJ, LiY. Prediction and analysis of train arrival delay based on XGBoost and Bayesian optimization. Appl Soft Comput, 2021, 109. 107538

[46] KecmanP, GoverdeRM. Online data-driven adaptive prediction of train event times. IEEE Trans Intell Transp Syst, 2014, 16(1): 465-474.

[47] HuangP, SpanningerT, CormanF. Enhancing the understanding of train delays with delay evolution pattern discovery: a clustering and Bayesian network approach. IEEE Trans Intell Transp Syst, 2022, 23(9): 15367-15381.

[48] Heglund JS, Taleongpong P, Hu S et al (2020) Railway Delay Prediction with Spatial-Temporal Graph Convolutional Networks. In: 2020 IEEE 23rd International Conference on Intelligent Transportation Systems (ITSC). 20–23 September 2020, Rhodes

[49] ZhangD, YiX, PengY, ZhangY, DaohuaW, WangH, LiuJ, MohammedS, CalviA. Prediction of train station delay based on multiattention graph convolution network. J Advan Transp, 2022, 2022: 1-12.

[50] LiZ, HuangP, WenC, DongW, JiY, RodriguesF. Railway network delay evolution: a heterogeneous graph neural network approach. Appl Soft Comput, 2024, 159. 111640

[51] LindfeldtA, SipiläH. Simulation of freight train operations with departures ahead of schedule. Trans Built Environ, 2014, 135: 239-249.

[52] Jusup M, Trivella A, Corman F (2021) A review of real-time railway and metro rescheduling models using learning algorithms. In: 21st Swiss Transport Research Conference (STRC 2021). 12–14 September 2021, Ascona

[53] Velickovic P, Cucurull G, Casanova A et al (2017) Graph attention networks. In: 6th International Conference on Learning Representations, Vancouver, pp 1–12

Funding

National Nature Science Foundation of China(72301221)

National Key Research and Development Program of China(2022YFB4300502)

China Postdoctoral Science Foundation(2023M741956)

RIGHTS & PERMISSIONS

The Author(s)

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.