## 3 Computational Analysis
### Computational Results
Table 5 depicts GVNS using the First Improvement search strategy and an execution time limit of 1 min. Table 6 shows GVNS using the Best Improvement as search strategy and an execution time of 1 min. Tables 7 and 8 are executed for 120 s within First and Best improvement search strategy respectively. The reported results show that the GVNS_3 produce better solutions than the other two algorithms, and that GVNS_1 and GVNS_2 do not have significant differences. \begin{table}
\begin{tabular}{c 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 & 7043 & 7207 & 7773 & 2.00 & 4.37 & 12.57 \\ _ft70.atsp_ & 38673 & 39358 & 40230 & 40588 & 1.77 & 4.03 & 4.95 \\ _ftv33.atsp_ & 1286 & 1286 & 1290 & 1370 & 0.00 & 0.31 & 6.53 \\ _ftv35.atsp_ & 1473 & 1474 & 1475 & 1509 & 0.07 & 0.14 & 2.44 \\ _ftv38.atsp_ & 1530 & 1538 & 1555 & 1599 & 0.52 & 1.63 & 4.51 \\ _ftv44.atsp_ & 1613 & 1636 & 1664 & 1731 & 1.43 & 3.16 & 7.32 \\ _ftv47.atsp_ & 1778 & 1787 & 1837 & 1903 & 0.51 & 3.32 & 7.03 \\ _ftv55.atsp_ & 1608 & 1640 & 1686 & 2012 & 1.99 & 4.85 & 25.12 \\ _ftv64.atsp_ & 1839 & 1914 & 2032 & 2217 & 4.08 & 10.49 & 20.55 \\ _ftv70.atsp_ & 1950 & 2038 & 2189 & 2342 & 4.51 & 12.26 & 20.10 \\ _ftv170.atsp_ & 2755 & 3351 & 3918 & 3923 & 21.63 & 42.21 & 42.40 \\ _kro124.atsp_ & 36230 & 36379 & 37378 & 37915 & 0.41 & 3.17 & 4.65 \\ _pt33.atsp_ & 5620 & 5620 & 5620 & 5625 & 0.00 & 0.00 & 0.09 \\ _rb323.atsp_ & 1326 & 1473 & 1531 & 1610 & 11.08 & 15.46 & 21.41 \\ _rb358.atsp_ & 1163 & 1292 & 1405 & 1435 & 11.09 & 20.80 & 23.38 \\ _rb5403.atsp_ & 2465 & 2498 & 2547 & 2553 & 1.30 & 3.25 & 11.76 \\ _rb344.atsp_ & 2720 & 2771 & 2822 & 2842 & 1.88 & 3.75 & 4.49 \\ _ry48p.atsp_ & 14422 & 14468 & 14464 & 14678 & 0.32 & 0.29 & 1.78 \\ \hline \hline
**Average** & **6599.74** & **6716.05** & **6888.89** & **7034.95** & **3.28** & **7.05** & **22.16** \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Results using the Best Improvement search strategy and an execution time limit of 2 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 a280.tsp & 2579 & 2683 & 2739 & 2745 & 4.03 & 6.20 & 6.44 \\ att48.tsp & 10628 & 10628 & 10628 & 10635 & 0.00 & 0.00 & 0.07 \\ bayg29.tsp & 1610 & 1610 & 1610 & 1610 & 0.00 & 0.00 & 0.00 \\ bays29.tsp & 2020 & 2020 & 2020 & 2020 & 0.00 & 0.00 & 0.00 \\ bieri27.tsp & 118282 & 118636 & 120066 & 119966 & 0.30 & 1.51 & 1.42 \\ kroA100.tsp & 21282 & 21296 & 21375 & 21398 & 0.07 & 0.44 & 0.55 \\ burma14.tsp & 3323 & 3323 & 3323 & 3323 & 0.00 & 0.00 & 0.00 \\ ch130.tsp & 6110 & 6156 & 6239 & 6235 & 0.75 & 2.11 & 2.05 \\ ch150.tsp & 6528 & 6583 & 6720 & 6723 & 0.84 & 2.94 & 2.99 \\ d493.tsp & 35002 & 36928 & 37307 & 37166 & 5.50 & 6.59 & 6.18 \\ kroB100.tsp & 22141 & 22187 & 22339 & 22362 & 0.21 & 0.89 & 1.00 \\ kroC100.tsp & 20749 & 20759 & 20864 & 20834 & 0.05 & 0.55 & 0.41 \\ kroD100.tsp & 21294 & 21370 & 21573 & 21667 & 0.36 & 1.31 & 1.75 \\ kroE100.tsp & 2068 & 22114 & 22291 & 22360 & 0.21 & 1.01 & 1.32 \\ kroA150.tsp & 26524 & 26792 & 27247 & 27206 & 1.01 & 2.73 & 2.57 \\ kroB150.tsp & 26130 & 26382 & 26680 & 26767 & 0.96 & 2.10 & 2.44 \\ kroA200.tsp & 29368 & 29753 & 30420 & 30392 & 1.31 & 3.58 & 3.49 \\ kroB200.tsp & 29437 & 30164 & 30727 & 30711 & 2.47 & 4.38 & 4.33 \\ d198.tsp & 15780 & 15908 & 16116 & 16147 & 0.81 & 2.13 & 2.33 \\ brg180.tsp & 1950 & 1960 & 2024 & 2040 & 0.51 & 3.79 & 4.62 \\ berlin52.tsp & 7542 & 7542 & 7542 & 7542 & 0.00 & 0.00 & 0.00 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Results using the First Improvement search strategy and an execution time limit of 1 min.