基于多旅行商问题建模的地铁乘务排班计划优化

doi:10.16097/j.cnki.1009-6744.2025.02.024

交通运输系统工程与信息 ›› 2025, Vol. 25 ›› Issue (2): 261-272.DOI: 10.16097/j.cnki.1009-6744.2025.02.024

基于多旅行商问题建模的地铁乘务排班计划优化

薛锋^1a,1b,1c，肖恩²，杨颖^1a，王金成^1a，罗建^*3

1. 西南交通大学，a.交通运输与物流学院，b.综合交通大数据应用技术国家工程实验室， c. 综合交通运输智能化国家地方联合工程实验室，成都611756；2.中铁第四勘察设计院集团有限公司，武汉430063；3. 西华大学，汽车与交通学院，成都610039

收稿日期:2024-10-27 修回日期:2025-01-15 接受日期:2025-02-10 出版日期:2025-04-25 发布日期:2025-04-20
作者简介:薛锋(1981—)，男，山东邹城人，副教授，博士。
基金资助:
国家重点研发计划项目 (2017YFB1200702)；四川省重点研发计划项目(2024YFHZ0021)。

Optimization of Metro Crew Scheduling Plans Based on Traveling Salesman Problem Modeling

XUE Feng^1a,1b,1c,XIAO En²,YANG Ying^1a,WANG Jincheng^1a,LUO Jian^*3

1a. School of Transportation and Logistics, 1b. National Engineering Laboratory of Integrated Transportation Big Data Application Technology, 1c. National United Engineering Laboratory of Integrated and Intelligent Transportation, Southwest Jiaotong University, Chengdu 611756, China; 2. China Railway Siyuan Survey and Design Group Co Ltd, Wuhan 430063, China; 3. School ofAutomobile and Transportation, Xihua University, Chengdu 610039, China

Received:2024-10-27 Revised:2025-01-15 Accepted:2025-02-10 Online:2025-04-25 Published:2025-04-20
Supported by:
National Key Research and Development Program of China (2017YFB1200702)；Key Research and Development Program of Sichuan Province(2024YFHZ0021)。

摘要/Abstract

摘要： 针对地铁乘务排班计划问题，本文借鉴多旅行商问题的模型特点进行建模，用排班问题中的乘务片段表示旅行商问题中的城市，乘务片段的接续时间表示旅行商问题中城市间的距离，综合考虑各班次最长在班时间、连续值乘时间、间休时间和就餐时间等约束，以乘务片段接续时间最短和乘务人员工作时间方差最小为优化目标，建立非线性0-1整数规划模型。基于多旅行商问题的求解思路，设计遗传模拟退火混合算法求解模型。最后，以成都地铁5号线为例验证算法，并与多种优化算法编制方案进行对比分析。实例分析结果显示，相比于ADMM(交替方向乘子法)算法和G-SPFA(基于贪婪思想的最短路)算法，本文优化后的排班方案在乘务任务数量优化率分别为17.9%和23.1%，接续时间方面的优化率分别为15.8%和12.1%，能够有效降低企业的人力成本，提高司乘员的值乘效率，验证了模型的有效性。

关键词: 城市交通, 多旅行商问题, 遗传模拟退火算法, 乘务排班计划

Abstract: This paper addresses the scheduling problem for subway crew by modeling it based on the characteristics of the multiple traveling salesmen problem. Specifically, crew segments in the scheduling problem are analogous to cities in the multiple traveling salesmen problem, and the succession time between crew segments represent the distances between cities. Constraints such as the maximum working time per shift, continuous duty time, interval time, and meal time are considered. A nonlinear 0-1 integer planning model is developed with the optimization objectives of shortest and minimum variance of crew working time. A genetic simulated annealing hybrid algorithm is designed to solve the model. The algorithm is validated through the case study for Chengdu Metro Line 5. The results show that compared with the Alternating Direction Method of Multipliers(ADMM) algorithm and Generalized Shortest Path Faster Algorithm(G-SPFA), the proposed method has optimization rates of 17.9% and 23.1% in the number of passenger tasks, and 15.8% and 12.1% in the succession time, which can effectively reduce the enterprise's manpower cost and improve the efficiency of the driver and passenger on duty.

Key words: urban traffic, multiple traveling salesman problem, genetic simulated annealing algorithm, crew scheduling

中图分类号:

U293.5

薛锋, 肖恩, 杨颖, 金成, 罗建. 基于多旅行商问题建模的地铁乘务排班计划优化[J]. 交通运输系统工程与信息, 2025, 25(2): 261-272.

XUE Feng, XIAO En, YANG Ying, WANG Jincheng, LUO Jian. Optimization of Metro Crew Scheduling Plans Based on Traveling Salesman Problem Modeling[J]. Journal of Transportation Systems Engineering and Information Technology, 2025, 25(2): 261-272.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/10.16097/j.cnki.1009-6744.2025.02.024

http://www.tseit.org.cn/CN/Y2025/V25/I2/261

参考文献

[1]丰富,陈绍宽,杜鹏.考虑时间均衡度的城市轨道交通乘务排班计划优化方法[J].交通运输系统工程与信息, 2014, 14(6): 164-170. [FENG F, CHEN S K, DU P. Time equitability-based crew scheduling optimization for urban rail transit[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(6): 164-170.]

[2] 杨帆,陈绍宽,刘泽远,等.面向列车可变编组的地铁乘务排班计划优化研究[J].铁道运输与经济,2024,46 (7): 159-167. [YANG F, CHEN S K, LIU Z Y, et al. Optimization of metro crew scheduling plan based on variable train formation[J]. Railway Transport and Economy, 2024, 46(7): 159-167.]

[3]金华,陈绍宽,王志美,等.基于地铁乘务资源共享的排班计划优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 126-132. [JIN H, CHEN S K, WANG Z M, 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.]

[4] 许仲豪,杜鹏.基于列生成的城市轨道交通乘务计划优化编制方法研究[J].铁道学报,2019, 41(3): 25-32. [XU Z H, DU P. A column generation based crew scheduling optimization method for urban rail transit[J]. Journal of the China Railway Society, 2019, 41(3): 25 32.]

[5] XUE F, ZHANG X, HU P, et al. Metro crew planning with heterogeneous duty paths and period-cycle pattern considerations[J]. Computers & Industrial Engineering, 2023, 182: 10935.

[6] 薛锋,梁鹏,李海,等.地铁乘务排班计划优化的最短路快速算法[J]. 铁道科学与工程学报, 2022, 19(9): 2532-2540. [XUE F, LIANG P, LI H, et al. Optimization of metro crew scheduling based on shortest path faster algorithm[J]. Journal of Railway Science and Engineering, 2022, 19(9): 2532-2540.]

[7] ZHOU J, XU X M, LONG J C, et al. Integrated optimization approach to metro crew scheduling and rostering[J]. Transportation Research Part C: Emerging Technologies, 2021, 123: 102975-102975.

[8] 苏铭,刘兰芬,杨信丰,等.基于TSP问题思想的城市轨道交通乘务排班计划研究[J].铁道运输与经济, 2022, 44(2): 131-138. [SU M, LIU L F, YANG X F, et al. Research on TSP-based crew scheduling plan for urban rail transit[J]. Railway Transport and Economy, 2022, 44(2): 131-138.]

[9] 侯彦娥,孔云峰,朱艳芳,等.公交司机排班问题的混合元启发算法研究[J]. 交通运输系统工程与信息, 2018, 18(1): 133-138. [HOU Y E, KONG Y F, ZHU Y F, et al. A hybrid metaheuristic algorithm for the transit bus and driver scheduling problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(1): 133-138.]

[10] 刘昊翔, 吴啊峰,龙建成,等.基于列生成启发式的单线电动公交车与司机整合调度优化[J].交通运输系统工程与信息,2021,21(4): 211-220. [LIU H X, WU A F, LONG J C, et al. Column generation-based heuristic approach for electric bus and driver scheduling on single bus lines[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(4): 211-220.]

[11] 潘寒川, 戚博洋,胡华,等.考虑司机偏好的城市轨道交通混合乘务轮转模型[J].交通运输系统工程与信息, 2023, 23(5): 258-267. [PAN H C, QI B Y, HU H, 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(5): 258-267.]

[12] 陈绍宽, 马卓然,彭小波,等.基于工作强度均衡的地铁乘务轮班计划优化模型[J].交通运输系统工程与信息, 2018, 18(6): 81-87. [CHEN S K, MA Z R, PENG X B, et al. Workload equitability-based optimum modeling for metro crew rostering[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(6): 81-87.]

[13] 石俊刚, 杨静,周峰,等.基于任务均衡的城市轨道交通乘务任务轮转模型及算法[J].铁道学报,2017,39 (9): 17-24. [SHI J G, YANG J, ZHOU F, 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.]

[14] JIN H, CHEN S K, RAN X C, et al. Column generatio based optimum crew scheduling incorporating network representation for urban rail transit systems[J]. Computers & Industrial Engineering, 2022, 169: 000 000.

[15] 刘葛辉, 金华,彭其渊,等.乘务资源共享下的城市轨道交通轮班计划优化[J].西南交通大学学报, (2024 01-12) [2024-10-20]. https://kns.cnki.net/KCMS/detail/ detail.aspx? dbcode = CJFD & dbname = CCJDLAST2 & filename=XNJT20240110001. [LIU G H, JIN H, PENG Q Y, et al. Crew rostering schedule optimization considering resource sharing for urban rail transit systems[J]. Journal of Southwest Jiaotong University, (2024-01-12) [2024-10-20]. https://kns.cnki.net/KCMS/ detail/ detail.aspx? dbcode = CJFD & dbname = CCJDLAST2 & filename=XNJT20240110001 .

[16] 黄志远,周峰,张在龙.基于可预知事件的城市轨道交通乘务轮转计划优化调整[J].交通运输系统工程与信息,2017, 17(4): 111-117. [HUANG Z Y, ZHOU F, ZHANG Z L. Optimizing adjustment of urban rail transit crew rostering plan based on predictable events[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(4): 111-117.]

[17] ZHOU J, XU X M, LONG J C, et al. Metro crew planning with day-off pattern, duty type, and rostering scheme considerations[J]. Transportation Research Part C: Emerging Technologies, 2022, 143: 10.

[18] FENG T, LUSBY R M, ZHANG Y X, 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.

[19] 梁鹏.基于网络图模型的乘务排班计划编制优化研究[D]. 成都: 西南交通大学,2023. [LIANG P. Research of crew scheduling optimization based on network diagram model[D]. Chengdu: Southwest Jiaotong University, 2023.]

[20] 陈科胜,鲜思东,郭鹏.求解旅行商问题的自适应升温模拟退火算法[J].控制理论与应用,2021,38(2): 245 254. [CHEN K S, XIAN S D, GUO P. Adaptive temperature rising simulated annealing algorithm for traveling salesman problem[J]. Control Theory & Applications, 2021, 38(2): 245-254.]

基于多旅行商问题建模的地铁乘务排班计划优化

Optimization of Metro Crew Scheduling Plans Based on Traveling Salesman Problem Modeling

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	晋泽倩, 俞诚成, 叶昕. 混合效用和后悔规则下的洪涝交通疏散决策行为研究[J]. 交通运输系统工程与信息, 2025, 25(2): 16-25.
[2]	周雨阳, 赵聪颖, 李京昆, 陈艳艳, 柳堤, 王书灵. 多类城市职住及通勤状态对出行方式选择影响比较[J]. 交通运输系统工程与信息, 2025, 25(2): 26-35.
[3]	彭其渊, 刘思源, 江山, 冯涛, 陈垚, 张永祥. 贯通运营下市域铁路与地铁列车开行方案协同优化[J]. 交通运输系统工程与信息, 2025, 25(2): 36-47.
[4]	蒋阳升, 叶肖甫, 徐尉耀, 刘洪汛, 胡路. 考虑转运与拼车的共享自动驾驶电动汽车动态运营[J]. 交通运输系统工程与信息, 2025, 25(2): 58-68.
[5]	赵雪亭, 胡立伟, 周君. 城市交通拥塞风险场级联失效及韧性评估研究[J]. 交通运输系统工程与信息, 2025, 25(2): 146-156.
[6]	武慧荣, 王玉莹, 盛椿婷. 考虑动态需求的城市货运公交线路规划模型研究[J]. 交通运输系统工程与信息, 2025, 25(2): 214-226.
[7]	徐伟汉, 李欣, 王天奇. 基于生态驾驶的常规和需求响应公交混合调度方法[J]. 交通运输系统工程与信息, 2025, 25(2): 227-240.
[8]	李昊, 陈绍宽, 徐彬, 石梦彤, 肖迪, 陈梓琦. 考虑值乘能力差异的地铁跨线乘务轮班计划优化方法[J]. 交通运输系统工程与信息, 2025, 25(2): 253-260.
[9]	张鹏, 吴照杰, 孙超, 李文权. 路口混合放行下的干线红波带宽最小优化模型[J]. 交通运输系统工程与信息, 2025, 25(2): 293-303.
[10]	许奇, 秦贝宁, 任澎, 陈越, 赖瑾璇. 建成环境对公交接驳地铁客流的异质性影响[J]. 交通运输系统工程与信息, 2025, 25(2): 352-363.
[11]	姚明, 王宇航, 曹淑超, 马露涵. 手机分心条件下行人运动特性研究[J]. 交通运输系统工程与信息, 2025, 25(2): 364-372.
[12]	翁剑成, 周慧缘, 张梦媛, 于江波. 考虑城市与群体异质的新能源车激励策略有效性研究[J]. 交通运输系统工程与信息, 2025, 25(1): 2-14.
[13]	李熙莹, 卢美燕, 何兆成, 苏淑妍, 庞淑敏. 基于车辆动态行为特征的交通状态识别研究[J]. 交通运输系统工程与信息, 2025, 25(1): 44-55.
[14]	王连震, 马志飞, 程国柱, 郑夫水. 城市道路智能网联汽车专用车道设置研究[J]. 交通运输系统工程与信息, 2025, 25(1): 56-66.
[15]	左忠义, 刘泽宇, 杨广川. 基于引力影响模型的轨道交通网络关键节点识别研究[J]. 交通运输系统工程与信息, 2025, 25(1): 102-112.