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

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

作　　者：薛锋[1,2,3] 肖恩 杨颖 王金成 罗建 XUE Feng;XIAO En;YANG Ying;WANG Jincheng;LUO Jian(a.School of Transportation and Logistics,Southwest Jiaotong University,Chengdu 611756,China;National Engineering Laboratory of Integrated Transportation Big Data Application Technology,Southwest Jiaotong University,Chengdu 611756,China;National United Engineering Laboratory of Integrated and Intelligent Transportation,Southwest Jiaotong University,Chengdu 611756,China;China Railway Siyuan Survey and Design Group Co Ltd,Wuhan 430063,China;School of Automobile and Transportation,Xihua University,Chengdu 610039,China)

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

出　　处：《交通运输系统工程与信息》2025年第2期261-272,共12页Journal of Transportation Systems Engineering and Information Technology

基　　金：国家重点研发计划项目(2017YFB1200702);四川省重点研发计划项目(2024YFHZ0021)。

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

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

分 类 号：U293.5[交通运输工程—交通运输规划与管理]