A MILP model for quasi-periodic strategic train timetabling. (April 2023)

• Record Type: Journal Article
• Authors: Sartor, Giorgio; Mannino, Carlo; Nygreen, Thomas; Bach, Lukas
• Is Part Of: Omega. Volume 116(2023)
• Publication Date: 2023-04
• Subjects: Mixed-integer programming -- Train scheduling -- Quasi-periodic timetabling; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2022.102798
• Languages: English
• ISSNs: 0305-0483

Abstract

Highlights: We introduce the new concept of quasi-periodicity, for which one could build a timetable that is almost perfectly periodic, but that can be presented to customers as a perfectly periodic timetable. We develop a model for quasi-periodicity and use it to produce a set of new timetables for 4 different scenarios in a busy railway line in Norway. Three of those timetables were ultimately used by the Norwegian Railway Directorate to steer the development of new infrastructure in the Jæen line in Norway. Abstract: In railways, the long-term strategic planning is the process of evaluating improvements to the railway network (e.g., upgrading a single track line to a double track line) and changes to the composition/frequency of train services (e.g., adding 1 train per hour along a certain route). The effects of different combinations of infrastructure upgrades and updated train services (also called scenarios), are usually evaluated by creating new feasible timetables followed by extensive simulation. Strategic Train Timetabling (STT) is indeed the task of producing new tentative timetables for these what-if scenarios. Unlike the more classic train timetabling, STT can often overlook (or at least give less importance to) some complementary aspects, such as crew and rolling stock scheduling. On the other hand, the different scenarios are likely to lead to very different timetables, hindering the common and effective practice of using existing timetables to warm start the solution process. We introduce the concept of quasi-periodic timetables, that are timetables where certain subsets of trains need to start at almost (rather than precisely) the same minute of every period. The additional flexibility offered by quasi-periodic timetables turned out to be crucial in real-life scenarios characterized by elevated train traffic. We describe a MILP based approach for strategic quasi-periodic train timetabling and we test it on 4 different realistic what-if scenarios for an important line in Norway. The timetables produced by our algorithm were ultimately used by the Norwegian Railway Directorate to select 3 out of the 4 scenarios for phasing the progressive expansion of the JȪren line.