Application of column generation for railway crew scheduling problems with practical constraints

In this paper, we propose a column generation method for the railway crew scheduling problem with a variety of practical constraints such as lower and upper constraints of one continuous traveling, total working time, admissible number of crews, and meal time constraints. The proposed method consists of the two steps. The first step is to derive a lower bound by the column generation and the second step is to generate a feasible solution by a heuristic method. In the proposed method, a label setting algorithm is developed to solve the pricing problem efficiently to reduce computational time. A new dominance condition is developed to eliminate unnecessary states in the label setting algorithm. A heuristic algorithm is also proposed to reduce the generation of the infeasible solutions violating the constraint on the number of the allocated crews. The effectiveness of the proposed method is evaluated by using a real railway data.