# Reinforcement Learning for Efficient Drone-Assisted Vehicle Routing
## 3 The Problem Formulation
### MDP Formulation of the VRPD  
Given the deterministic nature of the VRPD and the common goal of all vehicles to serve customers in minimal time, we assume that a central controller observes the entire graph and makes routing decisions for all vehicles. This problem is formalized as an MDP with discrete steps. An MDP is represented by the tuple \(\mathcal{M}=\langle\mathbf{s},\mathbf{a},P,R,T\rangle\), where \(\mathbf{s}\) denotes states, \(\mathbf{a}\) denotes actions, \(P\) denotes transition probabilities, \(R\) denotes the reward function, and \(T\) denotes the time horizon, with the details outlined below. Given the set of trucks \(\mathcal{K}\) and drones \(\mathcal{D}\), the state of the MDP for the VRPD is represented by the vector \(\mathbf{s}_{t}:=(\mathcal{V}_{t},\mathbf{c}_{t}^{tr},\mathbf{c}_{t}^{tr}, \mathbf{r}_{t}^{tr},\mathbf{r}_{t}^{tr},\mathbf{c}_{t}^{tr})\). The customers already served up to time step \(t\) must be kept track of, denoted as \(\mathcal{V}_{t}\subseteq\mathcal{N}\). The current destination node of truck \(k\) and its drone \(d\) is denoted by \(c_{t}^{k}\) and \(c_{t}^{k,d}\), respectively. However, at any time step \(t\), not all vehicles may arrive at their destination nodes. If a truck (or a drone) is still traversing between two nodes at step \(t\), then \(c_{t}^{k}\) (or \(c_{t}^{k,d}\)) is set as the destination node of the vehicle. If a truck (or a drone) arrives at a node at time step \(t\), then \(c_{t}^{k}\) (or \(c_{t}^{k,d}\)) is set as the node index. Consequently, vectors \(\mathbf{c}_{t}^{tr}:=(c_{t}^{k},\forall k\in\mathcal{K})\) and \(\mathbf{c}_{t}^{tr}:=(c_{t}^{k,d},\forall k\in\mathcal{K},\forall d\in\mathcal{D})\) can be constructed. The remaining times to arrive at destinations \(c_{t}^{k}\) and \(c_{t}^{k,d}\) of truck \(k\) and its drone \(d\) are denoted as \(r_{t}^{k}\) and \(r_{t}^{k,d}\), respectively. When a truck (or a drone) is not in transit, \(r_{t}^{k}=0\) (or \(r_{t}^{k,d}=0\)). \(\mathbf{t}_{t}^{tr}\) is defined as \((r_{t}^{k},\forall k\in\mathcal{K})\) and \(\mathbf{t}_{t}^{tr}\) is defined as \((r_{t}^{k,d},\forall k\in\mathcal{K},\forall d\in\mathcal{D})\). Let vectors \(\mathbf{e}_{t}^{tr}:=(c_{t}^{k,d},\forall k\in\mathcal{K},\forall d\in \mathcal{D})\), and \(\mathbf{t}_{t}^{tr}:=(l_{t}^{k,d},\forall k\in\mathcal{K},\forall d\in \mathcal{D})\) represent the remaining battery and load of drones at step \(t\), and let \(\varepsilon_{max}\) be the maximum battery level for drones. At \(t=0\), since all vehicles are located at the depot, we have \(\mathcal{V}_{0}=\{N\}\), \(c_{0}^{k}=N\), \(c_{0}^{k,d}=N\), \(r_{0}^{k}=0\), \(r_{0}^{k,d}=0\), \(c_{0}^{k,d}=\varepsilon_{max}\), \(r_{0}^{k,d}=1\) for all \(k\in\mathcal{K}\) and \(d\in\mathcal{D}\). At each step, the central controller must decide on the next destinations of the trucks, \(\mathbf{a}_{t}^{tr}:=(a_{t}^{k}\in\mathcal{N},\forall k\in\mathcal{K})\), and drones \(\mathbf{a}_{t}^{dr}:=(a_{t}^{k,d}\in\mathcal{N},\forall k\in\mathcal{K},\forall d \in\mathcal{D})\). When the previously assigned node has not been reached by a drone \(d\) of truck \(k\) yet, i.e., \(r_{t}^{k,d}>0\), we set \(a_{t}^{k,d}=c_{t}^{k,d}\). Analogously, \(a_{t}^{k}=c_{t}^{k}\) if truck \(k\) is in transit. For convenience, \(\mathbf{a}_{t}:=(\mathbf{a}_{t}^{tr},\mathbf{a}_{t}^{dr})\) is referred to as the action at step \(t\). Due to the deterministic nature of the problem, the state transition probabilities are also deterministic. We revise the remaining times for each vehicle after its action has been determined and denote them as \(\hat{r}_{t}^{k}=r_{t}^{k}+\tau_{c_{t}^{k,d}}^{tr}\) and \(\hat{r}_{t}^{k,d}=r_{t}^{k,d}+\tau_{c_{t}^{k,d},\hat{r}_{t}^{k,d}}^{tr}\) for truck \(k\) and drone \((k,d)\) respectively. Note that \(\tau_{i,j}^{tr}=0\) and \(\tau_{i,j}^{dr}=0\) for any \(i\in\mathcal{N}\). The time step is evolved when at least one vehicle arrives at its assigned node.