Integrated optimization approach to metro crew scheduling and rostering

You are here: Homepage > Search

Integrated optimization approach to metro crew scheduling and rostering

Zhou, Jue / Xu, Xiaoming / Long, Jiancheng / Ding, Jianxun

Highlights • Integrated optimization of crew scheduling and rostering can improve the use of crew. • A multi-commodity network flow model for the integrated problem is formulated. • A Lagrangian relaxation heuristic is developed to solve the integrated problem. • Computational study reports the benefits obtained by the proposed approach.

Abstract 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.