尚正阳，顾寄南，潘家保

(1.安徽工程大学 机械与汽车工程学院，安徽 芜湖 241000；2.江苏大学 机械工程学院，江苏 镇江 212000)

0 引言

基于广泛的服务对象与客户需求，我国电子商务已于2019年突破30万亿元规模[1]，高效低耗的物流网络运行是提升社会经济效益的重要手段。现阶段，信息技术、交通运输与包装工程的快速发展，为精准的配送过程管控提供了硬件支撑，也为实施系统的物流调度优化创造了条件。考虑装载约束的路径优化问题模拟了现实配送行为，旨在同时满足货物装载与车辆载重约束，实现整体路径最短。根据不同货物属性，装载状态可分为二维与三维两种类型，本文针对二维装载约束下的车辆路径问题(Two-Dimensional Loading Capacitated Vehicle Routing Problem, 2L-CVRP)展开研究。

2L-CVRP是在带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)中增加了货物装载约束，需要不断地调用二维装箱问题(Two-Dimensional Bin Packing Problem, 2BPP)模块，进行相应的填充可行性验证，它是基于CVRP与2BPP组合的NP-hard调度问题[2]。2007年，IORI等[3]最先研究2L-CVRP，并从路径寻优与装箱验证两个方面分别提出了分支切割(branch-and-cut)与分支定界(branch-and-bound)方法，完成了求解算法构建。这种两相式的算法构造策略，明确了2L-CVRP研究内容，得到了后续学者的广泛使用。

由于车辆载重与容积的双重约束，致使迭代过程易于陷入局部较优解，需要更为精准的寻优操作方法。GENDREAU等[4]在禁忌搜索的寻优框架下，设计了不同配送序列的邻域变换方式;LEUNG等[5]与RUAN等[6]分别将模拟退火与蜜蜂交配算法引入其中;DOMINGUEZ等[7]结合经典的路径优化Saving方法[8]，提出了具有导向性的……