区域聚焦文化基因算法（Region-Focused Memetic Algorithms）在大型现实废弃物收运问题中的应用研究

作者及机构
本文由Wenxing Lan、Ziyuan Ye、Peijun Ruan、Jialin Liu（IEEE Senior Member）、Peng Yang（IEEE Member）和Xin Yao（IEEE Fellow）共同完成，作者团队来自中国南方科技大学计算机科学与工程系及广东省脑启发智能计算重点实验室。研究成果发表于2022年8月的IEEE Transactions on Evolutionary Computation（第26卷第4期），论文标题为《Region-Focused Memetic Algorithms with Smart Initialization for Real-World Large-Scale Waste Collection Problems》。

学术背景

本研究属于进化计算（Evolutionary Computation）与运筹学（Operations Research）的交叉领域，聚焦于多车场多处理设施多行程的带容量约束车辆路径问题（Multidepot Multidisposal-Facility Multitrip CVRP, M3CVRP）的实际应用。

研究动机：
现有废弃物收运问题（Waste Collection Problem, WCP）的研究多基于单车场（Single-Depot）或单处理设施假设，而现实场景中车辆需从多个车场出发，访问多个废弃物处理设施（如中转站），且受容量和工作时长约束。这种复杂性导致传统算法（如经典文化基因算法MA或Clarke-Wright节约算法CWSA）无法直接适用。此外，现有研究多采用欧氏距离对称假设，而实际道路存在单向行驶导致的非对称性。本文首次系统建模了包含3000个收集点、3个车场和3个处理设施的大型现实问题。

目标：
1. 建立M3CVRP的数学模型；
2. 设计高效的区域聚焦文化基因算法（RFMA）解决搜索空间爆炸问题；
3. 提出启发式辅助的初始化方法（HASI）和逆向插入解码器（BSIM）；
4. 验证算法在真实大规模实例上的优越性。

研究方法与流程

1. 问题建模

M3CVRP模型的核心约束：
- C1：车辆需从同一车场出发并返回；
- C2：每个收集点仅被服务一次；
- C3：车辆载重不得超过容量；
- C4：单日工作时间不超过8小时；
- C5：离开车场或处理设施时车辆必须空载；
- C6：返回车场前需清空负载。

数学模型通过有向图表示顶点（车场、收集点、处理设施）和边（实际驾驶距离），目标函数是最小化总行驶距离（公式3）。

2. 算法设计

研究采用两阶段框架：

（1）智能初始化阶段（HASI算法）

关键创新：
- 紧致化策略：通过参数θ_c和θ_t动态限制车辆容量和工作时间的90%~99%，增强解多样性。
- 最近服务优先：将收集点分配至最近车场，按“最近未服务点优先”原则生成初始路径。

数据预处理：
- 基于高德地图API计算非对称实际驾驶距离（非欧氏距离）；
- 收集点服务时间δ©和废弃物体积t©作为输入约束。

（2）优化阶段（RFMA算法）

核心组件：
- 区域聚焦局部搜索（RFLS）：
- RFSPS算子：在半径ρ₁内交换单点（图4示例）；
- RFSS算子：在半径ρ₂内交换路径片段；
- RMPS算子：随机交换多点并松弛接受条件（ρ₃控制松弛度）。
- 逆向插入解码器（BSIM）：非贪婪插入处理设施和车场，回溯m个点评估最优插入位置（参数n_b=5）。

MA框架改进：
- 结合序列交叉（SBX）和随机排序（Stochastic Ranking）处理约束；
- 局部搜索概率p_ls=0.2，种群规模μ=30。

实验结果与发现

1. 初始化方法对比

• 基准算法：CWSA-I、CWSA-II（传统节约算法改进版）、MAC-Init（基于文献22的初始化方法）。
  
• HASI优势：
  
  • 在90辆车配置下，HASI生成解的总距离（6373.4–6664.8 km）仅为CWSA的1/3（表III）；
    
  • 运行时间秒，显著快于CWSA（需数小时）；
    
  • 解多样性熵值达421.1（公式9），参数θ_c=0.04时效果最优（图6a）。
    

2. 优化算法性能

• RFLS vs RFMA：
  
  • RFLS在短时优化（小时）中更优（图7a），平均距离较MA降低12.3%；
    
  • RFMA在高多样性初始种群下长期优化效果更佳（表VI）。
    
• 对比基准：
  
  • 优于MAC算法（p<0.01），总距离减少19.7%；
    
  • CPLEX在70个点的子问题上已无法50小时内求解，证实大规模问题的计算复杂性。
    

3. 算子贡献分析

• RFSPS：稳定提升解质量（降低标准差至15.8 km）；
  
• RFSS：扩大搜索邻域但易陷入局部最优（表VIII）；
  
• RMPS：通过松弛条件ρ₃跳出局部最优（图7c）。
  

研究价值与创新点

科学价值

1. 首个M3CVRP建模：统一多车场、多设施、多行程和时间约束，填补了CVRP研究空白；
   
2. 区域聚焦理论：通过空间相关性缩小搜索空间，为大规模组合优化提供新思路；
   
3. 紧致化策略：动态调整约束阈值的方法可推广至其他带约束优化问题。
   

应用价值

1. 实际部署：算法已在深圳某废弃物管理公司应用，日均减少行驶里程23%；
   
2. 扩展性：支持非对称距离和实时交通数据集成，适用于物流、快递等领域。
   

创新亮点

1. 混合初始化：HASI结合启发式分配与紧致化策略，平衡质量和多样性；
   
2. 非贪婪解码：BSIM通过逆向插入降低局部最优风险；
   
3. 计算效率：在3000节点规模下实现分钟级优化，远超CPLEX的可行性极限。
   

未来方向

作者建议进一步研究动态环境下的鲁棒优化（如交通不确定性[36]），并探索基于深度学习的算子自适应选择机制。