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

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

作　　者：王保华 何世伟[2] 

机构地区：[1]Amazon Research,北京100024 [2]北京交通大学交通运输学院,北京100044

出　　处：《铁道学报》2018年第2期8-14,共7页Journal of the China Railway Society

基　　金：国家自然科学基金(61374202);中国铁路总公司科技研究开发计划(2017X004-D,2017X004-E).

摘　　要：研究考虑车辆周转的铁路动态货运服务网络设计问题,目标是在合理设计铁路运输服务网络的基础上提高车辆利用率。将传统的离散时空网络拓展为考虑车辆周转的超级网络,构建混合整数规划模型,同时考虑列车开行时段、编组内容、空车调配、车辆归属、运输服务水平等约束。基于模型的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.

关 键 词：货运车辆周转 动态服务网络设计 分支-定价-切割算法 

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