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.
|column generation, crew re-scheduling, large-scale optimization, railways, transportation|
|Econometric Institute Research Papers|
|Report / Econometric Institute, Erasmus University Rotterdam|
|Organisation||Erasmus School of Economics|
Huisman, D. (2005). A column generation approach to solve the crew re-scheduling problem (No. EI 2005-54). Report / Econometric Institute, Erasmus University Rotterdam. Retrieved from http://hdl.handle.net/1765/7149