# Edge-Driven Multiple Trajectory Attention Model for Vehicle Routing Problems
## 3 Methodology
### Decoder  
E-MTAM comprises \(K\) attention-based decoders, which are structurally identical but do not share parameters. At time step \(t\), each decoder generates a probability value \(p_{\theta}^{k}\) to select the next node to visit, continuing this process until all nodes have been visited. Previous approaches [25,41] typically rely on the entire graph embedding vector produced by the encoder to compute the context embedding \(c_{t}\), which often fail to capture dynamic state transitions effectively. In this work, we integrate dynamic visitation information into the graph embeddings and propose a context embedding \(c_{t}\) that more effectively captures dynamic information changes. Specifically, we leverage the node embedding \(\mathbf{n}^{(L)}\) generated by the encoder and the subsequent mask \(m_{t}^{unv}\) produced by the decoder to obtain a masked node embedding \(\mathbf{n}_{t}^{mask}\). We then aggregate the mean and maximum values of \(m_{t}^{unv}\), along with the embeddings of the first \(n_{1}\) and last visited node \(n_{t-1}\) to construct a context embedding \(c_{t}\) that is more sensitive to dynamic state transitions:  
\[\mathbf{n}_{t}^{mask}=\sigma(W_{m}\mathbf{n}^{(L)}+b_{m})\odot\mathbf{n}^{( L)}\odot m_{t}^{unv}, \tag{13}\]  
\[c_{t}=Concat(\frac{1}{m}\sum_{i=1}^{m}\mathbf{n}_{i}^{mask},\max_{i}\mathbf{ n}_{i}^{mask},n_{1}^{(L)},n_{t-1}^{(L)}) \tag{14}\]  
where \(W_{m}\) and \(b_{m}\) are learnable variables, and \(\sigma\) is the Sigmoid function.  
We utilize an MHA module to compute the new context embedding \(\xi_{t}^{k}\) for decoder \(k\) at time step \(t\), where the attention values are computed based on \(\mathbf{n}^{(L)}\) and \(c_{t}\). In this work, we adopt the self-attention mechanism from AM to obtain the attention values. Unlike the MHA in our encoder, the queries in the decoder's MHA are computed from the context embedding \(c_{t}\), while the keys and values are derived from the node embeddings \(\mathbf{n}_{l}\):  
\[\xi_{t}^{k}=MHA(v^{Q}=c_{t},v^{K}=n^{L},v^{V}=n^{L}) \tag{15}\]  
We then compute the compatibility values \(u_{i}^{k}\) for each node based on \(\xi_{t}^{k}\) and the node embedding \(n_{i}^{(L)}\), and we apply tanh clipping to restrict the output within the range \([-C,C]\)To prevent revisiting nodes, we set the compatibility values of already visited nodes to \(-\infty\) according to the mask \(m_{t}^{unv}\). Finally, we apply a softmax function to obtain the final output probability \(p_{\theta}^{k}\) for decoder \(k\) at time step \(t\) to select node \(i\) for visitation:  
\[u_{i}^{k}=\left\{\begin{array}{ll}Ctanh(\frac{(W_{C,Q}^{k}\hat{x}_{t}^{k})^{ \top}(W_{C,R}^{k}n_{i}^{(L)})}{\sqrt{d_{k}}})&\text{if }m_{i}^{unv}=1\\ -\infty&\text{otherwise.}\end{array}\right. \tag{16}\]  
\[p_{\theta}^{k}(a_{t}=i|a_{1:t-1})=\frac{e^{u_{i}^{k}}}{\sum_{j}e^{u_{i}^{k}}} \tag{17}\]  
where \(W_{C,Q}^{k},W_{C,K}^{k}\in\mathbb{R}^{d_{k}\times d_{k}}\) are learnable weight matrices, and \(C\) is a constant.  
Subsequently, the action \(a_{t}\) will be sampled based on \(p_{\theta}\) at each time step \(t\). This process continues until all \(m\) nodes are selected. To record the visitation information for each node indexed by \(i\in[1,2,\dots,m]\), we initialize a mask vector \(m_{1}^{unv}\in\mathbb{R}^{1\times m}\) with all elements set to \(1\) and update it at each time step \(t\):  
\[m_{i,t+1}^{unv}=\left\{\begin{array}{ll}1&\text{if }i=a_{t}\\ m_{i,t}^{unv}&\text{otherwise.}\end{array}\right. \tag{18}\]