Abstract Crew planning, involving how to best schedule crew members during a given period, is a significant problem for urban rail transit companies. This paper proposes a new integer linear programming (ILP) model that can simultaneously optimize urban rail crew scheduling and rostering problems. The proposed ILP model is a set partitioning-based model with only one type of important duty selection variable that connects the two-level problem and circumvents the drawbacks of conventional approaches that usually formulate the crew scheduling and rostering problems separately and couple these two problems through linking constraints. This study demonstrates that the structure of the underlying network used to model the problem enables the development of an effective, heuristic branch-and-price procedure. The study compares the proposed approach with two other decomposition methods, namely Lagrangian relaxation and alternating direction method of multipliers (ADMM), on problems of different sizes and shows that the method provides lower bounds that are on average 16.4% better than Lagrangian relaxation and 5.03% better than ADMM, respectively. Furthermore, the study shows that, with an average optimality gap of 3.28%, the proposed approach obtains high-quality integer solutions to the integrated problem.

    Highlights Propose a unified ILP model for integrating urban rail crew scheduling and rostering. Design a branch-and-price heuristic procedure for obtaining high-quality solutions. Exploiting the structure of the underlying network to accelerate solving the pricing subproblem. Comparing the lower bounds of column generation, Lagrangian relaxation, and ADMM. Verify the proposed models and algorithms through a set of real-life instances.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


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


    Publication date :

    2024-03-30




    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



    Integrated optimization approach to metro crew scheduling and rostering

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


    A Branch-and-Price-and-Cut Algorithm for the Integrated Scheduling and Rostering Problem of Bus Drivers

    Dung-Ying Lin / Chieh-Ju Juan / Ching-Chih Chang | DOAJ | 2020

    Free access

    A Genetic Algorithm for the mass transit crew rostering problem

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