# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
The concept behind this approach is that heuristics can be viewed as decision-making policies which can be parameterized using neural networks. The policies can then be trained to solve different combinatorial optimization problems. In the next section, we introduce a reinforcement learning method to develop policies for solving the MD-GmTSP. This method holds great promise for achieving high-quality solutions in a shorter amount of time than traditional heuristics. ## 6 Learning-Based Approach for the MD-GmTSP

Several machine learning techniques, including neural networks [76], pointer networks [77], attention networks [78; 79] and reinforcement learning [80; 81] have been explored to solve the TSP problem. [PERSON] et al. [79] extended a single-agent TSP model to learn strong heuristics for the vehicle routing problem (VRP) and its variants. However, supervised learning, which is successful for most machine learning problems, is not applicable for combinatorial optimization problems due to the unavailability of optimal solutions for large instances, especially for co-operative combinatorial optimization problems like multiple agent TSP, asymmetric mTSP, and multi-agent task assignment and scheduling problems. These problems pose several challenges, such as an explosion of the search space with the increase in the number of agents and cities, a lack of data with ground truth solutions, and difficulty in developing an architecture that can capture interactive behaviors among agents. Reinforcement learning (RL) is a commonly explored paradigm to solve problems with the above difficulties, whose solution quality can be verified and provided as a reward to a learning algorithm. Recent studies [82; 83] have investigated using RL-based approaches to optimize the Euclidean version of MinMax TSP, but no significant study has been conducted for the Dubins MinMax TSP. The main advantage of using the RL-based method is that the majority of computational time and resources are spent on training. Once a trained model is available, a feasible solution can be inferred almost in real-time. In this paper, we utilize the RL framework developed by [PERSON] et al. (2018) and expand its application to the Dubins MTSP. The model consists of a shared graph neural network and distributed policy networks that collectively learn a universal policy representation for generating nearly optimal solutions for the Dubins MTSP. To address the challenges of optimization, the extensive search space of the problem is effectively partitioned into two tasks: assigning cities to agents with candidate heading angles and performing small-scale Dubins TSP planning for each agent. As proposed by [PERSON] et al. (2018), an S-sample batch reinforcement learning technique is used to address the lack of training data, reducing the gradient approximation variance and significantly enhancing the convergence speed and performance of the RL model. ### Framework Architecture

In this work, the graph isomorphism network (GIN) ([PERSON] and [PERSON], 2017) policy is used to summarize the state of the instance graph and assigns nodes to each agent for visitation, effectively transforming the MD-GmTSP into a single-agent DTSP problem. This approach facilitates the use of algorithms ([PERSON] and [PERSON], 2017; [PERSON] et al., 2017; [PERSON] et al., 2017), learning-based methods ([PERSON] et al., 2017; [PERSON] et al., 2017; [PERSON] et al., 2017), and solvers ([PERSON] et al., 2017; [PERSON] et al., 2017; [PERSON] et al., 2017) to quickly obtain near-optimal solutions. Additionally, we utilize a group of distributed policy networks to address the node-to-agent assignment problem. #### 6.1.1 Graph Embedding

For each node \(v\in V\), the graph embedding network GIN ([PERSON] and [PERSON], 2017) computes a \(p\)-dimensional feature embedding \(f_{v}\) by information sharing from the neighboring connected nodes according to the graph structure.