Graph-Driven Deep Reinforcement Learning for Vehicle Routing Problems with Pickup and Delivery
Dapeng Yan, Qingshu Guan, Bei Ou, Bowen Yan, Hui Cao
Abstract
Recently, the vehicle routing problem with pickup and delivery (VRP-PD) has attracted increasing interest due to its widespread applications in real-life logistics and transportation. However, existing learning-based methods often fail to fully exploit hierarchical graph structures, leading to suboptimal performance. In this study, we propose a graph-driven deep reinforcement learning (GDRL) approach that employs an encoder–decoder framework to address this shortcoming. The encoder incorporates stacked graph convolution modules (GCMs) to aggregate neighborhood information via updated edge features, producing enriched node representations for subsequent decision-making. The single-head attention decoder then applies a computationally efficient compatibility layer to sequentially determine the next node to visit. Extensive experiments demonstrate that the proposed GDRL achieves superior performance over both heuristic and learning-based baselines, reducing route length by up to 5.81% across synthetic and real-world datasets. Furthermore, GDRL also exhibits strong generalization capability across diverse problem scales and node distributions, highlighting its potential for real-world deployment.