铁路空车调整模型的D-W分解算法  

Dantzig–Wolfe Decomposition Algorithm Applied to Model of Distributing Empty Railway Wagons

作　　者：薛锋[1,2] 孙宗胜 XUE Feng;SUN Zong-sheng(School of Transportation and Logistics,Southwest Jiaotong University,Chengdu 611756,China;National United Engineering Laboratory of Integrated and Intelligent Transportation,Chengdu 611756,China)

机构地区：[1]西南交通大学,交通运输与物流学院,成都611756 [2]综合交通运输智能化国家地方联合工程实验室,成都611756

出　　处：《交通运输工程与信息学报》2019年第4期43-48,共6页Journal of Transportation Engineering and Information

基　　金：国家自然科学基金项目（61203175,61403022）;中央高校基本科研业务费专项资金项目（2682013CX068,2682016CX118）;四川省科技计划项目（2019YJ0211）

摘　　要：空车调整主要是指对铁路空车车辆进行合理优化,对铁路空车调整问题进行模型构建及算法研究可以促进车辆运用效率的提高与相关运输费用的降低.本文在对铁路空车调整理论研究的基础上,构建了铁路空车调整模型,并基于D-W分解算法对其进行求解.经过算法复杂度对比分析,发现D-W分解算法时间复杂度为O(n),优于蚁群算法、遗传算法等启发式算法,并最终通过算例进行了验证.Rational optimization is required for the distribution of empty wagons that have accumulated in parts of a rail network.Constructing models and using algorithms to research the optimum placement of empty wagons can improve the efficiency of vehicle operations and reduce the cost of transportation.Based on the theory of adjusting the placement of empty railway wagons,a model for the optimal placement of empty wagons was constructed and solved using the Dantzig-Wolfe(D-W)decomposition algorithm.Applying this complex algorithm to the placement of empty wagons in a specific railway network produced the D-W decomposition algorithm complexity that is designated as O(n).The ant colony algorithm and genetic algorithm are more complex than O(n);however,the D-W decomposition algorithm is shown to be superior to these and other heuristic algorithms.An example is provided that illustrates our findings.

关 键 词：铁路运输 空车调整 D-W分解算法 算法复杂度 

分 类 号：U292.45[交通运输工程—交通运输规划与管理]