# Graph-Driven Deep Reinforcement Learning for Vehicle Routing Problems with Pickup and Delivery
## 4 Methodology
### Encoder  
Traditional DRL-based methods primarily rely on node features to generate high-dimensional embeddings but fail to fully exploit the hierarchical structure of graph-based representations. As a result, these approaches often lead to suboptimal routing solutions. To mitigate this limitation, the proposed encoder, as shown in Figure 1, incorporates a graph convolution module (GCM) that integrates both node and edge features, capturing interdependencies between pickup and delivery locations as well as local and global structural relationships within the problem space.  
Moreover, computing pairwise connections among all nodes is computationally prohibitive, particularly for large-scale instances. To address this challenge, we construct a sparse k-nearest neighbor (KNN) graph that enables efficient edge-based message passing. Specifically, each node \(i\) exchanges edge features exclusively with its k nearest neighbor \(\mathbb{N}(i)\) in Euclidean space. This design preserves critical structural information while ensuring efficient information propagation across different problem scales.  
\[k=\mu_{k}N, \tag{11}\]  
where \(\mu_{k}\in(0,1)\) is a ratio which controls the scope of KNN.  
The raw node features \(v_{i}\) and edge features \(d_{ij}\) are firstly embedded into \(d_{g}\)-dimensional tokens via a linear projection as follows:  
\[g_{i}^{(0)}=v_{i}W_{g}^{(0)}+b_{g}^{(0)},\ \forall i\in\mathcal{V}, \tag{12}\]  
\[z_{ij}^{(0)}=d_{ij}W_{z}^{(0)}+b_{z}^{(0)},\ \forall i\in\mathcal{V},\ j\in \mathbb{N}(i), \tag{13}\]  
Figure 1: The encoding procedure of the proposed GDRL.  
where \(W_{g}^{(0)}\in\mathbb{R}^{2\times d_{g}}\) and \(W_{z}^{(0)},b_{g}^{(0)},b_{z}^{(0)}\in\mathbb{R}^{1\times d_{g}}\) are learnable parameter matrices. The initial node tokens \(g_{i}^{(0)}\) and edge tokens \(z_{ij}^{(0)}\) are processed through the GCM with \(L\) layers, where hierarchical feature extraction is performed. For each layer \(l\in\{1,\cdots,L\}\), the GCM operates as a message-passing mechanism, propagating information between neighboring nodes based on edge features defined in the KNN graph.  
\[g_{i}^{(l)}=g_{i}^{(l-1)}+\text{ReLU}\left(\text{BN}\left(g_{i}^{(l-1)}W_{g}^{ (l-1)}+\sum_{j\in\mathbb{N}(i)}\psi_{ij}^{(l-1)}\odot g_{j}^{(l-1)}W_{g^{ \prime}}^{(l-1)}\right)\right), \tag{14}\]  
\[\psi_{ij}^{(l)}=\frac{\text{Sigmoid}\left(z_{ij}^{(l-1)}\right)}{\text{Sigmoid }\left(\sum_{j\in\mathbb{N}(i)}z_{ij}^{(l-1)}\right)}, \tag{15}\]  
\[z_{ij}^{(l)}=z_{ij}^{(l-1)}+\text{ReLU}\left(\text{BN}\left(z_{ij}^{(l-1)}W_{ z}^{(l-1)}+g_{i}^{(l-1)}W_{z^{\prime}}^{(l-1)}+g_{j}^{(l-1)}W_{z^{\prime\prime}}^{ (l-1)}\right)\right),\;j\in\mathbb{N}(i), \tag{16}\]  
where \(W_{g}^{(l-1)},W_{g^{\prime}}^{(l-1)},W_{z}^{(l-1)},W_{z^{\prime}}^{(l-1)},W_{ z^{\prime\prime}}^{(l)}\in\mathbb{R}^{d_{g}\times d_{g}}\) are trainable weight matrices, and \(\psi_{ij}^{(l)}\) denotes the relative connection coefficient between two neighboring nodes. Nonlinear activation and normalization are applied through the rectified linear unit (\(\text{ReLU}(\cdot)\)), batch normalization (\(\text{BN}(\cdot)\)), and the sigmoid function (\(\text{Sigmoid}(\cdot)\)) to enhance learning stability.  
In each layer \(l\), the node token \(g_{i}^{(l)}\) is updated by aggregating information from its previous token \(g_{i}^{(l-1)}\) and edge tokens \(\{z_{ij}^{(l-1)}\}_{j\in\mathbb{N}(i)}\) associated with its k-nearest neighbors. Simultaneously, the edge token \(z_{ij}^{(l)}\) is refined by incorporating information from its prior state \(z_{ij}^{(l-1)}\) along with node tokens \(g_{i}^{(l-1)}\) and \(g_{j}^{(l-1)}\). After \(L\) layers, the final output of the encoder is obtained, where the global graph representation \(g_{\text{graph}}\) is computed as the mean of all node embeddings \(\{g_{i}^{(L)}\}\), encapsulating the overall structural information of the problem instance.  
\[g_{\text{graph}}=\sum_{i\in\mathcal{V}}\frac{1}{1+N}g_{i}^{(L)}. \tag{17}\]