车站封锁下基于问题知识的高速铁路列车运行实时调整方法

Real-time rescheduling approach of train operation for high-speed railways using problem-specific knowledge under a station blockage

针对突发事件导致的车站封锁情况,本文以列车运行图为问题对象,以进化计算框架为基础,提出基于问题知识的运行图实时调整方法,通过减小列车总晚点时间,保证高铁运营的安全高效和旅客的满意舒适.首先,基于调整列车发车次序的运行图调整策略提出排列编码方法,用于减少解空间的无效搜索.之后,根据“紧追踪”的列车运行追踪方式,设计启发式解码方法消除所有行车作业约束,提升算法求解效率.最后,将调度员调整运行图的经验作为问题知识,用于初始化进化计算的初始种群,由此提出基于问题知识的启发式种群初始化方法,加快算法前期的收敛速度并提高求解方案质量.以京津高速线为例,在北京南站设置车站封锁下20~150 min不同封锁时长的9个典型场景,选择加强精英保留遗传算法和差分进化算法,分别应用实整数编码和排列编码,与随机种群初始化和启发式种群初始化的不同组合进行仿真实验.仿真结果表明,相较于实整数编码难以获取可行解,2种进化算法应用排列编码方法后,能在9 s的平均时间内给出列车总晚点时间最小的调整方案.在启发式种群初始化的改进下,2种进化算法能更快地收敛于近似最优解.选取加强精英保留遗传算法应用排列编码和启发式种群初始化的改进变体,作为本文最优改进进化算法.针对CPLEX无法在10 min获得最优解的7个场景,该改进进化算法都能在20 s内给出近似最优解.

This study considers the train timetable as the problem object to investigate the station blockage caused by emergencies. Based on the evolutionary algorithm framework, a real-time rescheduling approach using problem-specific knowledge is proposed. This approach ensures the safety and efficiency of high-speed rail operations and the satisfaction and comfort of passengers by minimizing the total train delay. First, a permutation encoding method is developed to reduce invalid searches in the search space based on the rescheduling strategy of reordering train departure sequences. Next, according to the train operation tracking mode, called tracking interval control, a heuristic decoding method is designed to eliminate all constraints of train operation to improve efficiency. Finally, the dispatcher’s experience in adjusting the train timetable is used as the problem-specific knowledge to initialize the initial population of evolutionary computing. A heuristic population initialization method based on problem-specific knowledge is employed to speed up the algorithm convergence in the early stage and improve solution equality. Furthermore, the Beijing–Tianjin high-speed railway line is used as an example. Nine typical scenarios with different blockage durations of 20–150 min under the station blockage are installed at the Beijing South station. The strengthened elitist genetic algorithm(SEGA) and differential evolution(DE)are selected to perform the simulation using different combinations of the real-integer or permutation encoding and random or heuristic population initialization, respectively. The simulation results indicate that, compared with the real-integer encoding that cannot obtain feasible solutions, the two evolutionary algorithms can provide the rescheduling solution with a smaller total train delay in an average time of 9s after using the permutation encoding. Besides, the results of the two evolutionary algorithms improved by the heuristic population initialization can quickly converge to a quasi-optimal solution. Finally, the SEGA in the permutation encoding with the heuristic population initialization is chosen as the optimal improved evolutionary algorithm. This improved evolutionary algorithm can provide quasi-optimal solutions in 20s in the seven scenarios where the CPLEX cannot provide optimal solutions in 10 min.