考虑车辆周转的铁路动态货运服务网络设计优化模型及其分支-定价-切割算法

Optimization Model and Branch-price-cut Algorithm for Design of Railway Dynamic Freight Service Network Considering Rolling Stock Management

研究考虑车辆周转的铁路动态货运服务网络设计问题,目标是在合理设计铁路运输服务网络的基础上提高车辆利用率。将传统的离散时空网络拓展为考虑车辆周转的超级网络,构建混合整数规划模型,同时考虑列车开行时段、编组内容、空车调配、车辆归属、运输服务水平等约束。基于模型的NP-Hard特性,给出一种分支-定价-切割算法,通过在模型中添加Benders割的方法调整可行域,通过列生成方法避免网络规模较大导致可选径路数量过多的问题,该算法可保证模型收敛至最优解。算例证明了模型和算法的有效性,通过灵敏度分析验证可用车辆数量对于空车调配方案的影响。

This paper investigated the problem of railway dynamic freight service network design considering rolling stock management,in order to reasonably design railway transportation service network and improve the utilization ratio of rolling stock.The discrete traditional time-space network was extended to a super network to accommodate rolling stock flow.A mixed integer programming model(MIP),which considers the constraints of train operating time period,make-up,empty car reposition,transportation service level,was constructed.Based on NP-Hard characteristics of the model,a branch-price-cut algorithm was developed to obtain the global optimal solution of the model.Benders' cut was generated to adjust the feasible region.A column generation method was used to handle the explosion of candidate path set of rolling stock flow and shipment flow.Finally,a numerical example was presented to prove the validity of the model and algorithm.The sensitivity analysis was also presented to show the influence of available rolling stock on empty car reposition.