# Graph-Driven Deep Reinforcement Learning for Vehicle Routing Problems with Pickup and Delivery
## 3 Problem Formulation
### Formulation as a MDP  
The route construction of VRP-PD can be inherently framed as a sequential decision-making problem, making it well-suited for formulation within DRL. To this end, we frame the VRP-PD as a tailored MDP \(\mathcal{M}=\{\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R}\}\), where \(\mathcal{S}\) represents the state space, \(\mathcal{A}\) denotes the action space, \(\mathcal{T}\) defines the state transition dynamics, and \(\mathcal{R}\) corresponds to the cumulative reward. The components of this MDP are described as follows. State: At each decision step \(t\), the state \(s_{t}=\{\{v_{i}^{t}\}_{i\in\mathcal{V}},\{u_{k}^{t}\}_{k\in\mathcal{K}}\} \in\mathcal{S}\) encapsulates two key elements. The first component \(v_{i}^{t}=\big{(}p_{i},q_{i}^{t}\big{)}\) comprises the two-dimensional Euclidean coordinate and real-time demand of each customer node \(i\in\mathcal{V}\). The second component \(u_{k}^{t}\) represents the dynamic remaining capacity of vehicle \(k\in\mathcal{K}\) at time \(t\). Initially, the vehicle starts at its full capacity, such that \(u_{k}^{0}=\mathcal{D}\). Action: The action \(a_{t}\in\mathcal{A}\) corresponds to selecting the next customer node to visit at time step \(t\). This decision is governed by the current state \(s_{t}\) and a policy network parameterized by \(\theta\), i.e., \(a_{t}\sim p_{\theta}(a_{t}|s_{t})\). To ensure feasibility, nodes that have already been visited or violate problem constraints are masked from selection. The sequence of selected nodes ultimately forms the complete routing solution for the VRP-PD. Transition: The transition to the next state \(s_{t+1}\) follows the transition rule \(\mathcal{T}\), which updates the system based on the selected action \(a_{t}\) and the current state \(s_{t}\). Once node \(i\) is served by vehicle \(k\) at time \(t\), the real-time demand of node \(i\) is set to 0 (\(q_{i}^{t+1}=0\)), and the vehicle's remaining capacity is updated as \(u_{k}^{t+1}=u_{k}^{t}-q_{i}^{t}\). It is worth noting that the demand \(q_{i}^{t}\) can take either positive or negative values, reflecting whether the node corresponds to a pickup or delivery operation. Reward: The goal of VRP-PD is to minimize the total travel distance. Accordingly, the cumulative reward is defined as the negative of the total traversal length provided by \(\mathcal{R}=-L(\mathcal{A})\). \[L(\mathcal{A})=\left\|p_{\mathbb{T}}-p_{a_{0}}\right\|_{2}+\sum_{t=0}^{\mathbb{ T}-1}\left\|p_{a_{t+1}}-p_{a_{t}}\right\|_{2}, \tag{9}\]  
where \(\mathbb{T}\) is the maximum execution time required to construct a complete route, and \(\|\cdot\|_{2}\) represents the \(\mathcal{L}_{2}\) norm. The immediate reward \(r_{t}\in\mathcal{R}\) at time \(t\) is thus formulated as \(r_{t}=-\left\|p_{a_{t}}-p_{a_{t-1}}\right\|_{2}\), penalizing longer travel distances between consecutive decisions. \begin{table}
\begin{tabular}{c l} \hline \hline
**Parameter** & **Definition** \\ \hline \(\mathcal{G}\) & Whole graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\). \\ \(\mathcal{V}\) & Set of all nodes. \\ \(\mathcal{E}\) & Set of edges. \\ \(\mathcal{L}\) & Set of delivery (linehaul) nodes. \\ \(\mathcal{B}\) & Set of pickup (backhaul) nodes. \\ \(\mathcal{V}^{\prime}\) & Set of all nodes except the depot, i.e., \(\mathcal{V}^{\prime}=(\mathcal{L},\mathcal{B})\). \\ \(\mathcal{K}\) & Set of all vehicles. \\ \(\mathcal{D}\) & Maximum capacity of the vehicle. \\ \(q_{i}\) & Demand of the pickup (delivery) node \(i\). \\ \(d_{ij}^{k}\) & Traveling cost (length) for vehicle \(k\) to depart from node \(i\) to node \(j\). \\ \(u_{ij}^{k}\) & Remaining capacity of vehicle \(k\) when traveling from node \(i\) to node \(j\). \\ \(\varepsilon_{ij}^{k}\) & Binary decision variable representing whether the vehicle \(k\) travels from node \(i\) to node \(j\). \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The definition of parameters and decision variables in the VRP-PD model.