TY - JOUR
T1 - A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems
AU - Feng, Tao
AU - Lusby, Richard M.
AU - Zhang, Yongxiang
AU - Tao, Siyu
AU - Zhang, Bojian
AU - Peng, Qiyuan
N1 - Publisher Copyright:
© 2024 Elsevier Ltd
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
KW - Branch-and-price algorithm
KW - Crew scheduling and rostering problems
KW - Integrated optimization
KW - Urban rail transit
U2 - 10.1016/j.trb.2024.102941
DO - 10.1016/j.trb.2024.102941
M3 - Journal article
AN - SCOPUS:85189689221
SN - 0191-2615
VL - 183
JO - Transportation Research Part B: Methodological
JF - Transportation Research Part B: Methodological
M1 - 102941
ER -