基于替代图的列车运行调整计划编制及优化方法

A Method for Generation and Optimization of Train Operation Adjustment Plan Based on Alternative Graph

借助对列车优先级、节点、替代弧和替代对等参数的定义,以列车追踪运行间隔时间、列车连发间隔时间和列车间越行地点等为约束条件,以替代图中最长路径最短为优化目标,建立基于替代图的列车运行调整计划编制及优化模型。采用本地搜索算法对模型求解,经过原始计划生成和初级优化,得到有瑕疵(冲突)的但资源利用率较高的初始调整计划。当初始调整计划未满足需求或计划在实施过程中受到扰动需要修正时,采用分层多级优化分枝定界算法,对初始调整计划对应的替代图进行进一步的优化,得到优化的列车运行调整计划。由于替代图与列车运行调整计划的对应关系,用这2种算法对替代图分阶段求解和优化,可以得到满足不同需求的调整计划。通过对模拟环境的仿真,验证了模型和优化方法的完整性和可行性。

With the help of parameter definitions of train priority, node, alternative arc, alternative pair and so on, considering the time interval between trains spaced by automatic block signals, the time interval for two trains dispatching in succession in the same direction, overtaking place between trains and etc. as constraints, the generation and optimization model of train operation adjustment plan based on alternative graph is established aiming at minimizing the max-path in alternative graph. Local search algorithm with 2 phases of original plan＇s generation and preliminary optimization is adopted to solve the model and a flawed （conflict） original adjustment plan is produced with high resource utilization rate. Multistage stratified op- timized branch and bound algorithm is brought forward to optimize the original adjustment plan＇s corre- sponding alternative graph and outputs the optimized train operation adjustment plan when the original ad- justment plan dissatisfies the requirements or the plan suffers disturbance in practice. Due to the corre- sponding relationship between alternative graph and train operation adjustment plan, phased solving and optimization by these 2 algorithms can satisfy adjustment plan＇s different requirements. The integrity and feasibility of the model and optimization method are validated through environment simulation.