Journal of South China University of Technology(Natural Science) >
Integrated Optimization Method for Cross-Line Operations of Subway Crew Scheduling
Received date: 2025-05-13
Online published: 2025-09-23
Supported by
the Beijing Municipal Natural Science Foundation(L191023)
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.
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
| [1] | 魏润斌, 贾顺平, 童瑞咏, 等 .一般树型线条件下的列车开行方案优化研究[J].华南理工大学学报(自然科学版), 2022, 50(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),2022,50(11):44-51,81. | |
| [2] | 闫菲,姚向明,赵鹏,等 .互通运营模式下轨道交通开行方案编制模型[J].铁道学报,2023,45(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 Society, 2023, 45(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 Technologies,2021, 125: 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 Applications, 2022, 606: 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:Methodological, 2020, 134: 64-92. |
| [6] | 曾庆文, 彭其渊 .考虑多编组的城轨列车跨线运营开行方案研究[J].铁道科学与工程学报, 2023,20(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 Engineering,2023,20(3): 878-889. | |
| [7] | 张翕然, 陈绍宽, 赵兴东, 等 .跨线运营模式下地铁列车运行图调整优化方法[J].交通运输系统工程与信息, 2023, 23(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-logy, 2023, 23(4): 164-174. | |
| [8] | 陈垚, 柏赟, 毛保华,等 .跨线条件下城市轨道交通列车交路计划优化方法[J].铁道学报, 2024, 46(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-ciety, 2024, 46(8): 21-29. | |
| [9] | 黄俊生, 陈垚, 张安英, 等 .考虑互联互通的城市轨道交通网络列车开行方案优化[J].铁道科学与工程学报, 2023, 20(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 Engineering, 2023, 20(5): 1587-1597. | |
| [10] | ZEIGHAMI V, SADDOUNE M, SOUMIS F .Alternating lagrangian decomposition for integrated airline crew scheduling problem[J].European Journal of Operational Research, 2020, 287(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 Technologies,2022,143: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 Systems, 2021, 22(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 Technologies, 2023, 149: 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 Science, 2020, 54(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 Research, 2020,283(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 Neuroscience,2022,2022:8415169/1-15. |
/
| 〈 |
|
〉 |