Two-level decomposition algorithm for crew rostering problems with fair working condition

•Two-level decomposition algorithm is proposed for crew rostering problem.•The original problem is decomposed into the upper level master problem and the lower level subproblems.•Effective cuts are developed to reduce search space.•Computational results show that 1.6% of the duality gap can be obtained for a practical problem with 81 duties and 6 rosters.•The performance is shown to be effective by comparing with that of the constraint programming solver.

A typical railway crew scheduling problem consists of two phases: a crew pairing problem to determine a set of crew duties and a crew rostering problem. The crew rostering problem aims to find a set of rosters that forms workforce assignment of crew duties and rest periods satisfying several working regulations. In this paper, we present a two-level decomposition approach to solve railway crew rostering problem with the objective of fair working condition. To reduce computational efforts, the original problem is decomposed into the upper-level master problem and the lower-level subproblem. The subproblem can be further decomposed into several subproblems for each roster. These problems are iteratively solved by incorporating cuts into the master problem. We show that the relaxed problem of the master problem can be formulated as a uniform parallel machine scheduling problem to minimize makespan, which is NP-hard. An efficient branch-and-bound algorithm is applied to solve the master problem. Effective valid cuts are developed to reduce feasible search space to tighten the duality gap. Using data provided by the railway company, we demonstrate the effectiveness of the proposed method compared with that of constraint programming techniques for large-scale problems through computational experiments.