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

Wentao Wang; Lifeng Han; Guangyu Zou

cs.LGMar 9, 2026

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

Authors: Wentao Wang, Lifeng Han, Guangyu Zou

Organizations: Leicester International Institute, Dalian University of Technology, Panjin, 124221, Liaoning, China. · Department of Electronic and Information Technology, Dalian University of Technology, Panjin, 124221, Liaoning, China.

Abstract

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 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.

Figures & tables

Figure 1: Illustration of the sequential decision-making process for PDP modeled as an MDP. The process evolves from $t=0$ to $t=2$ , showing the transition of states $s_{t}$ based on selected actions $A_{t}$ (visiting nodes). The dashed orange ovals highlight the spatial cluster structure (pickup and delivery regions) explicitly considered in our framework. The reward $r_{t+1}$ corresponds to the negative distance traveled.

Figure 2: Cluster-Aware Policy Network architecture.

Figure 3: Training convergence on clustered instances.

Figure 4: Training convergence on uniform instances.

Variant	PDP20			PDP50			PDP100
Variant	Greedy	Sample 1280	Sample 12800	Greedy	Sample 1280	Sample 12800	Greedy	Sample 1280	Sample 12800
CAADRL	2.727	2.723	2.723	3.876	3.829	3.824	5.327	5.206	$5.201$
no_encoder	$2.763$	$2.759$	$2.758$	$3.907$	$3.861$	$3.857$	$5.341$	$5.236$	$5.220$
no_decoder	$2.728$	$2.724$	2.723	$3.877$	$3.833$	$3.827$	$5.330$	$5.213$	5.198
POMO	$2.731$	$2.727$	$2.726$	$3.882$	$3.832$	$3.826$	$5.407$	$5.262$	$5.236$

Table 3: Ablation study on clustered PDP instances (lower objective is better).

Method	Decode Strategy	Clustered Instances			Uniform Instances
Method	Decode Strategy	PDP200	PDP300	PDP500	PDP200	PDP300	PDP500
CAADRL	Greedy	$7.578$	9.601	13.205	$16.778$	$21.075$	$28.832$
	Sampling-1280	$7.507$	$9.834$	$14.811$	$15.974$	$21.099$	$31.297$
	Sampling-12800	7.456	$9.754$	$14.653$	15.765	$20.798$	$30.917$
POMO	Greedy	$7.798$	$10.116$	$14.484$	$16.958$	$21.465$	28.787
	Sampling-1280	$7.829$	$10.867$	$17.891$	$16.001$	$20.852$	$30.483$

Table 4: Cross-size generalization comparison on Clustered and Uniform instances (Lower objective is better).

Figure 5: Cross-size generalization of CAADRL under greedy decoding. Solid bars indicate uniform instances and hatched bars indicate clustered instances. Colors denote the training problem size (PDP10/20/40/80). Error bars show the standard deviation over 100 test instances.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 130 papers

Aug 14, 2026

Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

The task of constructing vehicles optimal routes for pickup and delivery of goods is one of most promising tasks in the context of global urban population growth. Although this kind of problems with small size can be solved by various classical approaches, a fast (or realtime) route optimizer under the constraints of the real world (such as capacity and time windows constraints) for medium-large size problems still remains a highly challenging task. In this work we, for the first time, successfully applied a deep Reinforcing Learning approach (modified JAMPR model) to solve Pickup and Delivery problem with Capacity and Time Window constraints (CPDPTW). We obtained a robust model that gives a fast optimal solution for problems of small and medium size, and gives fast suboptimal solution for problems of larger (> 200) size.

Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Moscow State University, Moscow, Russian Federation · Space Research Institute of RAS, Moscow, Russia

Vehicle Routing RL for Combinatorial Optimization Combinatorial Optimization Reinforcement Learning

Ask PDF

Apr 6, 2026

Vehicle-as-Prompt: A Unified Deep Reinforcement Learning Framework for Heterogeneous Fleet Vehicle Routing Problem

Unlike traditional homogeneous routing problems, the Heterogeneous Fleet Vehicle Routing Problem (HFVRP) involves heterogeneous fixed costs, variable travel costs, and capacity constraints, rendering solution quality highly sensitive to vehicle selection. Furthermore, real-world logistics applications often impose additional complex constraints, markedly increasing computational complexity. However, most existing Deep Reinforcement Learning (DRL)-based methods are restricted to homogeneous scenarios, leading to suboptimal performance when applied to HFVRP and its complex variants. To bridge this gap, we investigate HFVRP under complex constraints and develop a unified DRL framework capable of solving the problem across various variant settings. We introduce the Vehicle-as-Prompt (VaP) mechanism, which formulates the problem as a single-stage autoregressive decision process. Building on this, we propose VaP-CSMV, a framework featuring a cross-semantic encoder and a multi-view decoder that effectively addresses various problem variants and captures the complex mapping relationships between vehicle heterogeneity and customer node attributes. Extensive experimental results demonstrate that VaP-CSMV significantly outperforms existing state-of-the-art DRL-based neural solvers and achieves competitive solution quality compared to traditional heuristic solvers, while reducing inference time to mere seconds. Furthermore, the framework exhibits strong zero-shot generalization capabilities on large-scale and previously unseen problem variants, while ablation studies validate the vital contribution of each component.

Shihong Huang, Shengjie Wang, Lei Gao +4

Polytechnic Institute, Zhejiang University, 310015, Hangzhou, China · S.F. Technology Co., Ltd., 518054, Shenzhen, China · School of Management, Zhejiang University, 310058, Hangzhou, China

Vehicle Routing RL for Combinatorial Optimization Neural Combinatorial Optimization Reinforcement Learning

Ask PDF

Aug 14, 2026

JAMPR+/L2D: scalable neural heuristic for constrained vehicle routing problems in dynamic environment

The vehicle routing problems with real-world constraints (we consider vehicles capacity limits, time windows constrains, pickup-and-delivery multi-depo --- CPDPTW) pose significant computational challenges. While classical exact and heuristic methods remain effective to solve problems of small/medium size (

N\lesssim100

), they often lack adaptability and scalability for larger logistics tasks. In this work, we show how JAMPR+/L2D RL deep learning model, proposed in to solve large CPDPTW problems can be adopted in the case of substantial changes of graph distance matrix. We test performance of JAMPR+/L2D model for medium-sized CVRP and VRPTW problems on CVRPLIB benchmarks: JAMPR+/L2D outperforms the state-of-the-art heuristic HGS in over 85% of instances, achieving improvement in objective gap. We show that the JAMPR+/L2D model trained on CPDPTW problem, generalizes well for tasks with simpler constraints (CVRP, VRPTW), for different problem sizes and for moderate changes in distance matrixes. For more substantial changes in distance matrixes, we propose here to make fast finetuning of JAMPR+: on ORTEC data (for CPDPTW) the proposed strategy remarkably reduces the objective gap without full model retraining, what will give both accuracy and rapid inference of the model in the practical routing scenarios with distance matrix changes.

Andrew Soroka, Alex Meshcheryakov

Moscow State University, Moscow, Russian Federation · Space Research Institute of RAS, Moscow, Russia

Vehicle Routing Neural Combinatorial Optimization RL for Combinatorial Optimization

Ask PDF

Abstract

Vehicle Routing

Explore similar work

Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

Vehicle-as-Prompt: A Unified Deep Reinforcement Learning Framework for Heterogeneous Fleet Vehicle Routing Problem

JAMPR+/L2D: scalable neural heuristic for constrained vehicle routing problems in dynamic environment