基于TSP问题思想的城市轨道交通乘务排班计划研究  

Research on TSP-based Crew Scheduling Plan for Urban Rail Transit

作　　者：苏铭 刘兰芬[1] 杨信丰[1] 焦正玉 SU Ming;LIU Lanfen;YANG Xinfeng;JIAO Zhengyu(School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou 730070,Gansu,China)

机构地区：[1]兰州交通大学交通运输学院,甘肃兰州730070

出　　处：《铁道运输与经济》2022年第2期131-138,共8页Railway Transport and Economy

基　　金：国家自然科学基金项目(71761024);甘肃省自然科学基金项目(21JR1RA236);甘肃省教育厅双一流重大科研项目(GSSYLXM-04)。

摘　　要：乘务排班计划作为城市轨道交通运输组织与规划中的重要一步,其编制合理性关系着列车开行方案、列车运行图以及车底运用计划能否高效实现。将TSP问题思想应用于城市轨道交通排班计划的核心步骤中,考虑乘务规则、时间标准、运营限制等影响因素,以乘务工作班内乘务作业段间接续时间最小为目标构建乘务排班计划优化模型。将乘务作业段转化为附带时空属性的节点,节点间接续关系转化为弧,从而将乘务工作班的生成转化为类TSP问题。为减少搜索解时的盲目性与匹配时的无效性增加选择节点的方式,设置虚拟点和双路径表来划分乘务工作班,并设计蚁群算法求解。以某地铁线路为实例进行分析,结果显示平均接续时间为70.97 min,平均工作时间为246.14 min,平均工作班时间为307.11 min,证明该模型与算法的有效性。Crew scheduling plan is an important step in the transport organization and planning of urban rail transit,and its preparation rationality is vital to the efficient implementation of the train operation plan,train timetable,and rolling stock assignment.The traveling salesman problem(TSP)was applied to the core steps of scheduling plan formulation for urban rail transit.The crew rules,time standards,operation restrictions,and other factors were considered,and an optimization model for crew scheduling plans was constructed to minimize the connection time between crew sections in the crew working classes.The crew sections were transformed into nodes with spatiotemporal attributes,and the connection relationships between the nodes were transformed into arcs.Therefore,the generation of crew working classes was transformed into a TSP-like problem.A method of selecting nodes was added to reduce the blindness of searching solutions and the inefficiency of matching.Virtual points and two-path tables were set to group crew working classes,and an ant colony algorithm was designed to solve the problem.The model and the algorithm were applied to a subway line for a case study.The results show that the average connection time is 70.97 min,the average working time is 246.14 min,and the average crew shift time is 307.11 min,which proves the effectiveness of the model and the algorithm.

关 键 词：城市轨道交通 乘务排班计划 TSP问题 蚁群算法 双路径表 

分 类 号：U121[交通运输工程]