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

摘要

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