A column generation approach to railway crew recovery problem in disruption

Crew Recovery Problem frequently appears in transport industries. This problem is to modify schedules of crews who cannot perform their tasks in their duties given beforehand as the result from Crew Scheduling Problem because of delays of trains or flights. To obtain a good modified schedule of crews is needed when delay occurs while it is more important to find alternative and acceptable schedule(s) quickly. In this paper, we formulate the problem in railways as an integer programming problem and propose an approach to this as a basic framework for similar problems arising in transport industries. Our heuristic approach is based on the idea of column generation method, which is one of the effective and powerful methods for large scale integer programming problems. The procedure generates various schedules for a certain instance by gradually increasing the number of crews to be rescheduled, giving the lower bound to the optimal value of the objective function in each iteration. Numerical experiments are performed to instances from Japanese railway. The results indicate that our approach successfully gives good schedules in short computation time.