Datum / čas
Date(s) - 10.11.
15:00 - 17:00
Kategorie ne Kategorie
Scheduling Seminar Series
Train Scheduling: Models, decomposition methods and practice
Presenter: Carlo Mannino (SINTEF & Oslo Uni.)
Join the seminar online via Youtube: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A/live
Train scheduling is one of the most critical planning tasks required to run a railway, with most rail operators and managers having large departments devoted to this task. Depending on the time scale, we have two main scheduling problems. At the strategic and tactical levels, the train timetabling problem consists in finding feasible, robust schedules that are usable for months or years into the future. At the operational level, we have the train re-scheduling problem, where one wants to schedule trains in real-time in order to tackle deviations from the original timetable, minimizing delays and knock-on effects. Both problems share a common core-model, which is a job-shop scheduling model with no-wait and blocking constraints. The core problem can be modeled as a disjunctive program. After an illustration of the train scheduling application, I will present a basic MILP formulation for the disjunctive program. It turns out, however, that even small to medium size real-life instances cannot be solved by simply instantiating this formulation and invoking a state-of-the-art MILP solver. Next, therefore, I will go through two recent reformulations, which allow us to significantly increase the size of tractable instances. The first is obtained from the classical Benders‘ reformulation by strengthening its standard constraints. The second is often referred to as „Logic Benders‘ Reformulation“ and exploits a natural, spatial decomposition of the railway network. I will finally show the strong link between these reformulations. I will conclude the talk by presenting a practical application of the described approaches to a traffic management system controlling trains in the greater Oslo region network. The system is currently undergoing a field-test campaign at Oslo control center.
The seminar is organized by Zdeněk Hanzálek (CIIRC CTU in Prague), Michael Pinedo (New Y ork University) and Guohua Wan (Shanghai Jiao Tong).
Find full info and program at https://schedulingseminar.com/.