分支定价方法求解带二维装箱约束的车辆路径问题

Branch-and-price approach for solving the vehicle routing problem with two-dimensional loading constraints

面向家具、电器等货物的物流配送场景,研究带二维装箱约束的车辆路径问题(2L–CVRP),构建了2L–CVRP的混合整数线性规划模型.为求解大规模2L–CVRP,构建了该问题集合划分模型,提出基于分支定价的方法.针对分支节点的松弛模型,基于列生成策略将其分解为线性规划主问题、带资源和二维装箱约束的最短路径子问题,并提出基于ng-route松弛策略的标签算法和基于禁忌搜索的装箱算法有效求解复杂子问题.仿真结果表明,提出的方法可高效求解大规模2L–CVRP,其中ng-route松弛策略能有效提升算法求解效率,研究成果为装箱约束下大规模车辆路径问题的高效求解提供了有效途径.

Oriented to the logistics and distribution scenarios of goods such as furniture and appliances,this study addresses the vehicle routing problem with two-dimensional loading constraints(2L–CVRP).First,a mixed integer linear programming model of the 2L–CVRP is constructed.Then,a branch-and-price approach is proposed with a set partition model to solve the large-scale 2L–CVRPs.By using column generation approach,the relaxed 2L–CVRP at each branchand-bound node is decomposed into a linear programming master problem and a pricing problem of the elementary shortest path with resource constraints and two-dimensional loading constraints.Meanwhile,a labeling algorithm based on the ngroute relaxation strategy and a tabu-search-based packing algorithm are proposed to effectively solve the complex pricing problem.Numerical experiments and comparison results show that the proposed approach can efficiently solve the largescale 2L–CVRPs,and that the ng-route relaxation strategy can improve the efficiency of the approach.As such,this study provides an effective approach to solve the large-scale vehicle routing problems with loading constraints.