OASIcs.ATMOS.2022.11.pdf
- Filesize: 0.55 MB
- 8 pages
Document
Does Laziness Pay Off? - A Lazy-Constraint Approach to Timetabling
Authors
Thomas Schlechte 
-
Part of:
Volume:
22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-06
File
Document Identifiers
Author Details
Cite As Get BibTex
Torsten Klug, Markus Reuther, and Thomas 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). Open Access Series in Informatics (OASIcs), Volume 106, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/OASIcs.ATMOS.2022.11
Abstract
Timetabling is a classical and complex task for public transport operators as well as for railway undertakings. The general question is: Which vehicle is taking which route through the transportation network in which order? In this paper, we consider the special setting to find optimal timetables for railway systems under a moving block regime. We directly set up on our work of [T. Schlechte et al., 2022], i.e., we consider the same model formulation and real-world instances of a moving block headway system. In this paper, we present a repair heuristic and a lazy-constraint approach utilizing the callback features of Gurobi, see [Gurobi Optimization, 2022]. We provide an experimental study of the different algorithmic approaches for a railway network with 100 and up to 300 train requests. The computational results show that the lazy-constraint approach together with the repair heuristic significantly improves our previous approaches.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Combinatorial optimization
Keywords
- Moving Block
- Railway Track Allocation
- Timetabling
- Train Routing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ralf Borndörfer, Torsten Klug, Leonardo Lamorgese, Carlo Mannino, Markus Reuther, and Thomas Schlechte, editors. Handbook of Optimization in the Railway Industry, volume 268. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-72153-8.
- 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.
- Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL: https://www.gurobi.com.
- Steven S. Harrod. A tutorial on fundamental model structures for railway timetable optimization. Surveys in Operations Research and Management Science, 17(2):85-96, 2012. URL: https://doi.org/10.1016/j.sorms.2012.08.002.
- Leonardo Lamorgese and Carlo Mannino. An exact decomposition approach for the real-time Train Dispatching problem. Operations Research, 63:48-64, 2015. URL: https://doi.org/10.1287/opre.2014.1327.
- Bianca Pascariu, Marcella Samà, Paola Pellegrini, Andrea D'Ariano, Joaquin Rodriguez, and Dario Pacciarelli. Effective train routing selection for real-time traffic management: Improved model and aco parallel computing. Computers & Operations Research, 145:105859, May 2022. URL: https://doi.org/10.1016/j.cor.2022.105859.
- Ulrich Pferschy and Rostislav Staněk. Generating subtour elimination constraints for the TSP from pure integer solutions. Central European Journal of Operations Research, 25(1):231-260, February 2016. URL: https://doi.org/10.1007/s10100-016-0437-8.
- Thomas Schlechte, Ralf Borndörfer, Jonas Denißen, Simon Heller, Torsten Klug, Michael Küpper, Niels Lindner, Markus Reuther, Andreas Söhlke, and William Steadman. Timetable optimization for a moving block system. Journal of Rail Transport Planning & Management, 22:100315, June 2022. URL: https://doi.org/10.1016/j.jrtpm.2022.100315.
- Peijuan Xu, Francesco Corman, Qiyuan Peng, and Xiaojie Luan. A train rescheduling model integrating speed management during disruptions of high-speed traffic under a quasi moving block system. Transportation Research Part B, 104:638-666, 2017. URL: https://doi.org/10.1016/j.trb.2017.05.008.