# A Deep Reinforcement Learning-Based Decision-Making Approach for Routing Problems
## 3 Methodology
### Decoder  
In the decoding process, most existing DRL-based methods utilize a static context embedding, denoted as \(g^{\text{context}}\), to compute the compatibility scores for node selection. Typically, this context embedding is formed by concatenating the graph embedding \(g^{\text{graph}}\), the depot node embedding \(g_{n_{1}}^{(L)}\), and the last-visited node embedding \(g_{n_{t-1}}^{(L)}\). However, such a design fails to effectively capture the evolving dynamics inherent in routing state transitions. To overcome this limitation, we propose a dynamic-aware context embedding \(g_{t}^{\text{context}}\), which explicitly encodes both state transitions and graph variations over time. To be more specific, \(g_{t}^{\text{context}}\) integrates the embeddings of the visited subgraph \(g_{t}^{\text{vis}}\), the unvisited subgraph \(g_{t}^{\text{unv}}\), the depot node \(g_{n_{1}}^{(L)}\), and the last-visited node \(g_{n_{t-1}}^{(L)}\). This enriched and adaptive representation provides a more informative and flexible encoding of the current routing state, thereby enhancing the model's decision-making capability during the decoding process.  
\[g_{t}^{\text{context}}=\text{Concatenation}\Big{(}g_{t}^{\text{vis}},g_{t}^{ \text{unv}},g_{n_{1}}^{(L)},g_{n_{t-1}}^{(L)}\Big{)}, \tag{12}\]  
\[g_{t}^{\text{vis}}=\frac{1}{t-1}\sum_{i=1}^{t-1}g_{i}^{(L)}, \tag{13}\]  
\[g_{t}^{\text{unv}}=\frac{1}{N-t+1}\sum_{i=1}^{N}g_{i}^{(L)}-\frac{t-1}{N-t+1}g _{t}^{\text{vis}}. \tag{14}\]  
In the decoder, we employ an MHA layer followed by a single-head attention (SHA) layer to assess the compatibility between the context embedding and node embeddings, enabling iterative node selection and route construction. Within the MHA layer, a glimpse embedding is computed to aggregate information from the context and all nodes. The query vector in MHA is derived from the dynamic-aware context embedding \(g_{t}^{\text{context}}\), while the key and value vectors originate from the graph embedding. The computation process is formally defined as follows:  
\[g_{t}^{\text{glimpse}}=\text{MHA}\Big{(}g_{t}^{\text{context}}W_{S}^{Q},g^{ \text{graph}}W_{S}^{K},g^{\text{graph}}W_{S}^{V}\Big{)}, \tag{15}\]  
where \(W_{S}^{Q}\), \(W_{S}^{K}\), and \(W_{S}^{Q}\) are trainable parameter matrices.  
Then, a SHA layer is utilized to calculate the probability distribution of selecting the next node to visit. In order to promote exploration and enhance marginal performance, a tanh function is used to clip the compatibility with the range of \([-\mathcal{C},\mathcal{C}]\).  
\[p_{\theta}(\pi_{t}=i|s)=\frac{\exp(u_{i,t})}{\sum_{i}\exp(u_{i,t})}, \tag{16}\]  
\[u_{i,t}=\mathcal{C}\cdot\tanh\left(\frac{Q_{t}K_{i,t}^{\mathcal{C}}}{d_{g}} \right), \tag{17}\]  
\[Q_{t}=g_{t}^{\text{glimpse}}W_{c}^{Q},\ K_{i,t}=g_{i}^{(L)}W_{c}^{K}, \tag{18}\]where \(W_{c}^{Q},W_{c}^{K}\) are trainable matrices and \(\mathcal{C}\) is a constant. To ensure solution feasibility during the decoding process, an adaptive masking strategy is employed. Specifically, in routing problems, nodes that have already been visited are masked to prevent revisitation. For CVRPs, additional feasibility constraints are imposed by masking customer nodes whose demand exceeds the current remaining payload of the vehicle. This mechanism ensures that only serviceable nodes are considered at each decision step, thereby preserving the validity of the constructed solution.