Column Generation for Integrated Railway Crew Scheduling and Rostering : An Application to SJ

Sammanfattning

With the increasing use of railway transportation, efficient techniques for solving related personnel scheduling problems are becoming increasingly important. Traditionally, such problems have been solved by decomposing them into two smaller problems: the Crew Scheduling Problem (CSP) and the Crew Rostering Problem (CRP). This thesis investigates the possibility of achieving better overall solutions by combining the CSP and CRP into an Integrated Scheduling Rostering Problem (INT) for realistic railway instances based on data from the Swedish railway operator SJ. Column Generation models for the CSP, CRP, and INT are proposed. The resulting subproblems take the form of resource-constrained shortest path problems, for which tailored labeling algorithms are developed. Several acceleration strategies are introduced to improve computational performance, and different initialization schemes for the INT are explored. The results demonstrate improved computational performance of the column generation approach compared with the search-based method, as well as significant speedups from the tailored labeling algorithms relative to commercial solvers. The INT is also shown to achieve better solutions than the sequential approach. The main advantage of the INT is its ability to find solutions requiring fewer rosters. For the largest INT instances, long computation times remains a challenge. The results, however, indicate that early termination of the column generation procedure, together with extrapolation from shorter planning horizons, can provide high-quality solutions while significantly improving computation times.