Benders Decomposition for Robust Tactical Crew Scheduling

We consider robust tactical crew scheduling for a large passenger railway operator, whose timetable is subject to minor but uncertain updates on a weekly basis. Before the start of the planning period we must select a number of templates, specifying the time windows in which crew is supposed to work. These templates must be cost-efficient whilst providing sufficient capacity for the realised updated timetables. 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 Bart van Rossum

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.