引用本文:季彬,周赛琦,张政.分支定价方法求解带二维装箱约束的车辆路径问题[J].控制理论与应用,2023,40(3):409~418.[点击复制]
JI Bin,ZHOU Sai-qi,ZHANG Zheng.Branch-and-price approach for solving the vehicle routing problem with two-dimensional loading constraints[J].Control Theory and Technology,2023,40(3):409~418.[点击复制]
分支定价方法求解带二维装箱约束的车辆路径问题
Branch-and-price approach for solving the vehicle routing problem with two-dimensional loading constraints
摘要点击 2619  全文点击 752  投稿时间：2021-04-09  修订日期：2022-05-18
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/CTA.2021.10292
  2023,40(3):409-418
中文关键词  车辆路径  混合整数线性规划  分支定价  二维装箱问题
英文关键词  vehicle routing  mixed integer linear programming  branch-and-price  two-dimensional packing problem
基金项目  国家自然科学基金项目(72001216), 湖南省自然科学基金项目(2020JJ5780), 国家自然科学基金项目(71672193)资助.
作者单位E-mail
季彬* 中南大学 交通运输工程学院 cumtjibin@126.com 
周赛琦 中南大学 交通运输工程学院  
张政 中南大学 交通运输工程学院  
中文摘要
      面向家具、电器等货物的物流配送场景, 研究带二维装箱约束的车辆路径问题(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.