Intelligent Transportation System

Integrated Optimization Method for Cross-Line Operations of Subway Crew Scheduling

  • LI Hao ,
  • CHEN Shaokuan ,
  • SHI Mengtong ,
  • CHEN Ziqi
Expand
  • MOT Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport/Integrated Transport Research Center of China,Beijing Jiaotong University,Beijing 100044,China
李昊(1997—),男,博士生,主要从事城市轨道交通乘务计划研究。E-mail: 22110273@bjtu.edu.cn

Received date: 2025-05-13

  Online published: 2025-09-23

Supported by

the Beijing Municipal Natural Science Foundation(L191023)

Abstract

This study addresses the collaborative optimization of crew scheduling and rostering for subway trains operating in a cross-line pattern. It investigates the impact of an integrated optimization approach, based on a cyclic roster system, on both the efficiency of crew plan formulation and the utilization rate of crew members. A spatio-temporal network is constructed based on the cyclic roster system to search for feasible crew duty segments and the sequence of shift connections within a roster cycle. A mathematical model is formulated with the dual objectives of minimizing the total number of crew shifts and minimizing idle time during duties. Constraints are established, including crew shift connection rules and shift feasibility requirements, to define permissible roster paths for crew members. These constraints ensure that the assigned duties within the roster cycle comply with the rules for connecting duty segments.A roster path search algorithm and an improved column generation algorithm are developed, considering factors such as sign-on/sign-off depots for shifts, shift types, roster cycle length, and the shift system design. These algorithms are employed to obtain optimal duty assignments within the roster cycle. Furthermore, a hybrid roster system is proposed, exploring the effects of mixing “four crews for three operational shifts” and “six crews for five operational shifts” systems on the crew schedule. The results show that, compared to the traditional separate “four crews for three shifts” and “six crews for five shifts” systems, the proposed hybrid system within the integrated optimization framework increases the average shift efficiency by 1.5 and 2.3 percentage points, respectively. It also reduces the number of deadhead segments by 12.18% and 24.45%, respectively. Compared to a sequential (two-stage) optimization approach, the integrated method improves average shift efficiency and crew utilization rate without increasing the number of shifts worked per crew member. Additionally, it reduces the total number of shifts required within the roster cycle and decreases the redundancy in covering duty segments. The integrated optimization approach with the hybrid roster system can adapt to flexibile roster cycles and the spatio-temporal distribution differences of duty segments across various lines. This adaptability is beneficial for ensuring balanced duty assignments for crew members and enhancing their overall utilization efficiency.

Cite this article

LI Hao , CHEN Shaokuan , SHI Mengtong , CHEN Ziqi . Integrated Optimization Method for Cross-Line Operations of Subway Crew Scheduling[J]. Journal of South China University of Technology(Natural Science), 2026 , 54(3) : 127 -134 . DOI: 10.12141/j.issn.1000-565X.250142

References

[1] 魏润斌, 贾顺平, 童瑞咏, 等 .一般树型线条件下的列车开行方案优化研究[J].华南理工大学学报(自然科学版)202250(11): 44-51, 81.
  WEI Runbin, JIA Shunping, TONG Ruiyong, et al . Optimization of train planning for general tree-type line[J].Journal of South China University of Technology(Natural Science Edition)202250(11):44-51,81.
[2] 闫菲,姚向明,赵鹏,等 .互通运营模式下轨道交通开行方案编制模型[J].铁道学报202345(2):13-21.
  YAN Fei, YAO Xiangming, ZHAO Peng, et al .Modelling train operation plan for urban rail transit under interconnection operational mode[J].Journal of the China Railway Society202345(2): 13-21.
[3] HONG X, MENG L Y, DARIANO A, et al .Integrated optimization of capacitated train rescheduling and passenger reassignment under disruptions[J].Transportation Research Part C: Emerging Technologies2021125: 103025/1-19.
[4] SUN L, LU H, XU Y, et al .Fairness-oriented train service design for urban rail transit cross-line operation[J].Physica A: Statistical Mechanics and its Applications2022606: 128124/1-27.
[5] ZHANG C T, GAO Y, YANG L X, et al .Joint optimization of train scheduling and maintenance planning in a railway network: a heuristic algorithm using lagran-gian relaxation[J].Transportation Research Part B:Methodological2020134: 64-92.
[6] 曾庆文, 彭其渊 .考虑多编组的城轨列车跨线运营开行方案研究[J].铁道科学与工程学报202320(3): 878-889.
  ZENG Qingwen, PENG Qiyuan .Cross-line train plan in urban rail transit considering the multi-group train[J].Journal of Railway Science and Engineering202320(3): 878-889.
[7] 张翕然, 陈绍宽, 赵兴东, 等 .跨线运营模式下地铁列车运行图调整优化方法[J].交通运输系统工程与信息202323(4): 164-174.
  ZHANG Xi-ran, CHEN Shao-kuan, ZHAO Xing-dong,et al .A rescheduling optimization method for metro trains under cross-line operation[J].Journal of Transportation Systems Engineering and Information Techno-logy202323(4): 164-174.
[8] 陈垚, 柏赟, 毛保华,等 .跨线条件下城市轨道交通列车交路计划优化方法[J].铁道学报202446(8): 21-29.
  CHEN Yao, BAI Yun, MAO Baohua, et al .Optimization of train routing plan for interconnected line in urban rail transit[J].Journal of the China Railway So-ciety202446(8): 21-29.
[9] 黄俊生, 陈垚, 张安英, 等 .考虑互联互通的城市轨道交通网络列车开行方案优化[J].铁道科学与工程学报202320(5): 1587-1597.
  HUANG Junsheng, CHEN Yao, ZHANG Anying,et al .Optimization of urban rail network operation scheme considering interconnection[J].Journal of Railway Science and Engineering202320(5): 1587-1597.
[10] ZEIGHAMI V, SADDOUNE M, SOUMIS F .Alternating lagrangian decomposition for integrated airline crew scheduling problem[J].European Journal of Operational Research2020287(1): 211-224.
[11] ZHOU J, XU X, LONG J,et al .Metro crew planning with day-off pattern,duty type,and rostering scheme considerations[J].Transportation Research Part C:Emerging Technologies2022143:103832/1-26.
[12] ZHOU S, ZHAN Z, CHEN Z, et al .A multi-objective ant colony system algorithm for airline crew rostering problem with fairness and satisfaction[J].IEEE Transactions on Intelligent Transportation Systems202122(11): 6784-6798.
[13] FENG T, LUSBY R M, ZHANG Y, et al .An ADMM-based dual decomposition mechanism for integrating crew scheduling and rostering in an urban rail transit line[J].Transportation Research Part C:Emerging Technologies2023149: 104081/1-34.
[14] QUESNEL F, DESAULINIERS G, SOUMIS F .Improving air crew rostering by considering crew prefe-rences in the crew pairing problem[J].Transportation Science202054(1): 97-114.
[15] QUESNEL F, DESAULINIERS G, SOUMIS F .A branch-and-price heuristic for the crew pairing problem with language constraints[J].European Journal of Operational Research2020283(3):1040-1054.
[16] SHAFIPOUR O B, RASHIDI K A, SADJADI S J,et al .A fuzzy crew rostering model based on crew preferences and seniorities considering training courses: a robust optimization approach[J].Computational Intelligence and Neuroscience20222022:8415169/1-15.
Outlines

/