Integrated optimization approach to metro crew scheduling and rostering

Due to its complexity, the metro crew management problem is usually decomposed into a crew scheduling problem and a crew rostering problem. These two decomposed problems are often performed separately in a sequential manner, which may result in solutions that are inferior to those obtained via an integrated framework. Accordingly, this study seeks to develop an integrated optimization approach to model and solve the metro crew scheduling problem and the crew rostering problem simultaneously. To this end, we firstly construct a multi-layer time-space network, in which each layer represents a duty. We then formulate the considered problem as a minimum-cost multi-commodity network flow problem in which each crew is regarded as a commodity and present a Lagrangian relaxation heuristic to solve the proposed network flow problem. Finally, we conduct a computational study using the real-life data to test the effectiveness of our Lagrangian relaxation heuristic, compare the performance of our heuristic with the benchmark solution, and report the benefits obtained via the proposed integrated optimization approach.