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

Tao Feng, Richard M. Lusby, Yongxiang Zhang*, Siyu Tao, Bojian Zhang, Qiyuan Peng

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

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.

Original languageEnglish
Article number102941
JournalTransportation Research Part B: Methodological
Volume183
ISSN0191-2615
DOIs
Publication statusPublished - 2024

Keywords

  • Branch-and-price algorithm
  • Crew scheduling and rostering problems
  • Integrated optimization
  • Urban rail transit

Fingerprint

Dive into the research topics of 'A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems'. Together they form a unique fingerprint.

Cite this