Railway crew rostering plan based on improved ant colony optimization algorithm

doi:10.11772/j.issn.1001-9081.2019061118

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (12): 3678-3684.DOI: 10.11772/j.issn.1001-9081.2019061118

• Frontier & interdisciplinary applications • Previous Articles Next Articles

Railway crew rostering plan based on improved ant colony optimization algorithm

WANG Dongxian¹, MENG Xuelei¹, HE Guoqiang¹, SUN Huiping¹, WANG Xidong²

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

Received:2019-06-27 Revised:2019-09-05 Online:2019-12-10 Published:2019-10-08
Contact: 孟学雷
Supported by:
This work is partially supported by the National Key Research and Development Program of China (2016YFB1200100), the National Natural Science Foundation of China (71861022, 61563028).

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

王东先¹, 孟学雷¹, 何国强¹, 孙慧萍¹, 王喜栋²

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

作者简介:王东先(1992-),男,甘肃武威人,硕士研究生,主要研究方向:轨道交通运行管理与决策优化;孟学雷(1979-),男,山东泰安人,教授,博士,主要研究方向:轨道交通运行管理与决策优化;何国强(1990-),男,甘肃白银人,硕士研究生,主要研究方向:智能算法、仓储物流管理优化;孙慧萍(1993-),女,甘肃定西人,硕士研究生,主要研究方向:轨道交通运行管理与决策优化;王喜栋(1993-),男,甘肃临洮人,助理工程师,主要研究方向:铁路车流组织优化、货物运输组织。
基金资助:
国家重点研发计划项目（2016YFB1200100）；国家自然科学基金资助项目（71861022，61563028）。

Abstract

Abstract: In order to improve the quality and efficiency of railway crew rostering plan arrangement, the problem of crew rostering plan arrangement was abstracted as a Multi-Traveling Salesman Problem (MTSP) with single base and considering mid-way rest, a single-circulation crew rostering plan mathematical model aiming at the smallest rostering period and the most balanced distributed redundant connection time between crew routings was established, and a new amended heuristic ant colony optimization algorithm was proposed aiming at the model. Firstly, a solution space satisfying the spatial-temporal constraints was constructed and the pheromone concentration was set for the crew routing nodes and the continued paths respectively. Then, the amended heuristic information was adopted to make the ants start at the crew routing order and go through all the crew routings. Finally, the optimal crew rostering plan was selected from the different crew rostering schemes. The proposed model and algorithm were tested on the data of the intercity railway from Guangzhou to Shenzhen. The comparison results with the plan arranged by particle swarm optimization show that under the same model conditions, the crew rostering plan arranged by amended heuristic ant colony optimization algorithm has the average monthly man-hour reduced by 8.5%, the rostering period decreased by 9.4%, and the crew overwork rate of 0. The designed model and algorithm can compress the crew rostering cycle, reduce the crew cost, balance the workload, and avoid the overwork of crew.

Key words: railway, crew rostering plan, Multi-Traveling Salesman Problem (MTSP), redundant time, amended heuristic ant colony optimization algorithm

摘要： 为了提升铁路乘务排班计划编制的质量和效率，将乘务排班计划编制问题抽象为单基地、考虑中途休息的多旅行商问题（MTSP），建立以排班周期最小、乘务交路间冗余接续时间分布最均衡为优化目标的单一循环乘务排班计划数学模型，并针对该模型提出了一种启发式修正蚁群算法。首先，构建满足时空约束的解空间，分别对乘务交路节点和接续路径设置信息素浓度；然后，确定基于修正的启发式信息，规定蚂蚁按乘务交路顺序依次出发，使蚂蚁遍历所有乘务交路；最后，从不同的乘务排班方案中选择最优的排班计划。以广深城际铁路为例对所提模型及算法进行验证，并与粒子群算法进行对比。实验结果表明：在相同的模型条件下，采用启发式修正蚁群算法编制的乘务排班计划平均月工时降低了8.5%，排班周期降低了9.4%，乘务人员超劳率为0。所提模型和算法能够压缩乘务排班周期，降低乘务成本，均衡工作量，避免乘务人员超劳。

关键词: 铁路, 乘务排班计划, 多旅行商问题, 冗余时间, 启发式修正蚁群算法

CLC Number:

WANG Dongxian, MENG Xuelei, HE Guoqiang, SUN Huiping, WANG Xidong. Railway crew rostering plan based on improved ant colony optimization algorithm[J]. Journal of Computer Applications, 2019, 39(12): 3678-3684.

王东先, 孟学雷, 何国强, 孙慧萍, 王喜栋. 基于改进蚁群算法的铁路乘务排班计划编制[J]. 计算机应用, 2019, 39(12): 3678-3684.

References

[1] MERCIER A, SOUMIS F. An integrated aircraft routing, crew scheduling and flight retiming model[J]. Computers and Operations Research, 2007, 34(8):2251-2265.
[2] SOUAI N, TEGHEM J. Genetic algorithm based approach for the integrated airline crew-pairing and rostering problem[J]. European Journal of Operational Research, 2009, 199(3):674-683.
[3] NISHI T, SUGIYAMA T, INUIGUCHI M. Two-level decomposition algorithm for crew rostering problems with fair working condition[J]. European Journal of Operational Research, 2014, 237(2):465-473.
[4] VEELENTURF L P, POTTHOFF D, HUISMAN D, et al. A quasi-robust optimization approach for resource rescheduling[J]. Transportation Science, 2016, 50(1):204-215.
[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].计算机应用,2019,39(9):2749-2756.(WANG D X, MENG X L, QIAO J, et al. Research on railway crew routing plan based on improved ant colony algorithm[J]. Journal of Computer Applications, 2019, 39(9):2749-2756.)
[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].铁道运输与经济,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.)
[10] 褚飞跃,田志强,倪少权.高速铁路单循环乘务排班计划编制模型与算法[J].铁道学报,2012,34(7):1-9.(CHU F Y, TIAN Z Q, NI S Q. Model and algorithm for formulation of the single cycle crew rostering plans of high-speed railways[J]. Journal of the China Railway Society, 2012, 34(7):1-9.)
[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):23-29.(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):23-29.)
[14] 李雯,贾富强,杨睿.基于交路单元的高速铁路乘务交路编制模型与算法[J].交通运输研究,2018,4(4):48-53.(LI W, JIA F Q, YANG R. A model and algorithm of high-speed railway crew scheduling based on routing unit[J]. Transport Research, 2018, 4(4):48-53.)
[15] 符卓,袁雪莹.高速动车组乘务交路辅助编制系统研究[J].铁道运输与经济,2019(8):18-21.(FU Z, YUAN X Y. A research on high-speed EMU crew schedule auxiliary preparation system[J]. Railway Transport and Economy, 2019(8):18-21.)
[16] 杨国元,史天运,张秋亮.铁路客运乘务排班计划编制模型及算法[J].交通运输系统工程与信息,2016,16(4):159-164.(YANG G Y, SHI T Y, ZHANG Q L. Model and algorithm for railway passenger crew rostering plan[J]. Journal of Transportation Systems Engineering and Information Technology, 2016,16(4):159-164.)
[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 rostering plan based on improved ant colony optimization algorithm

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	ZENG Xiangyin, ZHENG Bochuan, LIU Dan. Detection of left and right railway tracks based on deep convolutional neural network and clustering [J]. Journal of Computer Applications, 2021, 41(8): 2324-2329.
[2]	HAO Pengfei, CHI Rui, QU Zhijian, TU Hongbin, CHI Xuexin, ZHANG Diyou. Improved grey wolf optimizer for location selection problem of railway logistics distribution center [J]. Journal of Computer Applications, 2021, 41(10): 2905-2911.
[3]	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.
[4]	XI Haozhe, WANG Ruifeng. Adaptive beamforming scheme of massive MIMO based on antenna grouping in high-speed railway environment [J]. Journal of Computer Applications, 2019, 39(3): 839-844.
[5]	YANG Fei, LUO Jianqiao, LI Bailin. Railway fastener classification model based on sLDA combined with global and local constraints [J]. Journal of Computer Applications, 2019, 39(3): 888-893.
[6]	GAO Jingang, LIU Zhiyong, ZHANG Shuang, HOU Daishuang, LIU Xiaofeng. Application of binocular stereo vision technology in key dimension detection of CRH body [J]. Journal of Computer Applications, 2018, 38(9): 2673-2677.
[7]	ZUO Liming, HU Kaiyu, ZHANG Mengli, CHEN Lanlan. Data transmission protocol based on short signature scheme for railway bridge monitoring [J]. Journal of Computer Applications, 2018, 38(8): 2261-2266.
[8]	DU Xueling, MENG Xuelei, YANG Bei, TANG Lin. Emergency resource assignment for requirements of multiple disaster sites in view of fairness [J]. Journal of Computer Applications, 2018, 38(7): 2089-2094.
[9]	XIA Haonan, DAI Shenghua. Security encryption of radio block center based on colored Petri net [J]. Journal of Computer Applications, 2018, 38(12): 3476-3480.
[10]	LUO Jianqiao, LIU Jiajia, LI Bailin, DI Shilei. Latent Dirichlet allocation model integrated with texture structure for railway fastener detection [J]. Journal of Computer Applications, 2016, 36(2): 574-579.
[11]	LI Xiaowen, YUAN Xianghui, ZHOU Chunxiang. Optimal line-shape parameter estimation algorithm of orbit plane based on inertial angle measurement [J]. Journal of Computer Applications, 2016, 36(12): 3499-3504.
[12]	PU Song, LYU Hongxia. Dynamic evaluation for train line planning in high speedrailway based on improved data envelopment analysis [J]. Journal of Computer Applications, 2015, 35(5): 1479-1482.
[13]	ZHU Haiyang, CUI Bingmou, HU Zhiyao. Comprehensive coordination optimization of train break-up and make-up scheme based on hard time windows at railway technical station [J]. Journal of Computer Applications, 2015, 35(3): 891-895.
[14]	YU Lizhen XU Zhongwei CHEN Zuxi ZHANG Shuqin. Formal verification of railway interlocking system based on ladder logic [J]. Journal of Computer Applications, 2013, 33(12): 3419-3422.
[15]	CUI Zhuanling LI Guoning LIN Sen. Hotbox level detection of railway vehicle using fuzzy neural networks [J]. Journal of Computer Applications, 2013, 33(09): 2566-2569.