A column generation approach to solve the crew re-scheduling problem

When tracks are out of service for maintenance during a certain period, trains cannot be operated on those tracks. This leads to a modified timetable, and results in infeasible rolling stock and crew schedules. Therefore, these schedules need to be repaired. The topic of this paper is the rescheduling of crew. In this paper, we define the Crew Re-Scheduling Problem (CRSP). Furthermore, we show that it can be formulated as a large-scale set covering problem. The problem is solved with a column generation based algorithm. The performance of the algorithm is tested on real-world instances of NS, the largest passenger railway operator in the Netherlands. Finally, we discuss some benefits of the proposed methodology for the company.