# Graph-Driven Deep Reinforcement Learning for Vehicle Routing Problems with Pickup and Delivery
## 1 Introduction  
The vehicle routing problem with pickup and delivery (VRP-PD) [1] is a fundamental subfield of combinatorial optimization problems (COPs) [2] with far-reaching implications in computer science [3] and operational research [4], as well as extensive real-world applications in logistics [5], robotics [6], transportation [7], and so forth. Unlike traditional VRP variants such as the traveling salesman problem (TSP) [8] and capacitated VRP (CVRP) [9], VRP-PD requires determining optimal routes that fulfill both pickup and delivery requests while adhering to several constraints: (1) each customer node is visited exactly once; (2) each vehicle begins and ends its route at a designated depot; (3) customer demands must be fully met without exceeding vehicle capacity; (4) each pickup operation must precede its corresponding delivery. These problem-specific constraints introduce unique challenges and complexities to optimization. In recent decades, a wide array of exact and heuristic methods has been developed to address routing problems, including the VRP-PD. Exact algorithms, including branch-and-cut [10] and its variants, provide theoretical guarantees of optimality but face prohibitive computational complexity, making them impractical for large-scale instances. In contrast,heuristic approaches, such as local neighbor search [11], ant colony optimization [12], and simulated annealing [13], offer a more computationally efficient alternative by leveraging manually crafted rules to guide the search process. While these methods achieve a balance between solution quality and execution speed, their reliance on problem-specific knowledge and expert knowledge limits their adaptability, often leading to suboptimal performance in complex and dynamic real-world routing scenarios. Deep neural networks and reinforcement learning have made remarkable strides in solving complex tasks, benefiting from the parallel computing capabilities of graphics processing units (GPUs) [14; 15]. Recently, deep reinforcement learning (DRL) has gained traction as a promising approach for solving various VRPs [16; 17]. By extracting patterns from large-scale data and autonomously learning decision rules during route construction, DRL-based methods have demonstrated strong performance across different routing problem variants. However, in our view, there are still several limitations to constructive DRL-based routing methods. On the one hand, prevalent methods predominantly rely on node-level features for representation learning, failing to fully exploit hierarchical graph structures, which limits routing performance. On the other hand, widely adopted decoding strategies incur substantial computational costs and lack adaptability for real-time decision-making, posing significant challenges in scaling to large problem instances. Overall, addressing these limitations is critical for further advancing DRL-based methods in combinatorial optimization. To address these challenges, we formulate the VRP-PD as a Markov decision process (MDP) and introduce a graph-driven deep reinforcement learning (GDRL) framework for route optimization. The proposed approach follows an encoder-decoder architecture, where the encoder constructs a k-nearest neighbor (KNN) graph to represent spatial relationships among nodes. Stacked graph convolution modules (GCMs) are then employed to extract hierarchical graph features, generating informative representations for both nodes and edges. The relative connection weight between adjacent nodes is derived from edge features, which are computed based on node embeddings via GCMs. In the decoding phase, a computationally efficient compatibility layer with a single-head attention mechanism produces a probability distribution for node selection at each decision step, iteratively constructing a complete route. The entire network is optimized using an enhanced reinforcement learning algorithm, ensuring improved training stability and performance.