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

作     者：季彬 周赛琦 张政 JI Bin;ZHOU Sai-qi;ZHANG Zheng

作者机构：中南大学交通运输工程学院湖南长沙410075 

出 版 物：《控制理论与应用》 (Control Theory & Applications)

年 卷 期：2023年第40卷第3期

页      面：409-418页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 081104[工学-模式识别与智能系统] 08[工学] 082303[工学-交通运输规划与管理] 0835[工学-软件工程] 0811[工学-控制科学与工程] 082302[工学-交通信息工程及控制] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0823[工学-交通运输工程] 

基　　金：国家自然科学基金项目(72001216) 国家自然科学基金项目(71672193)资助 湖南省自然科学基金项目(2020JJ5780) 

主　　题：车辆路径 混合整数线性规划 分支定价 二维装箱问题 

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