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.
two-level decomposition algorithm crew rostering railway scheduling cut generation