Logo PTI Logo FedCSIS

Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 39

Comparing Lazy Constraint Selection Strategies in Train Routing with Moving Block Control

,

DOI: http://dx.doi.org/10.15439/2024F3041

Citation: Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 39, pages 585–590 ()

Full text

Abstract. Railroad transportation plays a vital role in the future of sustainable mobility. Besides building new infrastructure, capacity can be improved by modern train control systems, e.g., based on moving blocks. At the same time, there is only limited work on how to optimally route trains using the potential gained by these systems. Recently, an initial approach for train routing with moving block control has been proposed to address this demand. However, detailed evaluations on so-called lazy constraints are missing, and no publicly available implementation exists. In this work, we close this gap by providing an extended approach as well as a flexible open-source implementation that can use different solving strategies. Using that, we experimentally evaluate what choices should be made when implementing a lazy constraint approach. The corresponding implementation and benchmarks are publicly available as part of the Munich Train Control Toolkit (MTCT) at https://github.com/cda-tum/mtct.

References

  1. J. Pachl, Railway Signalling Principles: Edition 2.0, 2021. [Online]. Available: http://dx.doi.org/10.24355/dbbs.084-202110181429-0
  2. L. Schnieder, Communications-Based Train Control (CBTC). Springer Berlin Heidelberg, 2021. [Online]. Available: http://dx.doi.org/10.1007/978-3-662-62876-8
  3. R. Borndörfer, T. Klug, L. Lamorgese, C. Mannino, M. Reuther, and T. Schlechte, Eds., Handbook of Optimization in the Railway Industry, 2018. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-72153-8
  4. T. Schlechte, R. Borndörfer, J. Denißen, S. Heller, T. Klug, M. Küpper, N. Lindner, M. Reuther, A. Söhlke, and W. Steadman, “Timetable optimization for a moving block system,” Journal of Rail Transport Planning & Management, vol. 22, 2022. [Online]. Available: http://dx.doi.org/10.1016/j.jrtpm.2022.100315
  5. T. Klug, M. Reuther, and T. Schlechte, “Does laziness pay off? - a lazy-constraint approach to timetabling,” in 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), 2022. [Online]. Available: http://dx.doi.org/10.4230/OASIcs.ATMOS.2022.11
  6. Siemens, Bombardier, Mermec, Network Rail, and Thales, “Deliverable D4.2 moving block enhancements,” in X2Rail-5 Completion of activities for Adaptable Communication, Moving Block, Fail Safe Train Localisation (including satellite), Zero on site Testing, Formal Methods and Cyber Security. Shift2Rail, 2023. [Online]. Available: https://projects.shift2rail.org/s2r_ip2_n.aspx?p=X2RAIL-5
  7. Siemens, Hitachi Rail STS, Bombardier, Thales, Network Rail, Alstom, CAF, Trafikverket, AZD, Mermec, Deutsche Bahn, SNCF, and ERTMS Users Group, “Deliverable D5.1 moving block system specification,” in X2Rail-1 Start-up activities for Advanced Signalling and Automation Systems. Shift2Rail, 2019. [Online]. Available: https://projects.shift2rail.org/s2r_ip2_n.aspx?p=X2RAIL-1
  8. S. Engels, T. Peham, J. Przigoda, N. Przigoda, and R. Wille, “Design tasks and their complexity for the European Train Control System with hybrid train detection,” 2024. [Online]. Available: http://dx.doi.org/10.48550/arXiv.2308.02572
  9. R. Wille, T. Peham, J. Przigoda, and N. Przigoda, “Towards automatic design and verification for Level 3 of the European Train Control System,” in Design, Automation & Test in Europe Conference & Exhibition (DATE), 2021. [Online]. Available: http://dx.doi.org/10.23919/date51398.2021.9473935
  10. T. Peham, J. Przigoda, N. Przigoda, and R. Wille, “Optimal railway routing using virtual subsections,” in Reliability, Safety, and Security of Railway Systems. Modelling, Analysis, Verification, and Certification, 2022. [Online]. Available: http://dx.doi.org/10.1007/978-3-031-05814-1_5
  11. S. Engels, T. Peham, and R. Wille, “A symbolic design method for ETCS Hybrid Level 3 at different degrees of accuracy,” in 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), 2023. [Online]. Available: http://dx.doi.org/10.4230/OASICS.ATMOS.2023.6
  12. S. Engels and R. Wille, “Late breaking results: Iterative design automation for train control with hybrid train detection,” in Design, Automation & Test in Europe Conference & Exhibition (DATE), 2024. [Online]. Available: https://ieeexplore.ieee.org/document/10546590 http://dx.doi.org/10.23919/DATE58400.2024.10546590
  13. DB InfraGO AG, “Richtlinie 301: Signalbuch,” 2024. [Online]. Available: https://www.dbinfrago.com/web/schienennetz/netzzugang-und-regulierung/regelwerke/betrieblich-technisch_regelwerke
  14. Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2023. [Online]. Available: https://www.gurobi.com
  15. M. Bartholomeus, L. Arenas, R. Treydel, F. Hausmann, N. Geduhn, and A. Bossy, “ERTMS Hybrid Level 3,” SIGNAL + DRAHT (110) 1+2, 2018. [Online]. Available: https://www.eurailpress.de/fileadmin/user_upload/SD_1_2-2018_Bartholomaeus_ua.pdf