大规模货物列车运行图优化编制的一种拉格朗日松弛启发式算法

针对货物列车运行图优化编制规模庞大、精确求解困难的问题,构造时空网络将列车运行线铺画描述为路径求解问题,将各类约束转化为时空网络节点选择限制,建立整数规划模型。该问题本质在于疏解各列车运行线潜在冲突。对原模型进行拉格朗日松弛,将列车运行线潜在冲突表示为各节点罚数,设计启发式算法并通过拉格朗日乘子更新迭代求解。以京九线北京西至阜阳区段为例,对该区段711条运行线中的439条货物列车运行线进行了优化编制实验。结果表明,在满足运行线铺画条数的前提下,全图货物列车平均旅行速度由39.28 km/h提升至41.81~43.72 km/h,所提出的算法是解决大规模列车运行图编制的一种有效算法。

A Large-scale Freight Train Diagram Optimization Heuristic Algorithm Based on Lagrangian Relaxation

Considering the problem of large scale and difficulty to achieve a precise solution in the optimization of freight train operation diagram,this paper used a time-space graph to describe the train path drawing as a routing solving problem,and transformed various constraints into the selection violation of the node of the time-space graph,to establish an integer programming model.The nature of the problem is to solve the possible conflicts among train paths,to relax the model in a Lagrangian way,and to represent the possible conflicts among train paths as the node penalty.A heuristic algorithm was used to obtain feasible solution and update the Lagrangian multiplier to optimize iteratively.Based on the verification study of the Beijing West-Fuyang section of Beijing West-Jiulong railway,an optimization experiment was conducted on 439 freight train paths out of all 711 train paths in the section.The results show that,under the precondition of satisfying the demand of arranging all the train paths,the average travel speed has increased from 39.28 km/h to 41.81-43.72 km/h.The algorithm proposed is effective in solving large-scale freight train diagram optimization.