# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase

Table 5: Influence of different neighborhood structures in GVNS on improving the MD-GmTSP tours with \(t_{max}=600\) s time limit. Figure 8: Feasible MD-GmTSP paths for the attt48 instance for \(m=3\) vehicles and \(h=8\) angle discretizations obtained from tour construction and improvement heuristics. The vehicle paths are differentiated by the colors of the paths. Figure 7: Feasible MD-GmTSP paths for the Ulysses22 instance for \(m=3\) vehicles and \(h=8\) angle discretizations obtained from different tour construction and GVNS heuristics. The vehicle paths are differentiated by the colors of the paths. other hand, the GVNS + Shake\({}_{mod}\) scheme resulted in an average improvement of 3.46% over the initial tours, while the VND + one-point move scheme generated an average improvement of 3.32% over the initial solution. A comparison is made between the best solutions obtained from VNS-based heuristics and MILP formulations for each instance in Table 7. It is observed that VNS heuristics generally produce superior solutions in significantly less time than the MILP solutions obtained from CPLEX. ### Learning-Based Approach

In the learning-based approach, training and testing datasets were generated separately for \(m\) Dubins agents and \(n\) cities. Each city coordinate was uniformly generated at random in the interval \((0,1)^{2}\) and paired with \(h=8\) heading angles in the range \([0,2\pi]\). During training, the data were randomly generated at every iteration. To overcome performance limitations, separate models were trained for different numbers of cities and radius of curvature (\(\rho\)) specific to each instance. A total of 1000 instances were generated for each type and utilized to train the RL model described in Section 6. The RL model was trained using the Adam optimization method with the following hyperparameters: a learning rate of =1\(e^{-5}\), a clipping gradients norm of 3, and S set of 10. Figure 9 illustrates the convergence of a model trained on the pr76 dataset after approximately 2000 iterations

\begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline  & & & \multicolumn{3}{c}{**Construction Phase**} & \multicolumn{6}{c}{**Improvement Phase**} \\ \cline{3-11}
**Instance** & **Cities** & **Radius** & \multicolumn{3}{c}{**Heuristic**} & \multicolumn{1}{c}{**Cost**} & \multicolumn{1}{c}{**Time**} & \multicolumn{1}{c}{**Scheme**} & \multicolumn{1}{c}{\(N_{\text{t}}\)} & \(N_{\text{t}}\) & \multirow{2}{*}{**Cost**} & \multirow{2}{*}{**Time**} & \multirow{2}{*}{**Improvement (\%)**} \\ \cline{4-11} \cline{6



during the training process. The dataset consists of 1000 instances, each comprising 76 cities randomly distributed within the original boundaries of the pr76 instances. The tours for these instances are calculated using a Dubins turning radius (\(\rho=980\)). In order to assess the effectiveness of the RL model, we compare its solutions to those generated by a heuristics-based approach for the MD-GmTSP. The trained RL model is utilized to evaluate the min-max tours for the original pr76 instance, ensuring a valid basis for comparison between the two approaches. Table 8 compares the solutions obtained from the RL model to the best solutions obtained from the MILP and VNS-based formulation. It is important to note that due to the absence of pre-existing baselines for the Dubins MTSP, it was not possible to determine the optimality gap for the solutions obtained from the RL model. It can be observed that the RL model outperformed both the MILP formulation and the VNS-based heuristics on smaller instances of the problem. Specifically, the RL-based solutions performed better in terms of solution quality for smaller instances. However, as the problem instances became larger, the VNS-based heuristics generated superior solutions compared to the RL model. This indicates that the RL model is especially effective