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

doi:10.11772/j.issn.1001-9081.2019020368

计算机应用 ›› 2019, Vol. 39 ›› Issue (9): 2749-2756.DOI: 10.11772/j.issn.1001-9081.2019020368

• 应用前沿、交叉与综合 • 上一篇下一篇

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

王东先¹, 孟学雷¹, 乔俊¹, 汤霖¹, 焦志臻²

1. 兰州交通大学交通运输学院, 兰州 730070;
2. 中国铁路兰州局集团有限公司武威南车务段, 甘肃武威 733000

收稿日期:2019-03-11 修回日期:2019-04-27 出版日期:2019-09-10 发布日期:2019-05-21
通讯作者: 孟学雷
作者简介:王东先(1992-),男,甘肃武威人,硕士研究生,主要研究方向:轨道交通运行管理、决策优化;孟学雷(1979-),男,山东泰安人,教授,博士,主要研究方向:轨道交通运行管理、决策优化;乔俊(1993-),女,陕西周至人,硕士研究生,主要研究方向:轨道交通运行管理、决策优化;汤霖(1989-),男,甘肃武威人,硕士,主要研究方向:轨道交通运行管理、决策优化;焦志臻(1992-),男,甘肃兰州人,助理工程师,主要研究方向:铁路车流组织优化、货物运输组织。
基金资助:
国家重点研发项目（2016YFB1200100）；国家自然科学基金资助项目（71861022，61563028）。

Railway crew routing plan based on improved ant colony algorithm

WANG Dongxian¹, MENG Xuelei¹, QIAO Jun¹, TANG Lin¹, JIAO Zhizhen²

1. School of Traffic and Transportation, Lanzhou Jiaotong Unirersity, Lanzhou Gansu 730070, China;
2. China Railway Lanzhou Group Company Limited, Wuwei South Station, Wuwei Gansu 733000, China

Received:2019-03-11 Revised:2019-04-27 Online:2019-09-10 Published:2019-05-21
Supported by:
This work is partially supported by the National Key Research and Development Project of China (2016YFB1200100), the National Natural Science Foundation of China (71861022, 61563028).

摘要/Abstract

摘要：

针对提高铁路乘务交路计划编制质量和效率的问题，将乘务交路计划编制问题抽象为单基地、均衡行驶路程的多旅行商问题（MTSP），引入均衡因子，建立了以乘务交路用时少和子乘务交路间任务均衡为目标的数学模型。针对该模型提出了一种双重策略蚁群优化算法，该算法首先构建满足时空约束的解空间，分别对乘务区段节点和接续路径设置信息素浓度，然后采用双重策略状态的转移概率，使蚂蚁遍历所有乘务区段，最终找到符合乘务约束规则的子乘务交路。最后运用广深线城际铁路数据对设计的模型及算法进行检验，经与遗传算法的实验结果对比分析表明：在相同的模型条件下，运用双重策略蚁群优化算法编制的乘务交路计划乘务交路个数减少了约21.74%、乘务交路总时长降低了约5.76%、交路超劳率为0。运用所设计的模型和算法编制乘务交路计划能够减少乘务计划交路时长，均衡工作量，避免产生超劳交路。

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

Abstract:

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.

Key words: railway, crew routing plan, equilibrium factor, Multi-Traveling Salesman Problem (MTSP), dual-strategy Ant Colony Algorithm (ACA)

中图分类号:

TP301.6

王东先, 孟学雷, 乔俊, 汤霖, 焦志臻. 基于改进蚁群算法的铁路乘务交路计划的编制[J]. 计算机应用, 2019, 39(9): 2749-2756.

WANG Dongxian, MENG Xuelei, QIAO Jun, TANG Lin, JIAO Zhizhen. Railway crew routing plan based on improved ant colony algorithm[J]. Journal of Computer Applications, 2019, 39(9): 2749-2756.

参考文献

[1] BEASLEY J E, CAO B. A tree search algorithm for the crew scheduling problem[J]. European Journal of Operational Research, 1996, 94(3):517-526.
[2] CHU S C K. Generating, scheduling and rostering of shift crew-duties, applications at the Hong Kong International Airport[J]. European Journal of Operational Research, 2007, 177(3):1764-1778.
[3] DENNIS HUISMAN. A column generation approach for the rail crew re-scheduling problem[J]. European Journal of Operational Research, 2007, 180(1):163-173.
[4] GAMACHE M, HERTZ A, OUELLET J O. A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding[J]. Computers and Operations Research, 2007, 34(8):2384-2395.
[5] 陈海平.高速铁路乘务组织理论与优化研究[D].北京:北京交通大学,2013:42-61.(CHEN H P. Research on theory and optimization of crew organization of high-speed railway[D]. Beijing:Beijing Jiaotong University, 2013:42-61.)
[6] 赵鹏,胡安洲,杨浩.机车乘务人员运用计划的优化编制[J].铁道学报,1998,20(4):8-13.(ZHAO P, HU A Z, YANG H. Research on optimization of crew scheduling[J]. Journal of the China Railway Society, 1998, 20(4):8-13.)
[7] 阎永光,黄斌.广深线城际列车乘务组排班计划编制方法探讨[J].交通运输工程与信息学报,2010,8(1):25-29.(YAN Y G, HUANG B. Research on the crew schedule programming method of Guangzhou-Shenzhen intercity trains[J]. Journal of Transportation Engineering and Information, 2010, 8(1):25-29.)
[8] 程岩岩.我国铁路乘务调度计划编制方法的研究与设计[D].北京:北京交通大学,2007:21-30.(CHENG Y Y. Research and design of domestic railway crew scheduling method[D]. Beijing:Beijing Jiaotong University, 2007:21-30.)
[9] 王莹,刘军,苗建瑞.客运专线乘务交路计划编制的优化模型与算法[J].铁道学报,2009,31(1):15-19.(WANG Y, LIU J, MIAO J R. Modeling and solving the crew scheduling problem of passenger dedicated line[J]. Journal of the China Railway Society, 2009, 31(1):15-19.)
[10] 王媛媛,周成晨,倪少权.基于蚁群算法的客运专线乘务交路计划编制方法研究[J].铁路计算机应用,2009,18(7):11-14.(WANG Y Y, ZHOU C C, NI S Q. Study on algorithm of crew routing scheduling for passenger dedicated line based on ant colony optimization[J]. Railway Computer Application, 2009, 18(7):11-14.)
[11] 黄珊.机车乘务人员运用问题及其辅助编排系统研究[D].长沙:中南大学,2014:30-44.(HUANG S. Locomotive crew scheduling problem and scheduling assistant system[D]. Changsha:Central South University, 2014:30-44.)
[12] 田志强.高速铁路乘务计划编制优化理论与方法研究[D].成都:西南交通大学,2011:45-72.(TIAN Z Q. Study on theory and methods of crew planning problem of high-speed railway[D]. Chengdu:Southwest Jiaotong University, 2011:45-72.)
[13] 陈旭,李海鹰,王莹,等.放射状路网条件下动车组运用优化研究[J].铁道学报,2017,39(11):1-7.(CHEN X, LI H Y, WANG Y, et al. Research on optimization of EMU scheduling for radial HSR network[J]. Journal of the China Railway Society, 2017, 39(11):1-7.)
[14] 郭璞.铁路客运机车乘务交路编制问题研究[D].长沙:中南大学,2013:24-32.(GUO P. Railway passenger train crew scheduling problem[D]. Changsha:Central South University, 2013:24-32.)
[15] 银大伟.乘务计划编制系统的研究与设计[D].成都:西南交通大学,2008:30-41.(YIN D W. Research and design of crew scheduling system[D]. Chengdu:Southwest Jiaotong University, 2008:30-41.)
[16] 张哲铭,王莹,陈旭,等.高速铁路单一循环乘务值乘计划优化研究[J].铁道运输与经济,2018,40(1):21-27.(ZHANG Z M, WANG Y, CHEN X, et al. Research on single-circulation crew rostering plan optimization for high-speed railway[J]. Railway Transport and Economy, 2018, 40(1):21-27.)
[17] 马良,朱刚,宁爱兵.蚁群优化算法[M].北京:科学出版社,2008:57-73.(MA L, ZHU G, NING A B. Ant Colony Optimization Algorithm[M]. Beijing:Science Press, 2008:57-73.)
[18] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005:212-232.(DUAN H B. Ant Colony Algorithms:Theory and Applications[M]. Beijing:Science Press, 2005:212-232.)

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

Railway crew routing plan based on improved ant colony algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	郝芃斐, 池瑞, 屈志坚, 涂宏斌, 池学鑫, 张地友. 求解铁路物流配送中心选址问题的改进灰狼优化算法[J]. 计算机应用, 2021, 41(10): 2905-2911.
[2]	杨飞, 罗建桥, 李柏林. 结合全局和局部约束的sLDA铁路扣件分类模型[J]. 计算机应用, 2019, 39(3): 888-893.
[3]	席皓哲, 王瑞峰. 基于天线分组的高铁大规模多输入多输出自适应波束赋形方案[J]. 计算机应用, 2019, 39(3): 839-844.
[4]	王东先, 孟学雷, 何国强, 孙慧萍, 王喜栋. 基于改进蚁群算法的铁路乘务排班计划编制[J]. 计算机应用, 2019, 39(12): 3678-3684.
[5]	左黎明, 胡凯雨, 张梦丽, 陈兰兰. 铁路桥梁监测中基于短签名方案的数据传输协议[J]. 计算机应用, 2018, 38(8): 2261-2266.
[6]	杜雪灵, 孟学雷, 杨贝, 汤霖. 考虑公平性的面向多灾点需求应急资源调度[J]. 计算机应用, 2018, 38(7): 2089-2094.
[7]	夏浩男, 戴胜华. 基于着色Petri网的无线闭塞中心安全加密[J]. 计算机应用, 2018, 38(12): 3476-3480.
[8]	罗建桥, 刘甲甲, 李柏林, 狄仕磊. 融合纹理结构的潜在狄利克雷分布铁路扣件检测模型[J]. 计算机应用, 2016, 36(2): 574-579.
[9]	于丽贞徐中伟陈祖希张舒青. 基于梯形逻辑的联锁系统形式化验证方法[J]. 计算机应用, 2013, 33(12): 3419-3422.
[10]	崔转玲李国宁林森. 基于模糊神经网络的铁路车辆热轴等级判别模型[J]. 计算机应用, 2013, 33(09): 2566-2569.
[11]	罗强王倩刘方林范瑞娟. 基于SCA/SDO的高速铁路综合调度系统中间件设计[J]. 计算机应用, 2013, 33(06): 1654-1669.
[12]	雷斌陶海龙徐晓光. 基于改进粒子群优化算法的灰色神经网络的铁路货运量预测[J]. 计算机应用, 2012, 32(10): 2948-2951.
[13]	蒋新华朱铨邹复民. 高速铁路3G通信的覆盖与切换技术综述[J]. 计算机应用, 2012, 32(09): 2385-2390.
[14]	王喆. 基于组合遗传算法的铁路危险货物办理站点整合优化[J]. 计算机应用, 2010, 30(9): 2301-2304.
[15]	熊静喻钢徐中伟郦萌. 面向安全评估的高速铁路CTCS-2列控系统安全性测试环境[J]. 计算机应用, 2010, 30(8): 2181-2184.