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

来源：交通运输系统工程与信息杂志2025年第2期北京时间：

作者：薛锋, 肖恩, 杨颖, 金成, 罗建

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

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

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

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