学术研究报告：一种针对三维装载约束下可拆分配送车辆路径问题的高效局部搜索算法
一、作者与发表信息
本研究由Han Zhang（南方科技大学计算机科学与工程系；香港理工大学计算学系）、Qing Li（香港理工大学计算学系）和Xin Yao（岭南大学数据科学学院）合作完成，发表于Memetic Computing期刊2025年第17卷第18期，DOI: 10.1007/s12293-025-00451-9。
二、学术背景
科学领域与问题背景
本研究属于组合优化领域，聚焦于三维装载约束下的可拆分配送车辆路径问题（3L-SDVRP, Split Delivery Vehicle Routing Problem with Three-Dimensional Loading Constraints）。该问题是传统车辆路径问题（VRP）的复杂变体，结合了三维装箱问题（3D Packing）和可拆分配送（Split Delivery）两大NP难问题，具有以下核心挑战：
1. 可拆分性：单个节点的货物可分配给多辆车运输，以解决车辆容量不足或货物体积超限问题。
2. 三维装载约束：货物为长方体，需考虑其尺寸、重量、装载顺序及空间位置，需同时优化路径规划与装载方案。
研究动机与目标
现有方法（如Bortfeldt和Yi提出的SDVRLH2算法）存在效率低、解质量次优等问题，具体表现为：
- 装箱策略生成子空间不足，导致车辆利用率低；
- 传统搜索算子未充分利用问题特征，搜索效率低；
- 拆分策略计算成本高。
本研究旨在提出一种更高效的局部搜索算法，通过改进装箱方法、设计新型搜索算子、优化拆分策略及后优化方法，减少车辆使用数量（首要目标）和总行驶距离（次要目标）。
三、研究流程与方法
1. 算法框架
算法采用“装箱优先，路径次之”策略，整体流程如下：
1. 初始解生成：随机生成初始解（“巨型路径”表示）。
2. 迭代优化：基于当前最优解进行局部搜索，包括：
- LKH变异算子：独立优化每条路径（视为TSP问题）；
- 路径对交换（RPS）：跨路径节点交换；
- 多对精英重组（MPER）：合并优质交换操作。
3. 自适应拆分策略：动态决定是否拆分货物，降低计算开销。
4. 后优化：通过负载重分配和单路径优化进一步提升解质量。
2. 关键创新方法
(1) 改进装箱方法
- 子空间生成优化：
- PM1：每次装载两个箱子，生成5个子空间（原方法仅2个）；
- PM2：每次装载一个箱子，生成3个子空间。
- 多阶段2C-SP构建：通过多轮混合层构建（合并不同节点的货物层），提升车辆空间利用率。
(2) 新型搜索算子
- LKH变异：利用LKH算法优化单条路径的TSP子问题。
- 路径对交换（RPS）：跨路径节点交换，生成邻域解。
- 多对精英重组（MPER）：筛选兼容的优质交换操作，组合为新解。
(3) 自适应拆分策略
根据车辆剩余容量与节点货物层配置动态决定是否拆分，替代原算法的固定成本循环，减少计算量。
(4) 后优化方法
- 负载重分配：将低负载车辆的货物转移至其他车辆，减少车辆数；
- 单路径优化：使用LKH变异缩短各路径行驶距离。
四、主要实验结果
1. 对比基准算法（SDVRLH2）
- 小规模实例（<100节点）：
- 平均减少1.3辆车，最大减少11辆车（实例SD11）；
- 总行驶距离平均增加37.79%，但车辆减少优先级更高。
- 大规模实例（100-200节点）：
- 平均减少4.5辆车，最大减少15辆车（实例B-Y19）；
- 计算效率显著提升，仅需0.18%的适应度评估次数（FEs）。
2. 消融实验验证
- 改进装箱方法（A1）：车辆数减少43.2（小规模）和51.2（大规模）；
- 新型搜索算子（A2）：总行驶距离降低6.15%（大规模），FEs减少60%-80%；
- 自适应拆分（A3）：进一步减少FEs至0.2%-4.09%；
- 后优化（A4）：显著优化大规模实例的车辆数与路径。
五、结论与价值
科学价值
- 算法创新：首次将LKH算法与自适应拆分策略结合，解决3L-SDVRP问题；
- 性能突破：在车辆数最小化上超越现有最佳算法，尤其适用于大规模实例；
- 方法论贡献：为复杂约束下的路径优化提供了可扩展的局部搜索框架。
应用价值
- 物流成本优化：减少车辆数可直接降低车队购置、维护及人力成本；
- 计算效率：适合实时调度需求，如电商仓储、冷链物流等场景。
六、研究亮点
- 多目标协同优化：优先车辆数，兼顾行驶距离，符合实际物流需求；
- 混合策略设计：融合装箱启发式与路径搜索，提升解质量；
- 计算效率革新：通过自适应策略减少冗余计算，适用于工业级问题规模。
七、其他价值
- 开源潜力：算法框架可扩展至其他VRP变体（如时间窗约束）；
- 跨领域应用：方法可迁移至机器人路径规划、航空货运调度等领域。
（全文约2400字）