铁路集装箱运输动态服务网络设计及Benders分解算法

A Dynamic Service Network Design for Railway Container Transportation and Benders Decomposition

充分考虑箱流的中转方案,研究铁路集装箱运输动态服务网络的设计方法。以总成本最小为优化目标,构建了铁路集装箱运输动态服务网络设计的线性规划模型。根据模型特点,采用Benders算法进行求解,将问题分解为服务网络设计的主问题及箱流分配的子问题,通过计算子问题的对偶模型不断产生主问题的割平面,由此进行迭代求解。为克服算法收敛速度慢的缺点,在主问题模型中添加有效不等式,使主问题更加紧致。以北京、郑州等集装箱办理站构建的运输网络为例,验证了模型和算法的有效性。算例结果表明,对于求解大规模的集装箱运输动态服务网络设计问题,改进后的算法运行46 s得到优化解,GAP为1.56%,未改进的Benders算法运行相同时间后,GAP为45.17%,改进策略的运用有效提高了计算效率;所得服务网络的总成本比所有箱流均采用直达运输模式服务网络的总成本减少了20%;与现有集装箱班列开行方案相比,优化后的班列发车时段、开行频率在满足运输需求的同时,保证了各组箱流能在规定运到期限内送至目的站。

A method of dynamic service network design for railway container transportation is studied,considering the transfer schemes of containers.A linear programming model of the dynamic service network design for railway con⁃tainer transportation is constructed to minimize the total cost.In accordance with the characteristics of the problem,a solution approach based on Benders decomposition is developed.Then,the formulation is decomposed into a master problem of service network design and subproblems of container flow allocation.The cuts of the master problem are constantly generated by utilizing the solutions of dual subproblems to solve them iteratively.Some valid inequalities are used to tighten the master problem,thus overcoming slow convergence.The effectiveness of the model and algo⁃rithm is demonstrated,taking the network constructed by railway container terminals in Beijing and Zhengzhou as a case study.The numerical results indicate that for the design of large-scale dynamic service network,the improved al⁃gorithm spends 46 s to obtain an optimized solution,and the Gap is 1.56%.The unimproved Benders decomposition takes the same time,and the Gap is 45.17%.The application of improved strategies can improve calculation.The to⁃tal cost of the optimized service network is reduced by about 20%compared to the service network with direct transpor⁃tation organization.Compared with the existing plans for container train service,the optimized departure time and oper⁃ation frequency of container trains can meet the transportation demand,ensuring that each container flow can be delivered to the destination within the specified transit period.