An ADMM-based dual decomposition mechanism for integrating crew scheduling and rostering in an urban rail transit line

Authors

Tao Feng
Richard M. Lusby
Yongxiang Zhang
Qiyuan Peng
Pan Shang
Siyu Tao

Document Type

Journal Article

Publication Date

2023

Subject Area

place - asia, place - urban, mode - rail, organisation - workforce planning

Keywords

urban rail transit (URT), Crew planning

Abstract

The crew planning problem is a key step in the urban rail transit (URT) planning process and has a critical impact on the operational efficiency of a URT line. In general, the crew planning problem consists of two subproblems, crew scheduling and crew rostering, which are usually solved in a sequential manner. Such an approach may, however, lead to a poor-quality crew plan overall. We therefore study the integrated optimization of crew scheduling and crew rostering and propose an effective dual decomposition approach. In particular, we formulate the integrated problem as an integer programming model using a space–time-state network representation, where the objective of the model is to minimize the weighted sum of total travel cost and penalties associated with imbalances in the workloads of the crew members. Then, an Alternating Direction Method of Multipliers (ADMM)-based dual decomposition mechanism that decomposes the model into a set of independent crew member-specific subproblems is introduced, where each of these subproblems is efficiently solved by a tailored time-dependent shortest path algorithm. To improve the performance of ADMM approach, two enhancement strategies are also designed to accelerate convergence. A set of real-life instances based on a rail transit line in Chengdu, China, is used to verify the effectiveness of the proposed model and algorithm. Computational results show that the ADMM-based approach with enhancements significantly outperforms a conventional Lagrangian Relaxation-based approach, yielding improved convergence and significantly smaller optimality gaps. Finally, on a set of real-life instances, the proposed ADMM-based approach with enhancements obtains an optimality gap of, on average, 4.2%. This is substantially better than Lagrangian Relaxation, which provides optimality gaps of, on average, 34.73%.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part C Home Page:

http://www.sciencedirect.com/science/journal/0968090X

Recommended Citation

Feng, T., Lusby, R.M., Zhang, Y., Peng, Q., Shang, P., & Tao, S. (2023). An ADMM-based dual decomposition mechanism for integrating crew scheduling and rostering in an urban rail transit line. Transportation Research Part C: Emerging Technologies, Vol. 149, 104081.