# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
GIN uses the following update process to parameterize the graph neural network:

\[f_{v}^{(k)}=MLP^{(k)}\{(1+\epsilon^{(k)}).h_{v}^{(k-1)}+\sum_{u\in N(v)}h_{u}^ {(k-1)}\} \tag{11}\]

where \(f_{v}^{k}\) is the feature vector of node \(v\in V\) at the \(k-\)th iteration/layer, \(N_{v}\) denotes all the neighbors of node \(v\), \(u\) is neighboring node of \(v\) (i.e., \(u\in N_{v}\)), \(MLP\) represents a multi-layer perceptron, and \(\epsilon\) is a learnable parameter. #### 6.1.2 Distributed Policy Networks

We propose a two-stage distributed policy network-based approach for designing a graph neural network with the attention mechanism ([PERSON] et al., 2017). In the first stage, each agent autonomously generates its _agent embedding_ by leveraging both the global information and the node embeddings present in the graph. In the second stage, each node selects an agent to associate with itself based on its own embedding and all the prior agent embeddings. Calculation of Agent Embedding

Graph embeddings, denoted as \(g_{f}\), are computed by max pooling from the set of node features \(f=\{f_{1},f_{2},\ldots f_{n}\}\), i.e.,

\[g_{f}=\max\{f_{1},f_{2},\ldots,f_{n}\}.\]

These graph embeddings are then used as inputs to construct an agent embedding, where \(f_{i}\in R^{p}\), \(n\) is the number of nodes, \(p\) is the dimension of node embedding, and \(g_{f}\in R^{p}\). To construct the agent embedding, an attention mechanism is employed to generate attention coefficients that signify the significance of a particular node's feature in creating its embedding. * _Graph Context embedding:_ A graph context embedding is used to ensure that every city, except the depot, is visited by only one agent and the depot is visited by all agents. By setting the depot as the first node in the graph (\(f_{depot}=f_{1}\)), we concatenate the depot features with the global embedding to create the graph context embedding, represented as \(f_{c}\in\mathbb{R}^{2p}\). The concatenation operation is denoted by \([:,:]\) and is shown in Equation (12): \[f_{c}=[g_{f};f_{1}].\] (12)
* _Attention Mechanism_: The attention mechanism [90] is used to convey the importance of a node to an agent \(a\). The node feature set obtains the keys and values, and the graph context embedding computes the query for agent \(a\), which is standard for all agents. \[q_{a}=\theta_{ag}^{d^{\prime}\times 2p}f_{c}^{2p},\] \[k_{ai}=\theta_{ak}^{d^{\prime}\times p}f_{i}^{p},i=\{2,3,\ldots,n\},\] Figure 4:0 (13) where \(d_{k}\) and \(d_{v}\) are the dimension of key and values. A _SoftMax_ is used to compute the attention weights \(w_{ai}\in[0,1]\), which the agent puts on node \(i\), using: Figure 4:1 (14) where \(u_{ai}\) is the compatibility of the query to be associated with the agent and all its nodes given by Figure 4:2 (15)
* _Agent embedding_: From the attention weights, we construct the agent embedding using Figure 4:3 (16)

In this section, we outline the process for determining the policy that assigns an agent to a specific node. To evaluate the importance of each agent to the node, we utilize the following set of equations. These equations are applied to each agent individually as follows:

Figure 4:4

Figure 4:5

Figure 4:6

Figure 4:7

Here, \(d^{{}^{\prime}}_{k}\) is the dimension of new keys; \(\theta_{ak^{{}^{\prime}}}\) and \(\theta_{aq^{{}^{\prime}}}\) are parameters of neural networks to project the embeddings back to \(d^{{}^{\prime}}_{k}\) dimensions. The importance \(imp_{ai}\) is computed by obtaining \(u_{ai^{{}^{\prime}}}\) for a new round of attention and clipping the result within \([-10,10]\) using \(\tanh\)[80]. Since each agent is limited to visiting only one city, the agent's importance factor determines which city it visits. A _SoftMax_ function evaluates the probability of an agents likelihood to visit a node:

Figure 4:8where \(p_{ai}\) is the probability of agent \(a\) visiting node \(i\); \(imp_{ai}\) is the importance of node \(i\) for agent \(a\); \(a\in 1,2,\ldots,m\); and \(i\in 1,2,\ldots,n\).