Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (9): 2749-2756.

• Frontier & interdisciplinary applications •

### Railway crew routing plan based on improved ant colony algorithm

WANG Dongxian1, MENG Xuelei1, QIAO Jun1, TANG Lin1, JIAO Zhizhen2

1. 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).

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

1. 1. 兰州交通大学 交通运输学院, 兰州 730070;
2. 中国铁路兰州局集团有限公司 武威南车务段, 甘肃 武威 733000
• 通讯作者: 孟学雷
• 作者简介:王东先(1992-),男,甘肃武威人,硕士研究生,主要研究方向:轨道交通运行管理、决策优化;孟学雷(1979-),男,山东泰安人,教授,博士,主要研究方向:轨道交通运行管理、决策优化;乔俊(1993-),女,陕西周至人,硕士研究生,主要研究方向:轨道交通运行管理、决策优化;汤霖(1989-),男,甘肃武威人,硕士,主要研究方向:轨道交通运行管理、决策优化;焦志臻(1992-),男,甘肃兰州人,助理工程师,主要研究方向:铁路车流组织优化、货物运输组织。
• 基金资助:

国家重点研发项目（2016YFB1200100）；国家自然科学基金资助项目（71861022，61563028）。

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.

CLC Number: