Integrated optimization approach to metro crew scheduling and rostering
Document Type
Journal Article
Publication Date
2021
Subject Area
mode - subway/metro, planning - integration, planning - methods
Keywords
Metro, Crew scheduling, Crew rostering, Time–space network, Lagrangian relaxation
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.
Rights
Permission to publish the abstract has been given by Elsevier, copyright remains with them.
Recommended Citation
Zhou, J., Xu, X., Long, J., & Ding, J. (2021). Integrated optimization approach to metro crew scheduling and rostering. Transportation Research Part C: Emerging Technologies, Vol. 123, 102975.
Comments
Transportation Research Part C Home Page:
http://www.sciencedirect.com/science/journal/0968090X