《基于新型下界方法的动态容量弧路径问题元启发式算法评估》学术报告

第一作者及机构
本文由英国University of Birmingham的Hao Tong与Leandro L. Minku、德国Honda Research Institute Europe GmbH的Stefan Menzel和Bernhard Sendhoff，以及中国香港Lingnan University（同时任职于University of Birmingham）的Xin Yao合作完成，发表于IEEE Computational Intelligence Magazine 2024年11月刊，DOI: 10.1109/MCI.2024.3440213。

学术背景
本研究聚焦于组合优化问题（Combinatorial Optimization Problems, COPs）中的动态容量弧路径问题（Dynamic Capacitated Arc Routing Problem, DCARP）。DCARP是经典NP难问题，其现实应用涵盖道路撒盐、垃圾回收等场景。现有元启发式算法（如进化算法）虽能提供近似最优解，但其性能评估通常依赖算法间相对比较，因真实全局最优解未知导致绝对性能评估困难。针对这一空白，本研究提出首个针对DCARP的节点匹配下界方法（Node Matching Lower Bound, NMLB），旨在通过计算问题实例的紧致下界（Lower Bound），为算法性能提供客观评价标准。

研究流程与方法
1. 问题建模与下界定义
- 动态环境建模：DCARP实例由动态事件（如任务新增、道路封闭）触发，需在部分路径已执行的情况下重新优化。
- 下界转换：通过构造辅助图（Auxiliary Graph）将下界计算转化为最小成本匹配问题（Minimum Cost Matching Problem, MCMP），并应用Blossom算法求解。

1. NMLB方法开发

   • 节点匹配机制：考虑外部车辆（位于非 depot 节点）的剩余容量和位置，通过构造四类节点集（A: depot副本；B: 任务节点副本；C: 外部车辆返回路径的depot副本；D: 外部车辆当前位置）形成辅助图。
     
   • 理论证明：基于三角不等式，证明节点自匹配的必然性（Theorem 2），确保下界有效性。
     

2. 图剪枝策略

   • 冗余节点剔除：针对高任务节点（degree >2），通过预筛选可能与非副本节点匹配的候选节点（Algorithm 2），显著降低MCMP计算复杂度（从O(|Vx|³)优化至实际运行时间减少50%以上）。
     

3. 实验验证

   • 紧致性测试：在已知全局最优解的GDB数据集上，NMLB与真实最优解的平均偏差为4.3%（表I），验证其紧致性。
     
   • 算法评估：对比Memetic Algorithm with Extended Neighborhood Search (MAENS)和Repair Operator based Tabu Search (RTS)在复杂VAL/EGL实例上的表现。以近似百分比偏离（Approximate Percentage Deviation, APD）为指标，MAENS在VAL实例中APD中位数为5.6%，而EGL实例因任务规模更大，APD升至50%以上（表II-III），表明算法在大规模实例中仍有优化空间（图6）。
     

主要结果
1. 下界紧致性：NMLB在小型DCARP实例（如GDB1-23）中与理论最优解差距极小（多实例gap=0%），但在节点数>20的复杂实例中偏差增大。
2. 算法性能：基于下界的评估显示，现有算法在任务密集度高的实例中表现不佳（如EGL-e2-c APD达91.4%），揭示了算法改进方向。
3. 剪枝效率：剪枝策略使EGL数据集计算时间从22.7秒（未剪枝）降至8.8秒（表III），且效率提升与高degree节点数线性相关（图7）。

结论与价值
1. 方法论贡献：首次提出DCARP动态下界方法，填补了动态优化问题绝对性能评估的空白。
2. 应用价值：为道路维护、物流调度等动态场景的算法选择提供了量化标准。
3. 理论意义：通过将动态约束转换为匹配问题，为其他NP难动态问题的下界设计提供了范式。

研究亮点
1. 创新性：首创动态环境下的DCARP下界方法，突破了静态CARP下界技术的限制。
2. 技术突破：提出的图剪枝策略将计算复杂度降低一个数量级，使大规模实例评估可行。
3. 跨学科启示：结合图论（Blossom算法）与元启发式评估，为动态优化领域提供了新工具。

其他价值
研究开源了所有DCARP实例与代码（GitHub），促进了领域内可比性研究。未来的工作可探索更紧致的下界或适配CPLEX/Gurobi等求解器以验证大规模实例的优化潜力。