# Heuristics and Learning Models for Dubins MinMax Traveling Salesman Problem
## 5 Heuristics for the MD-GmTSP
### Initial Solution: Construction Phase
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Construction**} & \multicolumn{2}{c}{\(N_{1}\)} & \(N_{2}\) & **Average** & \multicolumn{2}{c}{**Max**} & \multirow{2}{*}{
\begin{tabular}{c} **Standard** \\ **Deviation** \\ \end{tabular} } & \multicolumn{2}{c}{**Average**} \\ \cline{2-2} \cline{5-7}  & **Move** & **Insertion** & **Local** & **Improvement** & **Improvement** & **Deviation** & **Average** \\ \hline Cheapest & 2-move & Greedy & 2-opt & 4.461 & 26.670 & 7.283 & 899.159 \\ Cheapest & 2-move & Greedy & 3-opt & 3.377 & 21.675 & 6.248 & 912.802 \\ Cheapest & 2-move & Random & 2-opt & 2.191 & 18.315 & 5.487 & 898.602 \\ Cheapest & 2-move & Random & 3-opt & 1.912 & 16.786 & 5.201 & 916.977 \\ Cheapest & 1-move & Greedy & 2-opt & 5.644 & 29.894 & 8.035 & 899.059 \\ Cheapest & 1-move & Greedy & 3-opt & 4.603 & 26.105 & 7.240 & 914.916 \\ Cheapest & 1-move & Random & 2-opt & 2.547 & 19.881 & 5.932 & 899.179 \\ Cheapest & 1-move & Random & 3-opt & 2.596 & 17.587 & 5.607 & 913.728 \\ Farthest & 2-move & Greedy & 2-opt & 3.483 & 25.342 & 7.802 & 1372.255 \\ Farthest & 2-move & Greedy & 3-opt & 2.997 & 25.202 & 6.868 & 1373.696 \\ Farthest & 2-move & Random & 2-opt & 1.922 & 20.988 & 5.633 & 1365.133 \\ Farthest & 2-move & Random & 3-opt & 1.958 & 20.988 & 5.514 & 1381.819 \\ Farthest & 1-move & Greedy & 2-opt & 3.729 & 25.622 & 8.050 & 1356.863 \\ Farthest & 1-move & Greedy & 3-opt & 3.691 & 25.622 & 7.486 & 1374.722 \\ Farthest & 1-move & Random & 2-opt & 2.200 & 23.350 & 6.111 & 1388.016 \\ Farthest & 1-move & Random & 3-opt & 2.180 & 23.913 & 6.225 & 1376.558 \\ Nearest & 2-move & Greedy & 2-opt & 3.462 & 25.342 & 7.598 & 1358.205 \\ Nearest & 2-move & Greedy & 3-opt & 3.181 & 25.342 & 7.029 & 1374.512 \\ Nearest & 2-move & Random & 2-opt & 1.775 & 20.988 & 5.447 & 1362.595 \\ Nearest & 2-move & Random & 3-opt & 1.822 & 20.988 & 5.502 & 1379.830 \\ Nearest & 1-move & Greedy & 2-opt & 4.494 & 26.589 & 8.430 & 1360.322 \\ Nearest & 1-move & Greedy & 3-opt & 4.167 & 25.622 & 7.535 & 1372.429 \\ Nearest & 1-move & Random & 2-opt & 2.068 & 23.990 & 6.232 & 1367.803 \\ Nearest & 1-move & Random & 3-opt & 1.855 & 23.350 & 5.911 & 1375.266 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Influence of different neighborhood structures in VND heuristic on improving the MD-GmTSP tours with \(t_{max}=600\) s time limit. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Construction**} & \multicolumn{2}{c}{\(N_{1}\)} & \(N_{2}\) & **Average** & \multicolumn{2}{c}{**Max**} & \multirow{2}{*}{
\begin{tabular}{c} **Standard** \\ **Deviation** \\ \end{tabular} } & \multicolumn{2}{c}{**Average**} \\ \cline{2-2} \cline{5-7}  & **Move** & **Insertion** & **Local** & **Improvement** & **Improvement** & **Deviation** & **Computation** \\ \hline Cheapest & Shake & Greedy & VND\({}_{\text{eq}}\) & 5.862 & 22.840 & 6.842 & 915.206 \\ Cheapest & Shake & Random & VND\({}_{\text{eq}}\) & 2.241 & 21.121 & 6.233 & 969.554 \\ Cheapest & Shake\({}_{\text{mod}}\) & Greedy & VND\({}_{\text{eq}}\) & 6.165 & 23.141 & 7.486 & 919.908 \\ Cheapest & Shake\({}_{\text{mod}}\) & Random & VND\({}_{\text{eq}}\) & 2.902 & 21.666 & 6.005 & 974.873 \\ Farthest & Shake & Greedy & VND\({}_{\text{eq}}\) & 2.595 & 26.589 & 7.208 & 1370.046 \\ Farthest & Shake & Random & VND\({}_{\text{eq}}\) & 2.399 & 26.589 & 7.089 & 1406.246 \\ Farthest & Shake\({}_{\text{mod}}\) & Greedy & VND\({}_{\text{eq}}\) & 2.996 & 26.589 & 7.226 & 1368.846 \\ Farthest & Shake\({}_{\text{mod}}\) & Random & VND\({}_{\text{eq}}\) & 2.813 & 25.548 & 7.052 & 1409.714 \\ Nearest & Shake & Greedy & VND\({}_{\text{eq}}\) & 3.555 & 24.363 & 7.183 & 1368.566 \\ Nearest & Shake & Random & VND\({}_{\text{eq}}\) & 2.176 & 23.506 & 6.349 & 1412.890 \\ Nearest & Shake\({}_{\text{mod}}\) & Greedy & VND\({}_{\text{eq}}\) & 4.222 & 25.799 & 7.535 & 1391.104 \\ Nearest & Shake\({}_{\text{mod}}\) & Random & VND\({}_{\text{eq}}\) & 2.078 & 23.170 & 6.161 & 1433.516 \\ \hline \hline \end{tabular}
\end{table}