城市轨道交通乘务交路方案编制的禁忌搜索优化方法

Optimization method of Tabu Search algorithm for urban rail transit crew scheduling scheme

针对城市轨道交通普遍采用轮乘制、日班和两头班混合等特点,对城市轨道交通乘务交路方案编制问题进行研究,旨在降低乘务成本并提高乘务效率.首先,通过分析城市轨道交通乘务交路方案的构成要素,考虑值乘时长、值乘片段接续时间和接续地点等要求,构建值乘片段、值乘任务构成和乘务规则约束,由此建立以乘务组数量和总接续时间等综合指标最小化为目标函数的多目标0-1整数规划模型.然后,针对该模型设计禁忌搜索(Tabu Search,TS)算法进行求解,以先到先走(First-In-First-Out,FIFO)的就近指派原则得到初始解,并设计4种邻域变换策略,以提高邻域解的多样性,并构建基于多邻域结构的禁忌搜索求解算法,实现对乘务交路方案的优化.最后,以广州地铁7号线的乘务交路方案为例进行实例验证.研究结果表明:优化方案较实际运营方案的乘务作业段数和总接续时间分别降低了20%和4.94%,每个乘务作业段值乘列车数量从8.2列增加到10.3列,有效驾驶时间从5.4 h增加到5.8 h,优化方案的各项指标均得到显著提升.研究成果可以为城市轨道交通乘务计划编制提供理论和方法支持.

Considering the widespread adoption of rotation crew regulations and the mixing of day shifts and day-and-night shifts in urban rail transit,this study addresses the crew scheduling scheme to reduce service costs and improve efficiency.Firstly,by analyzing the elements of the urban rail transit crew scheduling scheme and considering requirements such as crew segment duration,connection time,and locations,a multi-objective 0-1 integer programming model is established.This model aims to minimize comprehensive index such as the number of crew members and total connection time.Secondly,a Tabu Search(TS) algorithm is designed to solve this model,using the First-In-First-Out(FIFO) principle for initial solution assignment and four neighborhood transformation strategies to enhance solution diversity.A multi-neighborhood structure-based Tabu Search Algorithm is constructed to optimize the crew scheduling scheme.Finally,the proposed method is validated using the crew scheduling scheme of Guangzhou Metro Line 7.Results demonstrate that the optimized scheme reduces the number of crew segments and total connection time by 20% and 4.94%,respectively,compared to the actual operation scheme.The number of trains on duty in each crew segment increases from 8.2 to 10.3,and the effective driving time increases from 5.4 to 5.8 hours.All indicators of the optimization plan are significantly improved,providing theoretical and methodological support for urban rail transit crew planning.