Benders Decomposition for Robust Tactical Crew Scheduling

Moreover, the templates must be compatible with the rostering process, i.e., we wish to limit the number of different templates used and ensure that there are not too many templates on early or late moments of the day. Throughout the planning period, the templates are assumed to be fixed and the updated timetable is released on a weekly basis.

All tasks in the timetable must be covered using the capacity provided by the templates, or, if necessary, costly reserve capacity. We model the template selection problem as a scenario-based robust optimisation model, for which we propose a Benders decomposition algorithm. We conduct computational experiments on real-life instances from Netherlands Railways and show that our algorithm is able to solve instances featuring up to three scenarios and up to 1,000 tasks per scenario to optimality.

Including more scenarios, allowing for more flexibility in choosing templates, or enlarging the template length all lead to reductions in reserve crew costs without increasing template-based crew costs.

About the speaker

Bart van Rossum is a PhD candidate at the Econometric Institute under the supervision of prof.dr. Dennis Huisman and dr. Twan Dollevoet. His work focuses on large-scale railway crew scheduling, featuring a close collaboration with Netherlands Railways, and fairness-oriented optimisation.

Coordinators

Ruben van Beesten, Olga Kuryatnikova, Ece Karakoyun.