Crew Rostering Schedule Optimization for Urban Rail Transit Through Resource Sharing
-
摘要:
在城市轨道交通网络化运营条件下,实现乘务资源共享对优化资源配置、降低运营成本、提高网络运输效率具有重要意义. 首先,针对城市轨道交通系统既有固定班制轮班模式,将多线乘务资源共享引入乘务轮班计划编制,在传统单一线路轮班基础上考虑乘务员的跨线值乘和出退勤偏好需求,建立面向线网乘务轮班优化模型以实现区域线网乘务计划的协同优化;其次,根据乘务员对出退勤地点的偏好进行分组,在各组内进行独立的轮班优化,均衡所有乘务员轮班计划工作量;然后,基于班次工作时间、班次间衔接时间和早晚时段工作时间,提出定量化的“辛苦”指标衡量不同班次的工作负荷;最后,根据固定班制和乘务资源共享的特点设计改进的蜂群算法,通过改进初始解生成和迭代搜索机制以完成模型的高效求解。研究表明:引入乘务资源共享可促进乘务员工作量的均衡性,同时满足乘务员对出退勤地点的偏好需求,在既有城市轨道交通乘务轮班模式下提高乘务计划效率和乘务员满意度.
Abstract:Given the context of network-level operation conditions of urban rail transit, crew resource sharing is significant for resource allocation optimization, operation cost reduction, and transport efficiency improvement. Firstly, targeted at existing fixed rostering patterns in urban rail transit systems, crew resource sharing among various lines was applied to crew rostering schedules. By considering cross-line duty and attendance and departure preferences of the crew based on traditional single line rostering, a crew rostering optimization model was proposed to achieve coordinated optimization of crew schedules for regional line networks. Secondly, the crew was grouped according to preferences for attendance and departure locations, and crew rostering in the groups was optimized separately, so as to balance the workload for crew rostering schedules. A quantified index was brought up to evaluate the workload of different crew shifts according to the shift working time, connecting time between shifts, and working time in morning and evening hours. Finally, through an improved swarm algorithm based on the characteristics of fixed crew rostering patterns and crew resource sharing, the model was solved efficiently by improving initial solution generation and iterative search methods. The results show that crew resource sharing can improve the balance of the crew workload, accommodate the crew preferences for attendance and departure locations, and enhance crew schedule efficiency and crew satisfaction under the existing crew rostering patterns of urban rail transit.
-
Key words:
- urban rail transit /
- crew rostering schedule /
- fixed rostering pattern /
- resource sharing /
- balance
-
表 1 四班三运转下4个乘务组的轮班计划
Table 1. Crew rostering schedule for four crew groups regarding four-team and three-shift patterns
乘务组 第 1 天 第 2 天 第 3 天 第 4 天 第 5 天 第 6 天 … 1 E M R D E M … 2 M R D E M R 3 R D E M R D 4 D E M R D E 表 2 符号定义
Table 2. Symbol definition
符号 含义 xj,i 决策变量,当且仅当班次 j 位于班次循环中第 i 个位置时,取值为 1 H 优化目标,所有轮班单位“辛苦”程度的均衡性 i 班次循环中的位置序号,i∈I,I 为班次位置集合 j 班次序号,j∈J,J 为班次集合 ts, j、te, j 班次 j 的开始和结束时间 td, j、tde, j、ti, j 班次 j 的驾驶时间、特殊时段附加值、非驾驶工作时间 JM, JE 早、晚班的班次集合 IE 班次循环中应分配晚班的位置集合 Tmins 晚班和早班的最小夜间休息(接续)时间 pi,k 0-1 变量,第 i 个位置的班次类型为 k 时,取值为 1 lk, j 0-1 变量,班次 j 属于班次类型 k 时,取值为1 t∗ 轮班单位长度,d r 轮班单位序号,r∈R,R 为轮班单位集合 Hr 轮班单位 r 的“辛苦”程度 h1,r、h2,r 轮班单位 r 由班次直接产生和接续产生的“辛苦”程度 qi,r 0-1 变量,轮班单位 r 包含位置 i 时,取值为 1 ir,m 轮班单位 r 的第 m 个班次(m=1,2,⋯,t)在班次循环中的位置 Tt,i,i* 班次循环中第 i 和第 i* 个位置对应班次类型之间的接续时间阈值 v1、v2、v3、v4 驾驶时间、特殊时段附加值、非驾驶工作时间、班次接续时间转化为“辛苦”程度的折算比例 表 3 3个案例场景的参数
Table 3. Parameters of three scenarios in case studies
场景 涉及线路 乘务区段数/个 连续值乘区段数/个 1 线路 1、3 1332 > 4567 2 线路 1、2 1689 > 6563 3 线路 1、2、3 1915 > 7144 表 4 考虑乘务员出退勤偏好的轮班输入构成
Table 4. Composition of crew rostering considering crew attendance and departure preferences
人 场景 班制 早班 白班 晚班 总乘务员数 排班数 备班数 排班数 备班数 排班数 备班数 1 四班三运转 41 5 41 5 41 5 368 六班五运转 56 6 28 3 56 6 372 2 四班三运转 43 5 43 5 43 5 384 六班五运转 68 8 34 4 68 8 456 3 四班三运转 54 6 54 6 54 6 480 六班五运转 78 8 39 4 78 8 516 表 5 不同场景和班制下乘务轮班计划优化结果
Table 5. Optimization results of crew rostering schedules in different scenarios and rostering patterns
场景 班制 A 组“辛苦”程度 B 组“辛苦”程度 总“辛苦”程度 计算时间/s 均值 标准差 均值 标准差 均值 标准差 1 四班三运转 883.6 42.2 854.3 46.2 869.0 46.5 8763 六班五运转 1311.6 58.1 1279.6 51.8 1295.6 57.3 11821 2 四班三运转 902.6 44.0 883.2 44.9 892.9 45.5 9138 六班五运转 1327.9 62.8 1269.1 61.0 1298.5 68.5 15033 3 四班三运转 902.1 48.6 869.8 46.5 886.0 50.2 11410 六班五运转 1310.6 69.7 1261.1 72.9 1285.8 75.4 16693 表 6 四班三运转下ABC与GA算法求解结果对比
Table 6. Comparison of ABC and GA results regarding four-team and three-shift patterns
场景 总“辛苦”程度 计算时间/s ABC GA ABC GA 1 868.95 ± 46.53 868.96 ± 49.76 8763 9053 2 892.91 ± 45.45 892.90 ± 52.82 9138 9385 3 885.97 ± 50.20 885.98 ± 53.18 11410 11639 注:u ± v中u为各个乘务组对应统计指标的均值,v为标准差. 表 7 场景3轮班计划对比
Table 7. Comparison of crew rostering schedules for scenario 3
班制 优化情形 乘务员数/人 日均额外通勤时间/h 工作效率/% 人均日工作时间/min “辛苦”程度均值/min “辛苦”程度标准差/min 四班三运转 分线优化 488 225.7 73.7 244.5 885.2 54.9 乘务共享 1 480↓ 0 73.9↑ 241.4↓ 886.0↑ 50.2↓ 乘务共享 2 468↓ 216.5↓ 74.9↑ 244.5↓ 890.3↑ 52.6↓ 六班五运转 分线优化 528 236.2 69.5 242.9 1287.3 89.0 乘务共享 1 504↓ 0 70.0↑ 246.6↑ 1285.8 ↓75.4↓ 乘务共享 2 504↓ 248.4↑ 70.7↑ 244.3↑ 1291.9 ↑70.9↓ 注:“↑”表示相较分线优化情形数值上增加;“↓”表示相较分线优化情形数值上减少. -
[1] 薛锋,梁鹏,李海,等. 地铁乘务排班计划优化的最短路快速算法[J]. 铁道科学与工程学报,2022,19(9): 2532-2540.XUE Feng, LIANG Peng, LI Hai, et al. Optimization of subway crew scheduling based on shortest path faster algorithm[J]. Journal of Railway Science and Engineering, 2022, 19(9): 2532-2540. [2] 潘寒川, 戚博洋, 胡华, 等. 考虑司机偏好的城市轨道交通混合乘务轮转模型[J]. 交通运输系统工程与信息,2023,23(1):258-267.PAN Hanchuan, QI Boyang, HU Hua, et al. Preference-oriented task-type-mixed crew rostering optimization model for urban railway transit[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1):258-267. [3] 杨子涵,刘葛辉,李明,等. 考虑资源共享的城市轨道交通架修基地选址优化模型[J]. 铁道科学与工程学报,2023,20(1): 74-83.YANG Zihan, LIU Gehui, LI Ming, et al. Optimum location selection of heavy repair depots for urban rail transit considering resource sharing[J]. Journal of Railway Science and Engineering, 2023, 20(1): 74-83. [4] 石俊刚,杨静,王凤丽. 多线乘务员共享条件下城市轨道交通乘务计划均衡编制探讨[J]. 铁道运输与经济,2016,38(3): 84-87.SHI Jungang, YANG Jing, WANG Fengli. Discussing on balanced crew scheduling of urban rail transit based on multi-line crews sharing[J]. Railway Transport and Economy, 2016, 38(3): 84-87. [5] 金华,陈绍宽,王志美,等. 基于地铁乘务资源共享的排班计划优化方法[J]. 交通运输系统工程与信息,2021,21(2): 126-132.JIN Hua, CHEN Shaokuan, WANG Zhimei, et al. Crew schedule optimization for urban rail transit with crew resources sharing[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(2): 126-132. [6] JIN H, CHEN S K, RAN X C, et al. Column generation-based optimum crew scheduling incorporating network representation for urban rail transit systems[J]. Computers & Industrial Engineering, 2022, 169: 108155.1-108155.12. [7] IBARRA-ROJAS O J, DELGADO F, GIESEN R, et al. Planning, operation, and control of bus transport systems: a literature review[J]. Transportation Research Part B: Methodological, 2015, 77: 38-75. [8] 褚飞跃,田志强,倪少权. 高速铁路单循环乘务排班计划编制模型与算法[J]. 铁道学报,2012,34(7): 1-9. doi: 10.3969/j.issn.1001-8360.2012.07.001CHU Feiyue, TIAN Zhiqiang, NI Shaoquan. Model and algorithm for formulation of the single cycle crew rostering plans of high-speed railways[J]. Journal of the China Railway Society, 2012, 34(7): 1-9. doi: 10.3969/j.issn.1001-8360.2012.07.001 [9] XIE L, SUHL L. Cyclic and non-cyclic crew rostering problems in public bus transit[J]. OR Spectrum, 2015, 37(1): 99-136. doi: 10.1007/s00291-014-0364-9 [10] QUESNEL F, DESAULNIERS G, SOUMIS F. Improving air crew rostering by considering crew preferences in the crew pairing problem[J]. Transportation Science, 2020, 54(1): 97-114. [11] MAENHOUT B, VANHOUCKE M. A hybrid scatter search heuristic for personalized crew rostering in the airline industry[J]. European Journal of Operational Research, 2010, 206(1): 155-167. [12] XIE L, MERSCHFORMANN M, KLIEWER N, et al. Metaheuristics approach for solving personalized crew rostering problem in public bus transit[J]. Journal of Heuristics, 2017, 23(5): 321-347. doi: 10.1007/s10732-017-9348-7 [13] 王骁. 高速铁路客运乘务排班优化研究[D]. 兰州:兰州交通大学,2021. [14] 金华,陈绍宽,冯旭杰,等. 考虑乘务员值乘需求的地铁乘务轮班优化方法[J]. 铁道学报,2023,45(7): 29-37. doi: 10.3969/j.issn.1001-8360.2023.07.004JIN Hua, CHEN Shaokuan, FENG Xujie, et al. A crew rostering optimization method for urban rail transit considering crew preference[J]. Journal of the China Railway Society, 2023, 45(7): 29-37. doi: 10.3969/j.issn.1001-8360.2023.07.004 [15] 张增勇. 城市轨道交通乘务计划编制方法研究[D]. 北京:北京交通大学,2014. [16] 罗红双. 网络化条件下城市轨道交通乘务计划编制方法研究[D]. 成都:西南交通大学,2019. [17] 金华,陈绍宽,刘爽,等. 基于固定班制的地铁乘务计划一体化优化方法[J]. 西南交通大学学报,2020,55(5): 955-962. doi: 10.3969/j.issn.0258-2724.20190952JIN Hua, CHEN Shaokuan, LIU Shuang, et al. Integrated optimum crew planning in fixed shift system for subways[J]. Journal of Southwest Jiaotong University, 2020, 55(5): 955-962. doi: 10.3969/j.issn.0258-2724.20190952 [18] LAI D S W, LEUNG J M Y, DULLAERT W, et al. A graph-based formulation for the shift rostering problem[J]. European Journal of Operational Research, 2020, 284(1): 285-300. doi: 10.1016/j.ejor.2019.12.019 [19] 石俊刚,杨静,周峰,等. 基于任务均衡的城市轨道交通乘务任务轮转模型及算法[J]. 铁道学报,2017,39(9): 17-24. doi: 10.3969/j.issn.1001-8360.2017.09.003SHI Jungang, YANG Jing, ZHOU Feng, et al. Crew rostering model and algorithm based on balanced workload in urban rail transit[J]. Journal of the China Railway Society, 2017, 39(9): 17-24. doi: 10.3969/j.issn.1001-8360.2017.09.003 [20] 汤希峰,何杰,张浩. 考虑碳排放的两阶段选址-路径问题及其算法[J]. 西南交通大学学报,2023,58(5): 1110-1116,1125. doi: 10.3969/j.issn.0258-2724.20210773TANG Xifeng, HE Jie, ZHANG Hao. Two-echelon location routing problem considering carbon emissions and its algorithm[J]. Journal of the Southwest Jiaotong University, 2023, 58(5): 1110-1116,1125. doi: 10.3969/j.issn.0258-2724.20210773 [21] 李冰,任泽强,轩华. 考虑多编组站专场作业的铁路枢纽车流组织优化[J]. 西南交通大学学报,2023,58(3): 489-498,545. doi: 10.3969/j.issn.0258-2724.20210796LI Bing, REN Zeqiang, XUAN Hua. Optimization of wagon flow assignment with transship work for multiple marshaling stations at railroad terminals[J]. Journal of the Southwest Jiaotong University, 2023, 58(3): 489-498,545. doi: 10.3969/j.issn.0258-2724.20210796 -