利用强化学习解决可扩展的多智能体路由问题

《IEEE Transactions on Neural Networks and Learning Systems》：Solving Scalable Multiagent Routing Problems With Reinforcement Learning

多智能体路由问题在物流、运输和应急响应中具有重要应用价值，但传统启发式算法难以处理大规模场景。本文提出RouteMaker方法，通过角色交互的图神经网络（RIGNN）实现位置分配，结合高级规划器优化路径，在无需微调的情况下即可处理40 agents和1000 locations的规模，相比ORTools实现600倍速度提升和88%成本降低。

　　

摘要：

多智能体路由问题源于实际应用，如物流、交通和应急响应等领域，随着问题规模的扩大，搜索空间呈指数级增长，这给问题解决带来了挑战。本文提出了RouteMaker来解决这一常被忽视的多智能体路由问题，该方案特别适用于涉及多个专用仓库的情况。RouteMaker利用基于角色交互的图神经网络（RIGNN）来实现有效的位置分配，并结合先进的规划算法为每个智能体规划出行路径。RouteMaker通过小规模问题的训练，能够产生与最佳启发式算法相当或更优的近似最优解。值得注意的是，该模型无需微调即可无缝扩展到大规模问题和实际场景中，从而在相对较短的时间内提供质量更高的解决方案。在涉及40个智能体和1000个地点的情景中，与传统的经典启发式求解器（ORTools）相比，RouteMaker实现了超过600倍的效率提升和超过88%的成本降低。

引言

多智能体路由问题的目标是为一组智能体找到访问一系列地点的最佳路径，这类问题属于典型的组合优化问题，被归类为NP难问题[1]、[2]、[3]。多智能体路由问题包括多种具体实例，如多旅行商问题（MTSP）[4]、多车辆路由问题（MVRP）[5]、多取货与送货问题（MPDP）[5]等。有效解决这些问题的方法对实际应用具有重要意义，尤其是在物流[8]、交通和应急响应等领域，因为优化的路径能够减少智能体的行驶距离和时间，从而降低运营成本并确保及时交付。