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

Railway crew rostering plan based on improved ant colony optimization algorithm

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

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.