arXiv:2603.10053cs.LG2026-03

提出一种显式建模聚类结构的强化学习方法,显著提升路径规划效率。

Cluster-Aware Attention-Based Deep Reinforcement Learning for Pickup and Delivery Problems

  • 通过聚类感知编码与分层解码,显式利用问题的多尺度结构
  • 在聚类实例上性能超越或媲美顶尖方法,且推理速度更快
  • 适合大规模路径规划任务,尤其适用于具有明显聚类特征的问题

取送问题(PDP)是车辆路径问题的一个基础而复杂的变体,其特点为紧密耦合的取送对、先后顺序约束以及常呈现聚类的空间布局。现有深度强化学习(DRL)方法要么将所有节点平铺建模,依赖隐式学习来满足约束;要么通过推理时的协同搜索获得高性能,但代价是显著的延迟。本文提出CAADRL(聚类感知注意力深度强化学习),一种通过聚类感知编码和分层解码显式利用PDP实例多尺度结构的DRL框架。编码器基于Transformer,结合全局自注意力与卸货点、取货点及配送点之间的簇内注意力,生成兼具全局信息与局部角色感知的嵌入表示。基于这些嵌入,我们引入带有可学习门控的动态双解码器,在每一步平衡簇内路径与簇间转移。策略通过每个实例多次对称采样的POMO风格策略梯度端到端训练。在合成的聚类与均匀分布的PDP基准测试中,CAADRL在聚类实例上达到或超过当前最优基线性能,且在问题规模增大时仍保持高竞争力。关键的是,该方法相比神经协同搜索基线显著降低推理时间,表明显式建模聚类结构为神经PDP求解器提供了有效且高效的归纳偏置。

原文摘要 · Abstract (English)

The Pickup and Delivery Problem (PDP) is a fundamental and challenging variant of the Vehicle Routing Problem, characterized by tightly coupled pickup--delivery pairs, precedence constraints, and spatial layouts that often exhibit clustering. Existing deep reinforcement learning (DRL) approaches either model all nodes on a flat graph, relying on implicit learning to enforce constraints, or achieve strong performance through inference-time collaborative search at the cost of substantial latency. In this paper, we propose \emph{CAADRL} (Cluster-Aware Attention-based Deep Reinforcement Learning), a DRL framework that explicitly exploits the multi-scale structure of PDP instances via cluster-aware encoding and hierarchical decoding. The encoder builds on a Transformer and combines global self-attention with intra-cluster attention over depot, pickup, and delivery nodes, producing embeddings that are both globally informative and locally role-aware. Based on these embeddings, we introduce a Dynamic Dual-Decoder with a learnable gate that balances intra-cluster routing and inter-cluster transitions at each step. The policy is trained end-to-end with a POMO-style policy gradient scheme using multiple symmetric rollouts per instance. Experiments on synthetic clustered and uniform PDP benchmarks show that CAADRL matches or improves upon strong state-of-the-art baselines on clustered instances and remains highly competitive on uniform instances, particularly as problem size increases. Crucially, our method achieves these results with substantially lower inference time than neural collaborative-search baselines, suggesting that explicitly modeling cluster structure provides an effective and efficient inductive bias for neural PDP solvers.

强化学习路径规划聚类建模DRL

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。