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

A team of researchers has introduced CAADRL (Cluster-Aware Attention-based Deep Reinforcement Learning), a novel deep reinforcement learning framework designed to tackle the computationally intense Pickup and Delivery Problem (PDP). Unlike previous approaches that treat all delivery nodes on a flat graph or rely on slow, inference-time collaborative searches, CAADRL explicitly exploits the inherent multi-scale, clustered structure of real-world logistics. Its core innovation is a Transformer-based encoder that performs both global self-attention and focused intra-cluster attention on depot, pickup, and delivery nodes. This creates embeddings that are globally informed yet locally aware of each node's specific role, providing a powerful inductive bias for the solver.

Building on these embeddings, the model employs a Dynamic Dual-Decoder with a learnable gate mechanism. This gate dynamically balances decisions at each step between routing within a cluster and transitioning between clusters, mimicking an efficient human dispatcher's thought process. Trained end-to-end with a POMO-style policy gradient using multiple symmetric rollouts, CAADRL was tested on synthetic clustered and uniform PDP benchmarks. The results show it matches or improves upon strong state-of-the-art baselines on clustered instances and remains highly competitive on uniform layouts, especially as problem size scales. Crucially, it achieves this high performance with "substantially lower inference time" than previous neural collaborative-search methods, offering a better balance of speed and accuracy for practical deployment.