基于改进分支定价算法的器具取配送运输问题研究

Containers Allocation and Recycle Transportation Problem with an Improved Branch-and-price Algorithm

为解决物流集装单元化背景下器具运输成本高且灵活性差问题,本文提出集装器具循环调拨与回收的运输方式,在此运输方式下的器具运输问题属于供需未匹配与需求可拆分的取送货车辆路径问题(USDSPDVRP)。为在准确描述问题的基础上使模型易于求解,提出两阶段建模思路,设计解决USDSPDVRP模型的改进分支定价算法,通过Dantzig-Wolfe分解将模型分解为选择运输方案使用数量的限制主问题与根据主问题结果生成新运输方案的子问题,并设计相适应的路径缩减策略改进算法,实现高效求解复杂子问题的目的。算例结果表明,提出的改进分支定价算法相比Gurobi求解器,求解时间平均减少了83.9%,求得的可行解与精确解目标值间隔平均为2.8%。并对比分析了循环运输与直达运输的运输效益指标,证明了循环调拨与回收的运输方式能够有效减少运输总费用和车辆使用数,提高车辆满载率。

Considering the drawback of high cost and poor flexibility of equipment transportation under containerization of logistics,a transportation mode of circular allocation and recovery of containers was proposed.In this transportation mode,the container transportation problem belongs to Unpaired Supply-Demand and Split Pickup and Delivery Vehicle Routing Problem(USDSPDVRP).With an accurate problem description,a two-stage model was proposed.And an improved branch pricing algorithm was designed to solve the USDSPDVRP model.The model is decomposed into a main problem of resolving the number of transport schemes used and a sub-problem model of generating new transport schemes based on the results of the main problem by Dantzig-Wolfe decomposition.To solve complex sub-problems efficiently,an appropriate path reduction strategy is designed.Results show that the proposed algorithm is effective.Compared with the result of the Gurobi solver,the average computational time is reduced by 83.9%,and the average gap between the feasible solution and the optimal solution is 2.8%.At the same time,a comparative analysis of cyclic dispatch transportation and direct transportation proves that the cyclic dispatch transportation can reduce the cost and the number of vehicles,and increase the load rating of vehicles.