提出CAMP模型解决带客户偏好的车辆路径优化问题,实现高效协同决策。
CAMP: Collaborative Attention Model with Profiles for Vehicle Routing Problems
- 基于多智能体强化学习与注意力机制,同步处理不同车辆的客户偏好嵌入
- 在两类PVRP变体上表现优于传统神经多智能体模型,解质量与效率俱佳
- 适用于有个性化约束或区域限制的物流配送场景,适合实际应用部署
带配置的车辆路径问题(PVRP)是异构容量车辆路径问题(HCVRP)的推广,其目标是在考虑各车辆配置偏好或约束的前提下,优化服务客户需求的路径。现有学习方法虽能在实时求解HCVRP方面取得进展,但尚无针对更实用且更具挑战性的PVRP的学习解法。本文提出协作注意力模型(CAMP),一种利用多智能体强化学习求解PVRP的新方法。CAMP采用专用注意力编码器架构,对每种车辆配置并行嵌入带配置的客户信息。设计智能体间的通信层,实现在每个解码步骤中跨配置嵌入的协同决策,并引入批处理指针机制以评估下一步动作的可能性。我们在两种PVRP变体上进行评估:带偏好影响奖励函数的PVRP,以及具有不同数量智能体和客户的区域约束型PVRP。实验表明,所学求解器在解质量与计算效率方面均达到与经典先进神经多智能体模型相当甚至更优的表现。代码已开源至https://github.com/ai4co/camp。
原文摘要 · Abstract (English)
The profiled vehicle routing problem (PVRP) is a generalization of the heterogeneous capacitated vehicle routing problem (HCVRP) in which the objective is to optimize the routes of vehicles to serve client demands subject to different vehicle profiles, with each having a preference or constraint on a per-client basis. While existing learning methods have shown promise for solving the HCVRP in real-time, no learning method exists to solve the more practical and challenging PVRP. In this paper, we propose a Collaborative Attention Model with Profiles (CAMP), a novel approach that learns efficient solvers for PVRP using multi-agent reinforcement learning. CAMP employs a specialized attention-based encoder architecture to embed profiled client embeddings in parallel for each vehicle profile. We design a communication layer between agents for collaborative decision-making across profiled embeddings at each decoding step and a batched pointer mechanism to attend to the profiled embeddings to evaluate the likelihood of the next actions. We evaluate CAMP on two variants of PVRPs: PVRP with preferences, which explicitly influence the reward function, and PVRP with zone constraints with different numbers of agents and clients, demonstrating that our learned solvers achieve competitive results compared to both classical state-of-the-art neural multi-agent models in terms of solution quality and computational efficiency. We make our code openly available at https://github.com/ai4co/camp.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。