## 3 Computational Analysis
### Computational Results
Table 4 shows the results achieved by the GVNS schemes within a 2 min run time limit and the Best Improvement search strategy. The results of Table 4 corroborate the conclusion of Tables 1 and 2 that both GVNS_1 and GVNS_2 outperform GVNS_3 in most cases. \begin{table}
\begin{tabular}{c c c c c c c c} \hline _Instance_ & **zOpt** & **GVNS\_1** & **GVNS\_2** & **GVNS\_3** & **GAP\_1 (\%)** & **GAP\_2 (\%)** & **GAP\_3 (\%)** \\ \hline _br17.atsp_ & 39 & 39 & 39 & 39 & 0.00 & 0.00 & 0.00 \\ _ft53.atsp_ & 6905 & 7043 & 7135 & 7674 & 2.00 & 3.33 & 11.14 \\ _ft70.atsp_ & 38673 & 39507 & 40206 & 40539 & 2.16 & 3.96 & 4.83 \\ _ft733.atsp_ & 1286 & 1289 & 1286 & 1379 & 0.23 & 0.00 & 7.23 \\ _ftv35.atsp_ & 1473 & 1476 & 1473 & 1533 & 0.20 & 0.00 & 4.07 \\ _ftv38.atsp_ & 1530 & 1538 & 1541 & 1599 & 0.52 & 0.72 & 4.51 \\ _ftv44.atsp_ & 1613 & 1632 & 1644 & 1728 & 1.18 & 1.92 & 7.13 \\ _ftv47.atsp_ & 1778 & 1792 & 1816 & 1940 & 0.79 & 2.14 & 9.11 \\ _ftv55.atsp_ & 1608 & 1642 & 1665 & 2012 & 2.11 & 3.54 & 25.12 \\ _ftv64.atsp_ & 1839 & 1908 & 1986 & 2193 & 3.75 & 7.99 & 19.25 \\ _ftv70.atsp_ & 1950 & 2110 & 2157 & 2346 & 8.21 & 10.62 & 20.31 \\ _ftv170.atsp_ & 2755 & 3341 & 3852 & 3923 & 21.27 & 39.82 & 42.40 \\ _kro124p.atsp_ & 36230 & 36501 & 37076 & 38195 & 0.75 & 2.34 & 5.42 \\ _pt43.atsp_ & 5620 & 5620 & 5620 & 5627 & 0.00 & 0.00 & 0.12 \\ _rb323.atsp_ & 1326 & 1486 & 1539 & 1633 & 12.06 & 16.06 & 23.15 \\ _rb358.atsp_ & 1163 & 1307 & 1409 & 1437 & 12.38 & 21.15 & 23.55 \\ _rbg403.atsp_ & 2465 & 2510 & 2547 & 2554 & 11.76 & 11.76 & 11.76 \\ _rbg443.atsp_ & 2720 & 2765 & 2824 & 2844 & 1.65 & 3.16 & 4.56 \\ _r48p.atsp_ & 14422 & 14480 & 14498 & 14659 & 0.40 & 0.12 & 1.64 \\ \hline \multicolumn{1}{c}{**Average**} & **6599.74** & **6736.11** & **6858.58** & **7044.95** & **15.88** & **17.69** & **22.28** \\ \hline \end{tabular}
\end{table} 
Table 2: The results depicted here were obtained using the Best Improvement search strategy and an execution time limit of 1 min [14]. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Instance** & **zOpt** & **GVNS\_1** & **GVNS\_2** & **GVNS\_3** & **GAP\_1 (\%)** & **GAP\_2 (\%)** & **GAP\_3 (\%)** \\ \hline _br17.atsp_ & 39 & 39 & 39 & 39 & 0.00 & 0.00 & 0.00 \\ _ft53.atsp_ & 6905 & 7024 & 7498 & 7752 & 1.72 & 8.59 & 12.27 \\ _ft70.atsp_ & 38673 & 39615 & 40827 & 40505 & 2.44 & 5.57 & 4.74 \\ _ftv33.atsp_ & 1286 & 1330 & 1370 & 1454 & 3.42 & 6.53 & 13.06 \\ _ftv35.atsp_ & 1473 & 1482 & 1519 & 1604 & 0.61 & 3.12 & 8.89 \\ _ftv38.atsp_ & 1530 & 1547 & 1618 & 1576 & 1.11 & 5.75 & 3.01 \\ _ftv44.atsp_ & 1613 & 1628 & 1839 & 1812 & 0.93 & 14.01 & 12.34 \\ _ftv47.atsp_ & 1778 & 1787 & 2020 & 2097 & 0.51 & 13.61 & 17.94 \\ _ftv55.atsp_ & 1608 & 1668 & 2012 & 1912 & 3.73 & 25.12 & 18.91 \\ _ftv64.atsp_ & 1839 & 1951 & 2484 & 2476 & 6.09 & 35.07 & 34.64 \\ _ftv70.atsp_ & 1950 & 2165 & 2571 & 2484 & 11.03 & 31.85 & 27.38 \\ _ftv170.atsp_ & 2755 & 3412 & 3923 & 3923 & 23.85 & 42.40 & 42.40 \\ _ftv24.atsp_ & 36230 & 39344 & 44243 & 40849 & 8.60 & 22.12 & 12.75 \\ _pt34.atsp_ & 5620 & 5620 & 5628 & 5657 & 0.00 & 0.14 & 0.66 \\ _rb323.atsp_ & 1326 & 1499 & 1576 & 1586 & 13.04 & 18.85 & 19.60 \\ _rbg358.atsp_ & 1163 & 1329 & 1410 & 1406 & 14.27 & 21.23 & 20.89 \\ _rbg403.atsp_ & 2465 & 2509 & 2586 & 2547 & 2.27 & 4.10 & 11.76 \\ _rbg443.atsp_ & 2720 & 2808 & 2849 & 2811 & 3.24 & 4.74 & 3.35 \\ _r48p.atsp_ & 14422 & 14475 & 14936 & 14708 & 0.37 & 3.56 & 1.98 \\ \hline \multicolumn{1}{c}{**Average**} & **6599.74** & **6906.95** & **7418.32** & **7220.95** & **5.29** & **13.96** & **24.78** \\ \hline \end{tabular}
\end{table} 
Table 3: Results using the First Improvement search strategy and an execution time limit of 2 min [14]. Tables 5-8 contain the aggregated experimental results for Symmetric TSP instances. Specifically, they contain the benchmark name, the optimal value (zOpt), the cost of the three GVNS variations (GVNS_1, GVNS_2 and GVNS_3) and their corresponding gaps from the optimal value.