# Reinforcement Learning for Efficient Drone-Assisted Vehicle Routing
## 4 Solution Methods
### The Deep Learning Model  
To route multiple drones and trucks for the last mile delivery, the stochastic policy \(\pi_{\theta}\) with parameters \(\theta\) needs to be learned, defined as a product of conditional probabilities. \[\pi_{\theta}(\mathbf{a}_{1},\mathbf{a}_{2},\dots,\mathbf{a}_{T}|\mathcal{G}) =\prod_{t=1}^{T}p_{\theta}(\mathbf{a}_{t}|\mathbf{s}_{t}). \tag{5}\]  
As demonstrated in the literature [10, 23, 30], a routing policy for a single vehicle can be learned through encoder-decoder-based deep learning models. The encoder is an information extractor from a graph, encoding its structure and the problem settings. The decoder aims to learn the policy \(\pi_{\theta}\) directly using the embeddings from the encoder. Furthermore, ref. [13] has demonstrated the HM's effectiveness, consisting of an attention-based encoder and an LSTM-based decoder, in routing a single drone and truck. However, the structure of the above model does not consider the interactions between groups when routing multiple drones and trucks, where a truck with its set of drones can be viewed as a group. Within a group, the model must consider coordinating actions taken by a truck and several drones to launch and retrieve them efficiently. On the other hand, one group's decisions affect another group's decisions since drones can be launched and retrieved only by their assigned trucks. To serve all customers effectively with a diverse set of locationsin minimal time, the model must consider the selected actions of the first group to make decisions about routing the second group. The HM presented in [13] is modified by adjusting inputs to the decoder, allowing for the efficient incorporation of coordination within a group and interactions between groups within a shared graph. This model is referred to as the attention-encoder group-based LSTM-decoder. Figure 1 gives an overview of the model. **ENCODER. ** A multi-head attention-based encoder is deployed, which has been shown to be effective in embedding graphs for routing problems [10; 25]. In the context of a given graph \(\mathcal{G}\) with nodes in \(\mathcal{N}\) and corresponding coordinates denoted as \(y_{n}=(y_{n}^{1},y_{n}^{2})\in R^{2}\) for each node \(n\in\mathcal{N}\), the process of embedding a fully connected graph begins with an initial transformation of node embeddings. The initial embeddings, represented as \(h_{n}^{0}=W^{0}y_{n}+b^{0}\) for all \(n\in\mathcal{N}\), involve learnable parameters \(W_{0}\) and \(b_{0}\). These initial node embeddings \(h_{n}^{0}:n\in\mathcal{N}\) undergo \(L\) attention layers, where each layer, denoted as \(l\), comprises two sublayers: a multi-head attention (MHA) layer and a fully connected feed-forward (FF) layer. The MHA layer takes input from the previous layer and facilitates message passing between nodes. For each input to the MHA layer, queries \(\mathbf{q}\), keys \(\mathbf{k}\), and values \(\mathbf{v}\) are computed by projecting the input \(\mathbf{h}_{n}\) using trainable parameters \(\mathbf{W}_{Q},\mathbf{W}_{K}\), and \(\mathbf{W}_{V}\). Compatibility between nodes \(i\) and \(j\) is determined based on the fully connected graph structure, expressed as \(u_{i,j}=\sqrt{dim}\), where \(dim\) represents the parameter size. The compatibility values \(u_{i,j}\) are then used to compute attention weights, \(a_{i,j}\in[0,1]\), using the softmax function. Messages received by node \(n\) are formed as convex combinations of messages from all nodes. An MHA layer with head size \(M\) is employed to enhance the attention mechanism's expressive power. Messages from each head are computed and combined for each node \(n\). The output of the MHA sublayer, along with skip connections, undergoes batch normalization. The resulting batch-normalized output is processed through a fully connected FF network with the ReLU activation function. Skip connections and batch normalization are applied again to the output of the FF layer, resulting in the final representation denoted as \(\mathbf{h}^{I}\) after \(l\) attention layers. **DECODER.