# Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems
## 3 Methodology
### Encoder  
Our encoder model takes a graph \(G=(V,E,W)\) as input. Taking TSP as an example, the initial node features can be given as two-dimensional coordinates \(x_{i}\), while the initial edge features \(e_{ij}\) represent the Euclidean distances, where \(i,j\in\{1,\ldots,m\}\). Before being fed into E-MTAM, these input node and edge features are first mapped into high-dimensional embeddings through a fully connected layer, respectively, as follows:  
\[n_{i}^{0}=BN(W^{x}x_{i}+b^{x}), \tag{3}\]  
\[\hat{e_{ij}}=BN(W^{x}e_{ij}+b^{x}) \tag{4}\]  
where \(W^{x}\), \(W^{x}\), \(b^{x}\) and \(b^{x}\) are trainable parameters. The initial node embeddings \(\mathbf{n^{0}}=\{n_{1}^{0},n_{2}^{0},\ldots,n_{m}^{0}\}\) and edge embeddings \(\mathbf{\hat{e}}=\{\hat{e}_{11},\hat{e}_{12},\ldots,\hat{e}_{mm}\}\) are jointly fed into the encoder, and the node embeddings are updated through \(L\) attention layers. Each attention layer consists of a multi-head attention (MHA) sublayer and a node-wise feed-forward network sublayer. We denote the node embeddings after the \(l\)-th attention layer as \(n_{i}^{l}\), where \(l\in\{1,2,\ldots,L\}\). In contrast to the conventional multi-head attention used in AM, our E-MTAM employs an edge-driven multi-head attention (EDMHA), which enhances the model's ability to capture and represent graph topology and relational information more effectively. As shown in Figure 2, EDMHA fuses edge information with node information and updates them simultaneously, enabling richer node representation learning (we omit the superscript (0) for readability). Specifically, we use node embeddings to compute the query, key, and value vectors, and the conventional compatibility \(u_{ij}^{h}\) is obtained by taking the dot product of the query and key vectors. Next, we map the edge embeddings to a higher-dimensional space using a fully connected linear layer to obtain \(e_{ij}^{w}\), which is then multiplied by the compatibility \(u_{ij}^{h}\), followed by a softmax function to compute the attention weights. Finally, we aggregate the neighboring graph information by weighted summation to update the node embeddings \(n_{i}^{h}\). Figure 1: Overall framework of proposed E-MTAM. We leverage the input node embeddings \(n_{i}\in\mathbb{R}^{m\times d_{n}}\) to compute the query, key, and value vectors:  
\[q_{i}^{h}=W_{E,Q}^{h}n_{i},k_{i}^{h}=W_{E,K}^{h}n_{i},v_{i}^{h}=W_{E,V}^{h}n_{i} \tag{5}\]  
where \(W_{E,Q}^{h},W_{E,K}^{h}\in\mathbb{R}^{d_{k}\times d_{n}}\) and \(W_{E,V}^{h}\in\mathbb{R}^{d_{v}\times d_{n}}\) are trainable query, key, and value matrices, respectively, for each head \(h\). Subsequently, we incorporate edge information to enhance the conventional compatibility and compute the weight values through a softmax layer:  
\[u_{ij}^{h}=\frac{(q_{i}^{h})^{T}k_{j}^{h}}{\sqrt{d_{k}}}, \tag{6}\]  
\[e_{ij}^{w}=W_{\_edge}e_{ij}+b_{\_edge}, \tag{7}\]  
\[w_{ij}^{h}=softmax(u_{ij}^{h}e_{ij}^{w}) \tag{8}\]  
where \(W_{\_edge}\) and \(b_{\_edge}\) are learnable parameters. Therefore, we can update the node's representation by aggregating the edge information from its neighborhood connectivity, as computed in  
\[n_{i}^{h}=\sum_{j\in N_{i}}w_{ij}^{h}v_{i}^{h} \tag{9}\]  
Figure 2: Edge-driven multi-head attention block. Each head of EDMHA, indexed by \(h\), generates the aggregated node embeddings \(\mathbf{n^{h}}=\{n_{1}^{h},n_{2}^{h},\ldots,n_{m}^{h}\}\). We then concatenate and linearly transform these node embeddings to obtain the final output of EDMHA:  
\[EDMHA(\mathbf{n},\mathbf{\hat{e}})=\sum_{h=1}^{H}(W_{E}^{h}\mathbf{n}^{h}+b_{E} ^{h}) \tag{10}\]  
where \(W_{E}^{h}\) and \(b_{E}^{h}\) are trainable parameters; \(H\) is the number of multi-head attention. In the encoder, let \(\mathbf{n}^{(l-1)}\) denote the output of the \((l-1)\)-th layer. The output of the \(l\)-th EDMHA sublayer can be calculated as follows:  
\[\hat{e_{ij}}=BN(W^{x}e_{ij}+b^{x}) \tag{4}\]0  
The operations in the feed-forward network (FFN) sublayer are similar.