An Optimization-Based Decision Support Tool for Incremental Train Timetabling
Tóm tắt
We consider the typical workflow of a route planner in the context of short-term train timetabling, that is, the incremental process of adjusting a timetable for the next day or up to the next year. This process usually alternates between (1) making rough modifications to an existing timetable (e.g., shifting the departure of a train by half an hour) and then (2) making small adjustments to regain feasibility (e.g., reduce or increase the dwell time of some trains in some stations). The most time-consuming element of this process is related to the second step, that is to manually eliminate all conflicts that may arise after a timetable has been modified. In this work, we propose a mixed-integer programming model tailored to solve precisely this problem, that is to find a conflict-free timetable that is as close as possible to a given one. Previous related work mostly focused on creating complex models to produce “optimal” timetables from scratch, which ultimately resulted in little to no practical applications. By using a simpler model, and by trusting route planners in steering the process towards a timetable with the desired qualities, we can get closer to handle real-life instances. The model has been integrated in a user interface that was tested and validated by Norwegian route planners to plan the yearly timetable of a busy railway line in Norway.
Tài liệu tham khảo
Cacchiani V, Toth P (2012) Nominal and robust train timetabling problems. Eur J Oper Res 219(3):727–737
Cacchiani V, Toth P (2018) Robust train timetabling. Handbook of Optimization in the Railway Industry, pp 93–115
Caimi G, Kroon L, Liebchen C (2017) Models for railway timetable optimization: applicability and applications in practice. J Rail Transp Plan Manag 6(4):285–312
Galli L, Stiller S (2018) Modern challenges in timetabling. Handbook of Optimization in the Railway Industry, pp. 117–140
Harrod SS (2012) A tutorial on fundamental model structures for railway timetable optimization. Surv Oper Res Manag Sci 17(2):85–96
Kümmling M, Großmann P, Nachtigall K, Opitz J, Weiß R (2015) A state-of-the-art realization of cyclic railway timetable computation. Public Transp 7(3):281–293
Lusby RM, Larsen J, Ehrgott M, Ryan D (2011) Railway track allocation: models and methods. OR Spectr 33(4):843–883
Castillo E, Gallego I, Ureña JM, Coronado JM (2009) Timetabling optimization of a single railway track line with sensitivity analysis. TOP 17(2):256–287
Forsgren M, Aronsson M, Kreuger P, Dahlberg H (2011) The Maraca: a tool for minimizing resource conflicts in a non-periodic railway timetable. In: RailRome 2011
Lamorgese L, Mannino C, Natvig E (2017) An exact micro-macro approach to cyclic and non-cyclic train timetabling. Omega 72:59–70
Liu SQ, Kozan E (2009) Scheduling trains as a blocking parallel-machine job shop scheduling problem. Comput Oper Res 36(10):2840–2852
Yang L, Gao Z, Li K (2010) Passenger train scheduling on a single-track or partially double-track railway with stochastic information. Eng Optim 42(11):1003–1022
Caimi G, Laumanns M, Schüpbach K, Wörner S, Fuchsberger M (2011) The periodic service intention as a conceptual framework for generating timetables with partial periodicity. Transp Plan Technol 34(4):323–339
Lamorgese L, Mannino C (2015) An exact decomposition approach for the real-time train dispatching problem. Oper Res 63(1):48–64
Sartor G, Mannino C, Nygreen T, Bach L (2023) A MILP model for quasi-periodic strategic train timetabling. Omega 116:102798
de Fabris S, Longo G, Medeossi G, Pesenti R (2014) Automatic generation of railway timetables based on a mesoscopic infrastructure model. J Rail Transp Plan Manag 4(1–2):2–13
Mascis A, Pacciarelli D (2002) Job-shop scheduling with blocking and no-wait constraints. Eur J Oper Res 143(3):498–517
Leutwiler F, Corman F (2022) A logic-based benders decomposition for microscopic railway timetable planning. Eur J Oper Res 303(2):525–540
Mannino CNakkerud A (2023) Optimal train rescheduling in Oslo central station. Omega 116(C)
Lamorgese L, Mannino C (2019) A noncompact formulation for job-shop scheduling problems in traffic management. Oper Res 67(6):1586–1609
Sartor G, Mannino C, Bach L (2019) Combinatorial learning in traffic management. In: Machine Learning, Optimization, and Data Science: 5th International Conference, LOD 2019, Siena, Italy, September 10–13, 2019, Proceedings 5, pp. 384–395. Springer
Gurobi Optimization (2023) LLC: Gurobi Optimizer Reference Manual. https://www.gurobi.com
Bane NOR: Sprengt kapasitet på jernbanen fra Lysaker til Bodø. Accessed on July 4, 2023. https://www.banenor.no/nyheter-og-aktuelt/nyheter/2023/sprengt-kapasitet-pa-jernbanen-fra-lysaker-til-bodo/