本文档属于类型a（单篇原创研究论文），以下是针对该研究的学术报告：

动态带容量弧路由问题（Dynamic Capacitated Arc Routing Problem, DCARP）的新型广义元启发式框架研究

1. 研究作者与发表信息

本文由Hao Tong（英国伯明翰大学）、Leandro L. Minku（伯明翰大学）、Stefan Menzel 和 Bernhard Sendhoff（德国本田欧洲研究院）、Xin Yao（伯明翰大学/南方科技大学）合作完成，发表于IEEE Transactions on Evolutionary Computation（2022年12月，第26卷第6期）。研究得到本田欧洲研究院、广东省重点实验室等机构资助。

2. 学术背景

科学领域：组合优化（Combinatorial Optimization）、动态优化（Dynamic Optimization）与计算智能（Computational Intelligence）。
研究动机：
- 带容量弧路由问题（Capacitated Arc Routing Problem, CARP）是现实物流（如垃圾收集、道路融雪作业）的核心模型，但传统研究仅关注静态场景，忽略了车辆服务过程中的动态变化（如道路封闭、新增任务）。
- 现有动态CARP（DCARP）研究存在两大缺陷：动态场景定义不完整，且算法复杂度过高，难以利用静态CARP的丰富算法成果。
研究目标：
1. 提出首个DCARP的数学建模；
2. 设计模拟车辆服务过程的仿真系统；
3. 开发通用框架（GOfVTS），将静态CARP算法泛化至DCARP。

3. 研究方法与流程

（1）数学建模与仿真系统设计

• 数学模型：定义了DCARP实例的三要素——动态事件触发后的更新路网、外部车辆（部分执行任务的车辆）状态、完整服务场景。
  
  • 目标函数：最小化服务总成本（路径成本扣除虚拟任务补偿成本）。
    
  • 约束条件：车辆容量、任务唯一服务、返回仓库等。
    
• 仿真系统：
  
  • 基于静态CARP基准（如EGL数据集）生成动态场景，模拟9类动态事件（表II），包括道路封闭（*road closure*）、拥堵加剧/缓解（*congestion change*）、新增任务（*added demand*）等。
    
  • 采用服务模拟器（Algorithm 1）动态更新路网状态，例如随机停用车辆、调整弧段成本或需求。
    

（2）虚拟任务（Virtual Task, VT）策略

• 核心思想：通过虚拟弧将外部车辆“逻辑回库”，转化为静态CARP问题：
  
  1. 为每辆外部车辆构建虚拟任务（VT），连接其当前位置与仓库（图2）；
     
  2. 设置VT的需求为已服务量（确保剩余容量约束），服务成本为仓库到当前位置的最短路径成本，但死驱成本（deadheading cost）设为无限大（防止其他车辆误用）。
     
• 优势：兼容现有静态CARP算法（如MAENS、ILMA），无需修改底层优化逻辑。
  

（3）优化框架（GOfVTS）与策略

• 重启策略（Restart Strategy, RS）：独立优化每个DCARP实例，不依赖历史信息。
  
• 序列转移策略（Sequence Transfer Strategy, STS）：
  
  • 将上一实例最优解中的未服务任务序列保留，贪婪插入新增任务（Algorithm 3），生成新初始解。
    
  • 适用于种群算法（如MAENS），减少随机初始化偏差。
    

（4）实验验证

• 数据集：EGL基准的24个静态CARP实例，生成动态实例（每实例3种剩余容量设置）和动态场景（5个连续实例）。
  
• 对比算法：
  
  • 简单基准：返回优先策略（Return-First, RF，强制外部车辆先返库）；
    
  • 现有动态算法：MASDC（基于距离分割的Memetic算法）；
    
  • 静态算法扩展：VT-MAENS、VT-ILMA、VT-RTS等。
    
• 评估指标：服务总成本（均值和标准差），Wilcoxon检验统计显著性。

4. 主要结果

（1）VT策略的必要性

• RF策略缺陷（表III）：当外部车辆剩余容量充足（>34%容量）时，VT策略显著优于RF（p<0.05）。例如，在EGL-E1实例中，VT策略降低成本约12%。
  
• 原因：RF策略因强制返库导致路径绕行（三角不等式不经济，图3）。
  

（2）VT-MASDC vs. 原始MASDC

• 性能提升（表IV）：VT-MASDC在所有DCARP实例中均显著优于MASDC（p=1.67e-13）。
  
• 归因：VT策略消除MASDC分割方案的随机性，并允许调用高效静态分割算子（如Ulusoy’s split）。
  

（3）GOfVTS框架通用性

• 算法拓展（表V）：静态算法（MAENS、ILMA、RTS）通过GOfVTS适配DCARP后，性能均超越MASDC。
  
  • 最佳组合：VTTF-MAENS（STS策略）在动态场景中排名第一（图6 Nemenyi检验）。
    
  • 策略选择：STS对个体算法（如RTS）提升显著（p=0.01），但对种群算法影响较小（MAENS p=0.93）。
    

5. 结论与价值

• 科学价值：
  
  • 提出首个DCARP数学形式化模型，填补领域空白；
    
  • 通过虚拟任务策略，建立静态与动态CARP的算法桥梁，推动动态优化理论发展。
    
• 应用价值：
  
  • 仿真系统支持真实场景测试（如突发路况下的物流调度）；
    
  • GOfVTS可直接部署现有CARP算法，降低动态场景开发成本。
    

6. 研究亮点

• 创新方法：VT策略通过“逻辑回库”巧妙地统一动静态问题接口，避免复杂算法重构。
  
• 跨领域贡献：首次系统定义了动态事件类型（如道路恢复*为新增事件），扩展了动态优化研究边界。
  
• 工程实用性：开源仿真系统（GitHub）与框架代码，促进学术与工业界应用。
  

7. 其他补充

• 参数鲁棒性：实验验证不同参数配置下（如SMAC调参），GOfVTS优势依然显著（补充材料表VII）。
  
• 未来方向：大规模CARP实例测试、多目标动态优化、全历史信息迁移策略。
  

此报告基于论文内容系统梳理，兼顾学术严谨性与可读性，可供研究人员快速把握核心贡献与方法细节。