基于变邻域下降的列车运行时刻调整算法

Train Rescheduling Algorithm Based on Variable Neighborhood Descent

高速铁路区间失效可能严重影响列车正常运行,区间失效后调度员需要及时调整列车运行时刻.本文主要针对区间失效后不改变列车顺序下的时刻调整问题进行研究,建立了以所有列车在各站晚点时间之和为目标的列车运行调整模型,模型中各约束条件保证列车安全运行.针对目前常见的获取最优解或次优解需花费较长时间的问题,提出一种基于变邻域下降算法的多阶段变邻域下降算法.算法的第一、第二阶段使用变邻域下降算法结合禁忌表快速确定哪些列车经过调整后的时刻能与图定时刻相等,第三阶段则调整未恢复到图定时刻的列车.最后,以西成客运专线与某日的列车时刻数据为算例,求解多种区间失效场景下的列车运行时刻调整方案验证算法的有效性与实时性.

The blockage of the high-speed railway segment may seriously affect the original timetable of the train.If it happens,the dispatcher needs to adjust the timetable.This study focuses on how to reschedule the timetable without changing the sequence of trains that are affected by the segment blockage.A train rescheduling model is formulated with aiming at minimizing the sum of the delay time of all trains in each station,and all constraints of the model is used to ensure the safety of trains.And a multi-stage variable neighborhood descent algorithm is proposed to solve the problem that it takes a long time to get the optimal or suboptimal solution.In the first and second stages of the algorithm,variable neighborhood descent combined with tabu table is used to quickly ascertain the trains which can maintain the original timetable after several adjustments,and then adjust other trains in the third stage.Finally,taking Xi’an-Chengdu Passenger Dedicated Line and the timetable of a single day as an example,the validity and real-time performance of the algorithm is verified by getting the timetable adjusted under various interval failure scenarios.