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.
A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems
2024-03-30
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Lifestyle Rostering for Rail Transit Crew
British Library Conference Proceedings | 2007
|Integrated optimization approach to metro crew scheduling and rostering
Elsevier | 2021
|DOAJ | 2020
|