Proceedings

Linear-Time Optimal Deadlock Detection for Efficient Scheduling in Multi-Track Railway Networks

Download BibTeX Cite

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. Main Track. Pages 5799-5807.

https://doi.org/10.24963/ijcai.2024/641

© 2024 International Joint Conferences on Artificial Intelligence

Abstract

The railway scheduling problem requires the computation of an operable timetable that satisfies constraints involving railway infrastructure and resource occupancy times, while minimising average delay over a set of events. Since this problem is computationally hard, practical solutions typically roll out feasible (but suboptimal) schedules one step at a time, by choosing which train to move next in every step. The choices made by such algorithms are necessarily myopic, and incur the risk of driving the system to a deadlock. To escape deadlocks, the predominant approach is to stay away from states flagged as potentially unsafe by some fast-to-compute rule R. While many choices of R guarantee deadlock avoidance, they are suboptimal in the sense of also flagging some safe states as unsafe. In this paper, we revisit the literature on process scheduling and describe a rule R0 that is (i) necessary and sufficient for deadlock detection when the network has at least two tracks in each resource (station / track section), (ii) computable in linear time, and (iii) yields lower delays when combined with existing scheduling algorithms on both synthetic and real data sets from Indian Railways.

  1. [Agarwal, 2022] Keshav Agarwal. Real-time railway scheduling. Master's thesis, Indian Institute of Technol- ogy Bombay, 2022.
  2. [Araki et al., 1977] Toshiro Araki, Yuji Sugiyama, Tadao Kasami, and Jun Okui. Complexity of the deadlock avoid- ance problem. In 2nd IBM Symp. on Mathematical Foun- dations of Computer Science, pages 229-257, 1977.
  3. [Cai and Goh, 1994] X Cai and C Goh. A fast heuristic for the train scheduling problem. Computers & Op. Res., 21(5):499-510, 1994.
  4. [Chen et al., 2015] L Chen, C Roberts, F Schmid, and E Stewart. Modeling and solving real-time train reschedul- ing problems in railway bottleneck sections. IEEE Trans. on Intelligent Transportation Systems, 16(4):1896-1904, 2015.
  5. [Cocco and Monasson, 2001] Simona Cocco and Rémi Monasson. Trajectories in phase diagrams, growth processes, and computational complexity: How search algorithms solve the 3-satisfiability problem. Physical review letters, 86(8):1654, 2001.
  6. [Fanti et al., 1997] Maria Pia Fanti, Bruno Maione, Saverio Mascolo, and A Turchiano. Event-based feedback con- trol for deadlock avoidance in flexible production sys- tems. IEEE Transactions on Robotics and Automation, 13(3):347-363, 1997.
  7. [Gold, 1978] E Mark Gold. Deadlock prediction: Easy and difficult cases. SIAM Journal on Computing, 7(3):320- 336, 1978.
  8. [Goverde, 2010] Rob MP Goverde. A delay propaga- tion algorithm for large-scale railway traffic networks. Transportation Research Part C: Emerging Technologies, 18(3):269-287, 2010.
  9. [Higgins et al., 1996] A Higgins, E Kozan, and L Ferreira. Optimal scheduling of trains on a single line track. Trans- portation Research Part B, 30(2):147-161, 1996.
  10. [Higgins et al., 1997] A Higgins, E Kozan, and L Ferreira. Heuristic techniques for single line train scheduling. Jour- nal of Heuristics, 3(1):43-62, 1997.
  11. [Khadilkar, 2017a] Harshad Khadilkar. Data-enabled stochastic modeling for evaluating schedule robust- ness of railway networks. Transportation Science, 51(4):1161-1176, 2017.
  12. [Khadilkar, 2017b] Harshad Khadilkar. Scheduling of vehi- cle movement in resource-constrained transportation net- works using a capacity-aware heuristic. In 2017 Ameri- can Control Conference (ACC), pages 5617-5622. IEEE, 2017.
  13. [Khadilkar, 2018] Harshad Khadilkar. A scalable reinforce- ment learning algorithm for scheduling railway lines. IEEE Transactions on Intelligent Transportation Systems, 20(2):727-736, 2018.
  14. [Liu and Kozan, 2009] S Liu and E Kozan. Scheduling trains as a blocking parallel-machine job shop scheduling prob- lem. Computers & Operations Research, 36(10):2840- 2852, 2009.
  15. [Lovett et al., 2015] Alexander H Lovett, C Tyler Dick, and Christopher PL Barkan. Determining freight train delay costs on railroad lines in north america. Proceedings of Rail Tokyo, 2015.
  16. [Mackenzie, 2010] S. Mackenzie. Train scheduling on long haul railway corridors. PhD thesis, University of South Australia, 2010.
  17. [Manne, 1960] Alan S Manne. On the job-shop scheduling problem. Operations research, 8(2):219-223, 1960.
  18. [Mascis and Pacciarelli, 2002] Alessandro Mascis and Dario Pacciarelli. Job-shop scheduling with blocking and no- wait constraints. European Journal of Operational Re- search, 143(3):498-517, 2002.
  19. [Pachl, 2012] Jörn Pachl. Deadlock avoidance in railroad op- erations simulations. In PROMET Traffic & Transporta- tion, pages 359-369, 2012.
  20. [Pappaterra et al., 2021] Mauro José Pappaterra, Francesco Flammini, Valeria Vittorini, and Nikola Bešinović. A sys- tematic review of artificial intelligence public datasets for railway applications. Infrastructures, 6(10):136, 2021.
  21. [Prasad et al., 2021] Rohit Prasad, Harshad Khadilkar, and Shivaram Kalyanakrishnan. Optimising a real-time sched- uler for Indian railway lines by policy search. In 2021 Seventh Indian Control Conference (ICC), pages 75-80. IEEE, 2021.
  22. [Preston et al., 2009] John Preston, Graham Wall, Richard Batley, J Nicolás Ibáñez, and Jeremy Shires. Impact of delays on passenger train services: evidence from great britain. Transportation research record, 2117(1):14-23, 2009.
  23. [Reveliotis et al., 1997] Spiridon A Reveliotis, Mark A Law- ley, and Placid M Ferreira. Polynomial-complexity dead- lock avoidance policies for sequential resource alloca- tion systems. IEEE transactions on automatic control, 42(10):1344-1357, 1997.
  24. [Russell and Norvig, 2022] Stuart Russell and Peter Norvig. Artificial intelligence : a Modern Approach. Pearson Ed- ucation, 4th edition, 2022.
  25. [Schlake et al., 2011] Bryan W Schlake, Christopher PL Barkan, and J Riley Edwards. Train delay and economic impact of in-service failures of railroad rolling stock. Transportation research record, 2261(1):124-133, 2011.
  26. [Šemrov et al., 2016] Darja Šemrov, Rok Marsetič, Marijan Žura, Ljupčo Todorovski, and Aleksander Srdic. Rein- forcement learning approach for train rescheduling on a single-track railway. Trans. Res. Part B: Methodological, 86:250-267, 2016.
  27. [Sinha et al., 2016] Sudhir Kumar Sinha, Shripad Salsingikar, and Siddhartha SenGupta. An iterative bi-level hierarchical approach for train scheduling. Journal of Rail Transport Planning & Management, 6(3):183-199, 2016.
  28. [Strotmann, 2007] Christian Strotmann. Railway scheduling problems and their decomposition. PhD thesis, Univ. Os- nabrück, 2007.
  29. [Tesauro and Galperin, 1996] Gerald Tesauro and Gregory Galperin. On-line policy improvement using monte-carlo search. Advances in Neural Information Processing Sys- tems, 9, 1996.
  30. [Törnquist and Persson, 2007] Johanna Törnquist and Jan A Persson. N-tracked railway traffic re-scheduling during disturbances. Transportation Research Part B: Method- ological, 41(3):342-362, 2007.
  31. [Vujanic and Hill, 2022] Robin Vujanic and Andrew J Hill. Computationally efficient dynamic traffic optimization of railway systems. IEEE Transactions on Intelligent Trans- portation Systems, 23(5):4706-4719, 2022.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards