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

多智能体强化学习框架在路径规划与调度问题中的应用研究

一、作者与发表信息

本研究由Maria Amélia Lopes Silva（巴西米纳斯吉拉斯联邦技术教育中心）、Sérgio Ricardo de Souza（同机构）、Marcone Jamilson Freitas Souza（欧鲁普雷图联邦大学计算机系）及Ana Lúcia C. Bazzan（南里奥格兰德联邦大学信息研究所）合作完成，发表于2019年《Expert Systems with Applications》第131卷（148–171页）。

二、学术背景

科学领域：本研究属于组合优化与多智能体系统（Multi-Agent Systems, MAS）的交叉领域，结合了强化学习（Reinforcement Learning, RL）和元启发式算法（Metaheuristics）。

研究动机：
1. 问题需求：车辆路径问题（VRPTW）和并行机调度问题（UPMSp-ST）是经典的NP难问题，传统数学规划方法在有限计算时间内难以求解。
2. 方法局限：现有元启发式框架（如OptFrame、Jmetal）缺乏自适应能力，且多智能体协作机制未充分利用强化学习的动态决策优势。
3. 创新目标：提出自适应多智能体元启发式框架（AMAM），通过强化学习（Q-learning算法）使智能体动态调整搜索策略，提升解的质量与协作效率。

三、研究流程与方法

1. 框架设计（AMAM架构）

• 核心组件：

  • 环境（Environment）：问题搜索空间，存储问题实例数据（如客户坐标、时间窗、机器处理时间等）。
    
  • 智能体（Agents）：每个智能体封装一个迭代局部搜索（Iterated Local Search, ILS）算法，独立探索解空间。
    
  • 解池（Solution Pool）：共享存储空间，通过niching技术（基于解的距离函数）维护解的多样性。
    

• 协作机制：智能体通过解池交换信息，合作策略包括：

  • 解插入规则：新解需优于池中最差解且不重复。
    
  • 距离函数：计算解间差异（如VRPTW中非共享路径弧的数量）。
    

2. 自适应局部搜索（ALS-Qlearning）

• 状态与动作定义：
  
  • 状态（States）：邻域函数（如VRPTW的8种邻域操作，包括路径内交换、跨路径移位等）。
    
  • 动作（Actions）：状态间的转移（如从“路径内交换”切换到“跨路径移位”）。
    
• Q-learning流程：
  
  1. 初始化Q表：所有状态-动作对的初始值为0。
     
  2. 探索与利用：采用ε-greedy策略选择动作（ε=0.05，衰减率0.999）。
     
  3. 奖励设计：基于目标函数改进值（如VRPTW中减少的车辆数或距离）。
     
  4. 更新规则：按Bellman方程更新Q值，学习率α=0.1，折扣因子γ=0.9。
     

3. 实验验证

• 测试问题：
  
  • VRPTW：56个Solomon基准实例（C1/C2/R1/R2/RC1/RC2类）。
    
  • UPMSp-ST：24个Vallada & Ruiz实例（50/100个任务，10–25台机器）。
    
• 对比方案：
  
  • ALS-LA（基于学习自动体的旧版框架） vs. ALS-Qlearning（新版）。
    
  • 四种智能体规模（1/2/4/8个智能体）的协作效果。
    
• 评估指标：
  
  • VRPTW：车辆数（首要）和总距离（次要）。
    
  • UPMSp-ST：最大完工时间（Makespan）。
    

四、主要结果

1. 协作有效性：

   • VRPTW：89.28%的实例中，多智能体（≥2）显著优于单智能体（p<0.05）。例如，R201实例中，8智能体的平均距离比单智能体降低12.7%。
     
   • UPMSp-ST：100%的实例显示多智能体协作提升解质量（如i_50_10_s_1-9_1实例的Makespan降低18.3%）。
     

2. 学习算法优势：

   • ALS-Qlearning在44个VRPTW实例中，90.9%的案例优于ALS-LA（如R111实例车辆数减少1辆）。
     
   • Q-learning的适应性：智能体通过奖励机制快速识别高效邻域序列（如VRPTW中“跨路径移位→消除最小路径”的组合收益最高）。
     

3. 可扩展性：智能体数量增加（1→8）持续改善解质量，验证框架的并行潜力。

五、结论与价值

1. 科学价值：

   • 首次将Q-learning嵌入多智能体框架，实现邻域操作的动态选择，克服了传统元启发式固定邻域顺序的局限。
     
   • 提出解池的niching评估函数（公式2–3），有效平衡解的质量与多样性。
     

2. 应用价值：

   • 为物流（VRPTW）和制造（UPMSp-ST）提供高效求解工具，代码已开源（GitHub，LGPLv3协议）。
     
   • 框架支持灵活扩展，可适配其他组合优化问题。
     

六、研究亮点

1. 方法创新：

   • 结合MAS与RL的双层学习机制（个体智能体学习+群体协作）。
     
   • 自适应解池管理：通过距离阈值（pool radius, pr）控制解分布。
     

2. 实验设计：

   • 跨问题验证（VRPTW与UPMSp-ST），证明框架的通用性。
     
   • 统计检验（ANOVA）确保结果显著性。
     

七、其他贡献

• 开源实现：AMAM框架提供Java实现，支持自定义问题与算法嵌入。
  
• 未来方向：探索深度强化学习（如DQN）进一步优化智能体决策。
  

此报告系统梳理了研究的创新性、方法细节及实证结果，可为相关领域学者提供技术参考与应用启示。