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

    Highlights Propose a new IP model for integrating crew scheduling and rostering problems. Design an ADMM-based dual decomposition mechanism to decompose the original IP model. Quadratic penalty terms in ADMM are linearized by the properties of model structure. Solve each subproblem efficiently with a time-dependent shortest path algorithm. The proposed IP model and algorithm are verified through a set of real-life instances.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:
    Feng, Tao (author) / Lusby, Richard M. (author) / Zhang, Yongxiang (author) / Peng, Qiyuan (author) / Shang, Pan (author) / Tao, Siyu (author)


    Publication date :

    2023-02-24




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Lifestyle Rostering for Rail Transit Crew

    American Public Transportation Association | British Library Conference Proceedings | 2007


    A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems

    Feng, Tao / Lusby, Richard M. / Zhang, Yongxiang et al. | Elsevier | 2024


    A Genetic Algorithm for the mass transit crew rostering problem

    Martins, Leandro do C. / Silva, Gustavo P. | IEEE | 2016


    Integrated optimization approach to metro crew scheduling and rostering

    Zhou, Jue / Xu, Xiaoming / Long, Jiancheng et al. | Elsevier | 2021


    Crew Scheduling for Shanghai Urban Rail Transit from Modeling to Implementation

    Li, X. / Xu, R. / Beijing jiao tong da xue; Guo jia zi ran ke xue ji jin wei yuan hui (China); Wang Kuancheng jiao yu ji jin hui | British Library Conference Proceedings | 2006