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

• Autorzy: Engels Stefan , Wille Robert

Identyfikatory

DOI

10.15439/2024F3041

• Konferencja: Federated Conference on Computer Science and Information Systems (19 ; 08-11.09.2024 ; Belgrade, Serbia)
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

computer science; design automation; pipeline; layout; process control; transportation; optimization method; routing; control system; planning

PL

informatyka; automatyzacja projektowania; rurociąg; układ; sterowanie procesem; transport; metoda optymalizacji; trasowanie; system sterowania; planowanie

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2024
• Tom: Vol. 39
• Strony: 585--590
• Opis fizyczny: Bibliogr. 15 poz., il., wykr., wz.

Twórcy

autor

Engels Stefan

• Chair for Design Automation, Technical University of Munich (TUM), 80333 Munich, Germany

autor

Wille Robert

• Software Competence Center Hagenberg GmbH (SCCH), 4232 Hagenberg, Austria

Bibliografia

• 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

Uwagi

Thematic Sessions: Short Papers