# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
Additionally, the cheapest-insertion heuristics generated solutions approximately 2.5 times faster than the nearest-insertion method. \begin{table}
\begin{tabular}{l c c c c} \hline
**Instance** & **Targets** & **Turning Radius (\(\rho\))** & **Minmax Cost** & **Optimality Gap (\%)** \\ \hline att48 & 47 & 394 & 28,315.3486 & 42.23 \\ berlin52 & 51 & 55 & 5433.474 & 43.54 \\ ch130 * & 129 & 39 & - & - \\ eil101 * & 100 & 4 & - & - \\ eil51 & 50 & 4 & 333.7285 & 46.46 \\ eil76 * & 75 & 4 & - & - \\ gr137 * & 136 & 4 & - & - \\ gr96 * & 95 & 4 & - & - \\ kroA100 * & 99 & 200 & - & - \\ pr136 * & 135 & 516 & - & - \\ pr76 * & 75 & 980 & - & - \\ rat99 * & 98 & 5 & - & - \\ rd100 * & 99 & 57 & - & - \\ st70 * & 69 & 6 & - & - \\ ulysses16 & 15 & 2 & 57.7487 & 19.27 \\ ulysses22 & 21 & 2 & 58.0386 & 14.09 \\ \hline \end{tabular}
\end{table} 
Table 1: MD-GmTSP results for \(m=3\) vehicles and \(h=8\) discretizations on TSPLIB instances using CPLEX 12.10 with a runtime of 3 h (10,800 s). _Instances that CPLEX could not solve are indicated by *_. #### 7.2.2 Analysis of VNS Improvements for MD-GmTSP

The impact of different neighborhood structures on improving the MD-GmTSP tours using BVNS, VND, and GVNS heuristics is shown in Tables 3-5, respectively. These improvement heuristics were executed with a computational time limit of \(t_{max}=600\) s (10 min) as the stopping criterion, with FirstImprovement used to switch between neighborhoods. The presented results in each row of Tables 3-5 represent the average MD-GmTSP solutions for all TSPLIB instances considered. The analysis reveals that the improvement heuristics can achieve solution quality improvements of up to 30.78%. Furthermore, the average time required to solve these instances ranged from 898.6 s to 1439.96 s. Refer to Figure 7 for sample solutions with respect to the GVNS heuristic. \begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multirow{2}{*}{**Radius**} & \multicolumn{2}{c}{**Cheapest Insertion**} & \multicolumn{2}{c}{**Farthest Insertion**} & \multicolumn{2}{c}{**Nearest Insertion**} & \multicolumn{2}{c}{\(\underline{\underline{\underline{\underline{\underline{\underline{\underline{\underline{ \underline{\underline{\underline{\underline{\underline{\underline{\underline{\leftleftleftleftleftleftleft}} \right)}}}}}}}}}\) (\%)**} \\ \cline{2-9}  & & **Cost (\(c_{c}\))** & **Time (\(t_{c}\))** & **Cost (\(c_{f}\))** & **Time (\(t_{f}\))** & **Cost (\(c_{n}\))** & **Time (\(t_{n}\))** & **Time (\(t_{n}\))** \\ \hline attt8 & 394 & 32,336.39 & 43.38 & 28,197.11 & 108.72 & 28,197.11 & 107.47 & 114.68 \\ berlin52 & 55 & 6025.99 & 54.05 & 5453.38 & 138.37 & 5453.38 & 138.63 & 110.50 \\ ch130 & 39 & 6472.87 & 751.58 & 5998.74 & 1904.17 & 5998.74 & 1944.28 & 107.90 \\ eil101 & 4 & 554.77 & 361.14 & 450.26 & 898.30 & 450.26 & 900.88 & 123.21 \\ eil51 & 4 & 308.30 & 50.70 & 277.73 & 126.92 & 277.73 & 128.76 & 111.01 \\ eil76 & 4 & 416.51 & 157.05 & 345.66 & 394.27 & 345.66 & 402.35 & 120.50 \\ gr137 & 4 & 847.06 & 850.68 & 701.39 & 2154.25 & 701.39 & 2217.90 & 120.77 \\ gr96 & 4 & 551.00 & 311.42 & 488.93 & 770.56 & 488.93 & 780.32 & 112.69 \\ kroA100 & 200 & 272.36 & 355.99 & 225.92 & 572.53 & 22,592.95 & 879.44 & 120.55 \\ pr136 & 516 & 98,637.39 & 842.15 & 82,162.29 & 2130.30 & 82,162.29 & 2191.75 & 120.05 \\ pr76 & 980 & 97,434.78 & 156.94 & 99,023.43 & 398.98 & 99,023.43 & 400.01 & 98.40 \\ rat99 & 5 & 798.94 & 337.41 & 819.30 & 841.77 & 819.30 & 850.65 & 97.51 \\ rd100 & 57 & 8679.56 & 343.93 & 6833.40 & 870.01 & 6833.40 & 869.33 & 127.02 \\ st70 & 6 & 593.76 & 125.90 & 550.76 & 310.80 & 550.76 & 318.95 & 107.81 \\ ulysses16 & 2 & 66.40 & 2.57 & 76.34 & 5.50 & 76.34 & 5.94 & 86.97 \\ ulysses22 & 2 & 88.00 & 5.26 & 80.49 & 12.78 & 80.49 & 12.94 & 109.33 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of MinMax costs of feasible solutions obtained from insertion heuristics for the MD-GmTSP for \(m=3\) vehicles, \(C=8\) angle discretizations, and \(k=0\) relaxation. Times are specified in secs.