# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
\begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multirow{2}{*}{**Cities**} & \multirow{2}{*}{**Radius**} & \multicolumn{2}{c}{**VNS Solution**} & \multicolumn{2}{c}{**MILP Solution**} & \multicolumn{2}{c}{**RL Solution**} \\ \cline{3-8}  & & & **Cost (\(C_{R}\))** & **Cost (\(C_{m}\))** & \(\frac{C_{R}}{C_{R}}\) & **Cost (\(C_{RL}\))** & \(\frac{C_{RL}}{C_{R}}\) \\ \hline att48 & 48 & 394 & 25,775.29 & 28,315.35 & 1.10 & 22,846.38 & 0.89 \\ ei51 & 51 & 4 & 274.60 & 333.73 & 1.22 & 252.64 & 0.92 \\ pr76 & 76 & 980 & 90,809.31 & - & - & 98,174.43 & 1.08 \\ rd100 & 100 & 57 & 6827.48 & - & - & 7549.84 & 1.11 \\ st70 & 70 & 6 & 550.75 & - & - & 564.64 & 1.03 \\ ulysses16 & 16 & 2 & 56.04 & 57.75 & 1.03 & 54.86 & 0.98 \\ ulysses22 & 22 & 2 & 60.31 & 58.04 & 0.96 & 57.98 & 0.96 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Comparison for best solutions obtained from MILP formulation (\(t_{max}=10\),800 s) against the VNS-based heuristics (\(t_{max}=600\) s). Figure 9: Learning curve for Dubins pr 76.

for solving MD-GmTSP instances with a relatively small number of cities and Dubins agents. This effectiveness can be attributed to the fact that the quality of Dubins tours used during the training phase is higher for smaller instances, while the training data quality decreases with the increase in instance size. The RL model's ability to learn and generalize patterns from the training data enables it to achieve high-quality solutions in these instances. There is scope for additional research and experimentation to explore the potential for enhancing the RL model performance and scalability for larger instances of the MD-GmTSP by leveraging advanced RL techniques and alternative network architectures. ## 8 Conclusions

In this paper, we explore different methods to solve MinMax routing problems for a team of Dubins vehicles. We formulate the routing problem as a one-in-a-set mTSP with Dubins paths and refer to it as the MD-GmTSP. We then develop a MILP formulation for the MD-SmTSP and solve it on 16 TSPLIB instances (ranging from 16 to 137 cities) using CPLEX for finding optimal solutions. We show that this method does not scale well for large instances involving higher numbers of nodes or robots. As an alternate approach, we develop fast heuristics based on insertion techniques to obtain good, feasible solutions for the MD-GmTSP. The results show that, on average, the nearest-insertion algorithm generates solutions with tour costs 11.81% lower than the solutions constructed using the cheapest-insertion algorithm. Subsequently, a combination of VNS-based heuristics with several neighborhood search structures is explored to improve the quality of initial feasible solution within a 600 s time limit. The neighborhood structures we studied include 2-opt, 3-opt, k-point, Or-opt, Shake, and the Shake\({}_{mod}\). We solved the TSPLIB instances to check the performance of different combinations of heuristics and identified the best combination to solve MD-GmTSP. Overall, GVNS-based heuristics produced the most promising improvements over the initial solutions. The best-performing combination to solve the MD-GmTSP was to use the nearest-insertion heuristic to construct the initial tour followed by a GVNS-type heuristic to improve the solution quality using neighborhood search structures. Finally, we also explore a learning-based method to generate solutions for the MD-GmTSP. Our architecture consists of a shared graph neural network, with distributed policy networks that extract a common policy for the Dubins multiple traveling salesmen. An S-sample batch reinforcement learning method trains the model, achieving significant improvements in convergence speed and performance. The resulting RL model is used to generate fast feasible paths to the MD-GmTSP, and a comprehensive comparison is presented on the solution quality obtained from each of the other approaches.