Document Open Access Logo

A Formulation of MIP Train Rescheduling at Terminals in Bidirectional Double-Track Lines with a Moving Block and ATO

Authors Kosuke Kawazoe, Takuto Yamauchi, Kenji Tei

PDF

File

Thumbnail PDF
PDF
OASIcs.ATMOS.2022.10.pdf
  • Filesize: 0.74 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
Keywords
  • Train rescheduling
  • Mixed integer programming
  • ATO
  • Moving block

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

When delays in trains occur, train schedules are rescheduled to reduce the impact. Despite many existing studies of automated train rescheduling, this study focuses on automated rescheduling considering a moving block and Automatic Train Operation (ATO). This study enables such automated rescheduling by formalizing this problem as a mixed integer programming (MIP) model. In previous work, the formulation was achieved for unidirectional single-track railway lines. In this paper, we aim to achieve the formulation for bidirectional double-track lines. Specifically, we propose a formulation of constraints about trains’ running terminal stations. To evaluate our automated rescheduling approach, we implemented an MIP model consisting of a combination of the new constraints with the previous MIP model. We demonstrated the feasibility of our approach by applying it to a bidirectional double-track line with eight delay scenarios. We also evaluate the delay reduction and computation overhead of our approach by comparing it with a baseline with these eight scenarios. The results show that the total delay of all trains from our approach reduced from 20% to 30% than one from the baseline. On the other hand, the computation time increased from less than 1 second to a minimum of about 20 seconds and a maximum of about 1600 seconds.

Cite As Get BibTex

Kosuke Kawazoe, Takuto Yamauchi, and Kenji Tei. A Formulation of MIP Train Rescheduling at Terminals in Bidirectional Double-Track Lines with a Moving Block and ATO. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/OASIcs.ATMOS.2022.10

Author Details

Kosuke Kawazoe
  • Faculty of Science and Engineering, Waseda University, Shinjuku, Tokyo, Japan
Takuto Yamauchi
  • Faculty of Science and Engineering, Waseda University, Shinjuku, Tokyo, Japan
Kenji Tei
  • Faculty of Science and Engineering, Waseda University, Shinjuku, Tokyo, Japan

References

  1. Valentina Cacchiani, Dennis Huisman, Martin Kidd, Leo Kroon, Paolo Toth, Lucas Veelenturf, and Joris Wagenaar. An overview of recovery models and algorithms for real-time railway rescheduling. Transportation Research Part B: Methodological, 63:15-37, 2014. URL: https://doi.org/10.1016/j.trb.2014.01.009.
  2. Wei Fang, Shengxiang Yang, and Xin Yao. A survey on problem models and solution approaches to rescheduling in railway networks. IEEE Transactions on Intelligent Transportation Systems, 16(6):2997-3016, 2015. URL: https://doi.org/10.1109/TITS.2015.2446985.
  3. Zhenhuan He. Research on improved greedy algorithm for train rescheduling. In 2011 Seventh International Conference on Computational Intelligence and Security, pages 1197-1200, 2011. URL: https://doi.org/10.1109/CIS.2011.265.
  4. Zhuopu Hou, Hairong Dong, Shigen Gao, Gemma Nicholson, Lei Chen, and Clive Roberts. Energy-saving metro train timetable rescheduling model considering ato profiles and dynamic passenger flow. IEEE Transactions on Intelligent Transportation Systems, 20(7):2774-2785, 2019. URL: https://doi.org/10.1109/TITS.2019.2906483.
  5. Kosuke Kawazoe, Takuto Yamauchi, Kenji Tei, Norio Tomii, and Shinichi Honiden. Applying mip train traffic rescheduling model with automatic train control to moving block systems (japanese edition). Journal of Information Processing (Japanese Edition), 63(3), 2022. URL: https://doi.org/10.20729/00217476.
  6. Philippe Laborie, Jérôme Rogerie, Paul Shaw, and Petr Vilím. Ibm ilog cp optimizer for scheduling. Constraints, 23(2):210-250, 2018. URL: https://doi.org/10.1007/s10601-018-9281-x.
  7. Leonardo Lamorgese, Carlo Mannino, Dario Pacciarelli, and Johanna T. Krasemann. Train Dispatching. Springer, 2018. URL: https://doi.org/978-3-319-72153-8_12.
  8. Leonardo Lamorgese, Carlo Mannino, and Mauro Piacentini. Advances and Trends in Optimization with Engineering Applications. Society for Industrial and Applied Mathematics, 2017. URL: https://doi.org/10.1137/1.9781611974683.ch6.
  9. N. Miyaguchi, D. Uchiyama, I. Inaba, Y. Baba, and N. Hiura. The radio-based train control system atacs. In WIT Transactions on The Built Environment, volume 155, pages 175-183, 2015. URL: https://doi.org/10.2495/CRS140151.
  10. Robert D. Pascoe and Thomas N. Eichorn. What is communication-based train control? IEEE Vehicular Technology Magazine, 4(4):16-21, 2009. URL: https://doi.org/10.1109/MVT.2009.934665.
  11. Juliette Pochet, Sylvain Baro, and Guillaume Sandou. Supervision and rescheduling of a mixed cbtc traffic on a suburban railway line. In 2016 IEEE International Conference on Intelligent Rail Transportation (ICIRT), pages 32-38, 2016. URL: https://doi.org/10.1109/ICIRT.2016.7588547.
  12. Juliette Pochet, Sylvain Baro, and Guillaume Sandou. Automatic train supervision for a cbtc suburban railway line using multiobjective optimization. In 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), pages 1-6, 2017. URL: https://doi.org/10.1109/ITSC.2017.8317670.
  13. Kei Tamura, Keisuke Sato, and Norio Tomii. A train timetable rescheduling mip formulation with additional inequalities minimizing inconvenience to passengers. The IEICE Transactions on Information and Systems, 97(3):393-404, 2014. Google Scholar
  14. Yihui Wang, Bing Ning, Fang Cao, Bart De Schutter, and Ton J.J. van den Boom. A survey on optimal trajectory planning for train operations. In Proceedings of 2011 IEEE International Conference on Service Operations, Logistics and Informatics, pages 589-594, 2011. URL: https://doi.org/10.1109/SOLI.2011.5986629.
  15. Chao Wen, Ping Huang, Zhongcan Li, Javad Lessan, Liping Fu, Chaozhe Jiang, and Xinyue Xu. Train dispatching management with data- driven approaches: A comprehensive review and appraisal. IEEE Access, 7:114547-114571, 2019. URL: https://doi.org/10.1109/ACCESS.2019.2935106.
  16. Peijuan Xu, Dawei Zhang, Jingwei Guo, Dan Liu, and Hui Peng. Integrated train rescheduling and rerouting during multidisturbances under a quasi-moving block system. Journal of Advanced Transportation, 2021:1-15, April 2021. URL: https://doi.org/10.1155/2021/6652531.
  17. Jing Xun, Bin Ning, Ke-Ping Li, and Tao Tang. An optimization approach for real-time headway control of railway traffic. In 2013 IEEE International Conference on Intelligent Rail Transportation Proceedings, pages 25-31, 2013. URL: https://doi.org/10.1109/ICIRT.2013.6696262.
  18. Darja Šemrov, R. Marsetič, Marijan Zura, Ljupco Todorovski, and Aleksander Srdić. Reinforcement learning approach for train rescheduling on a single-track railway. Transportation Research Part B Methodological, 86:250-267, April 2016. URL: https://doi.org/10.1016/j.trb.2016.01.004.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact