基于改进蚁群算法的铁路乘务交路计划的编制  

Railway crew routing plan based on improved ant colony algorithm

作　　者：王东先 孟学雷[1] 乔俊 汤霖 焦志臻 WANG Dongxian;MENG Xuelei;QIAO Jun;TANG Lin;JIAO Zhizhen(School of Traffic and Transportation,Lanzhou Jiaotong Unirersity,Lanzhou Gansu 730070,China;China Railway Lanzhou Group Company Limited,Wuwei South Station,Wuwei Gansu 733000,China)

机构地区：[1]兰州交通大学交通运输学院,兰州730070 [2]中国铁路兰州局集团有限公司武威南车务段,甘肃武威733000

出　　处：《计算机应用》2019年第9期2749-2756,共8页journal of Computer Applications

基　　金：国家重点研发项目(2016YFB1200100);国家自然科学基金资助项目(71861022,61563028)~~

摘　　要：针对提高铁路乘务交路计划编制质量和效率的问题,将乘务交路计划编制问题抽象为单基地、均衡行驶路程的多旅行商问题(MTSP),引入均衡因子,建立了以乘务交路用时少和子乘务交路间任务均衡为目标的数学模型。针对该模型提出了一种双重策略蚁群优化算法,该算法首先构建满足时空约束的解空间,分别对乘务区段节点和接续路径设置信息素浓度,然后采用双重策略状态的转移概率,使蚂蚁遍历所有乘务区段,最终找到符合乘务约束规则的子乘务交路。最后运用广深线城际铁路数据对设计的模型及算法进行检验,经与遗传算法的实验结果对比分析表明:在相同的模型条件下,运用双重策略蚁群优化算法编制的乘务交路计划乘务交路个数减少了约21.74%、乘务交路总时长降低了约5.76%、交路超劳率为0。运用所设计的模型和算法编制乘务交路计划能够减少乘务计划交路时长,均衡工作量,避免产生超劳交路。In order to improve the quality and efficiency of railway crew routing plan, the problem of crew routing plan was abstracted as a Multi-Traveling Salesman Problem(MTSP) with single base and balanced travel distance, and a equilibrium factor was introduced to establish a mathematical model aiming at less crew routing time and balanced tasks between sub-crew routings. A dual-strategy ant colony optimization algorithm was proposed for this model. Firstly, a solution space satisfying the space-time constraints was constructed and pheromone concentration was set for the node of the crew section and the continuation path respectively, then the transitional probability of the dual-strategy state was adopted to make the ant traverse all of the crew segments, and finally the sub-crew routings that meet the crew constraint rules were found. The designed model and algorithm were tested by the data of the intercity railway from Guangzhou to Shenzhen. The comparison with the experimental results of genetic algorithm shows that under the same model conditions, the number of crew routing in the crew routing plan generated by double-strategy ant colony optimization algorithm is reduced by about 21.74%, the total length of crew routing is decreased by about 5.76%, and the routing overload rate is 0. Using the designed model and algorithm to generate the crew routing plan can reduce the crew routing time of crew plan, balance the workload and avoid overload routing.

关 键 词：铁路 乘务交路计划 均衡因子 多旅行商问题 双重策略蚁群算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]