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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Feng, Tao (Autor:in) / Lusby, Richard M. (Autor:in) / Zhang, Yongxiang (Autor:in) / Tao, Siyu (Autor:in) / Zhang, Bojian (Autor:in) / Peng, Qiyuan (Autor:in)


    Erscheinungsdatum :

    2024-03-30




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    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

    Freier Zugriff

    A Genetic Algorithm for the mass transit crew rostering problem

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