最大通过能力下高速铁路运行图优化研究

Optimization of high-speed railway timetabling based on maximum utilization of railway capacity

为最大限度地利用多等级列车共存的高速铁路繁忙线路通过能力,同时保证运输质量,构建高速铁路网通过能力最大化条件下的列车运行图优化模型。根据列车运行过程中不得有冲突的特点将该问题抽象为时空网络中带约束的最大独立集问题。通过D-W分解将模型进行转化及线性松弛。采用列生成算法对有大规模决策变量的松弛问题进行求解。在松弛解的基础上设计分支定界算法求得最优可行列车最大独立运行线集。研究结果表明:所建模型具有在不同参数表示的需求场景下灵活求得兼顾运能和运输质量的有效运行图的功能。通过与求解独立集问题的常用启发式算法对比,本文方法可在保持旅行时间平均1.33%波动条件下使得通过能力值目标提高2.56%、总目标值提高4.6%。

In order to maximize the capacity utilization in busy high-speed railways with mixed trains and ensuring the transportation efficiency,this paper constructs the model of train timetabling with maximum capacity.Since there must be no conflicts between trains,the problem is abstracted into constrained maximum independent set in the space-time network.The model are transformed and linearly relaxed by D-W decomposition method.Column generation is applied to solve the relaxed problem.Based on the relaxed solution a branch and bound algorithm is designed to find the optimal feasible solution.The experiment results show that the proposed method is able to flexibly find timetables with balanced capacity and efficiency under each scenario of demand specified by different parameters.Compared with general heuristic algorithm,on average,the proposed method makes effort to improve the objective value of capacity by 2.56%,the total objective value by 4.6%while holding the fluctuation of the objective value of total travel time within 1.33%.