A Column Generation Approach for the Integrated Crew Re-Planning Problem

In this paper, we propose a column generation approach for crew re-planning, i.e., the construction of new duties and rosters for the employees, given changes in the timetable and rolling stock schedule. In the current practice, the feasibility of the new rosters is `assured' by allowing the new duties to deviate only slightly from the original ones. In the Integrated Crew Re-Planning Problem (ICRPP), we loosen this requirement and allow more exibility: The ICRPP considers the re-scheduling of crew for multiple days simultaneously, thereby explicitly taking the feasibility of the rosters into account, and hence allowing arbitrary deviations from the original duties. We propose a mathematical formulation for the ICRPP and develop a column generation approach to solve the problem. We apply our solution approach to practical instances from NS, and show the benefit of integrating the re-scheduling process.