## 3 Computational Analysis
### Computational Results
\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 r15915.tsp & 565530 & 695466 & 695602 & 695602 & 22.98 & 23.00 & 23.00 \\ r15934.tsp & 556045 & 672290 & 672412 & 672412 & 20.91 & 20.93 & 20.93 \\ si535.tsp & 48450 & 48648 & 48803 & 48765 & 0.41 & 0.73 & 0.65 \\ si1032.tsp & 92650 & 92864 & 93285 & 92925 & 0.23 & 0.69 & 0.30 \\ u574.tsp & 36905 & 40248 & 39803 & 39467 & 9.06 & 7.85 & 6.94 \\ u724.tsp & 41910 & 44972 & 45492 & 44598 & 7.31 & 8.55 & 6.41 \\ u1060.tsp & 224094 & 286667 & 251451 & 240193 & 27.92 & 12.21 & 7.18 \\ u1432.tsp & 152970 & 181206 & 188807 & 164045 & 18.46 & 23.43 & 7.24 \\ u1817.tsp & 57201 & 71024 & 72030 & 63539 & 24.17 & 25.92 & 11.08 \\ u1252.tsp & 64253 & 78581 & 79260 & 79217 & 22.30 & 23.36 & 23.29 \\ u2319.tsp & 234256 & 274542 & 278765 & 266890 & 17.20 & 19.00 & 13.93 \\ vm1084.tsp & 239297 & 265725 & 279047 & 255832 & 11.04 & 16.61 & 6.91 \\ vm1748.tsp & 336556 & 407007 & 408102 & 361567 & 20.93 & 21.26 & 7.43 \\ \hline
**Average** & **253944.13** & **301717.44** & **322626.30** & **273781.10** & **14.50** & **7.41** & **5.26** \\ \hline \hline \end{tabular}
\end{table} 
Table 7: _Cont._ \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 a280.tsp & 2579 & 2630 & 2725 & 2706 & 1.98 & 5.66 & 4.92 \\ att48.tsp & 10628 & 10628 & 10628 & 10820 & 0.00 & 0.00 & 1.81 \\ bayg29.tsp & 1610 & 1610 & 1610 & 1613 & 0.00 & 0.00 & 0.19 \\ bayg29.tsp & 2020 & 2020 & 2020 & 2029 & 0.00 & 0.00 & 0.45 \\ bier127.tsp & 118282 & 118421 & 119583 & 119527 & 0.12 & 1.10 & 1.05 \\ kroA100.tsp & 21282 & 21282 & 21312 & 21631 & 0.00 & 0.14 & 1.64 \\ burm14.tsp & 3323 & 3323 & 3323 & 3323 & 0.00 & 0.00 & 0.00 \\ ch130.tsp & 6110 & 6137 & 6208 & 6337 & 0.44 & 1.60 & 3.72 \\ ch150.tsp & 6528 & 6564 & 6680 & 6749 & 0.55 & 2.33 & 3.39 \\ d493.tsp & 35002 & 36232 & 37168 & 36822 & 3.51 & 6.19 & 5.20 \\ kroB100.tsp & 22141 & 22168 & 22249 & 22517 & 0.12 & 0.49 & 1.70 \\ kroC100.tsp & 20749 & 20749 & 20804 & 21402 & 0.00 & 0.27 & 3.15 \\ kroD100.tsp & 21294 & 21317 & 21461 & 21935 & 0.11 & 0.78 & 3.01 \\ kroE100.tsp & 22068 & 22122 & 22201 & 22450 & 0.24 & 0.60 & 1.73 \\ kroA150.tsp & 26524 & 26656 & 27119 & 27400 & 0.50 & 2.24 & 3.30 \\ kroB150.tsp & 26130 & 26232 & 26605 & 26816 & 0.39 & 1.82 & 2.63 \\ kroA200.tsp & 29368 & 29494 & 30276 & 30135 & 0.43 & 3.09 & 2.61 \\ kroB200.tsp & 29437 & 29732 & 30481 & 30843 & 1.00 & 3.55 & 4.78 \\ d198.tsp & 15780 & 15832 & 16036 & 16036 & 0.33 & 1.62 & 1.62 \\ brg180.tsp & 1950 & 1955 & 2014 & 2166 & 0.26 & 3.28 & 11.08 \\ berlin52.tsp & 7542 & 7542 & 7542 & 7737 & 0.00 & 0.00 & 2.59 \\ dantzig4.tsp & 699 & 699 & 699 & 703 & 0.00 & 0.00 & 0.57 \\ eil51.tsp & 426 & 426 & 426 & 432 & 0.00 & 0.00 & 1.41 \\ eil76.tsp & 538 & 538 & 542 & 543 & 0.00 & 0.74 & 0.93 \\ eil101.tsp & 629 & 630 & 644 & 648 & 0.16 & 2.38 & 3.02 \\ fri26.tsp & 937 & 937 & 937 & 940 & 0.00 & 0.00 & 0.32 \\ gil262.tsp & 2378 & 2432 & 2505 & 2497 & 2.27 & 5.34 & 5.00 \\ gr17.tsp & 2085 & 2085 & 2085 & 2086 & 0.00 & 0.00 & 0.05 \\ gr21.tsp & 2707 & 2707 & 2707 & 2707 & 0.00 & 0.00 & 0.00 \\ \hline
**Average** & **253944.1262** & **272756.94** & **277586.89** & **273027.78** & **3.55** & **4.49** & **4.24** \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Results using the Best Improvement search strategy and an execution time limit of 2 min. Tables 9-12 contain the aggregated experimental results for the National TSP instances. They contain the benchmark name, the optimal value (zOpt), the cost of the three GVNS algorithms (GVNS_1, GVNS_2 and GVNS_3) and the solution gaps from the optimal value for each method. Table 9 depicts GVNS using the First Improvement search strategy and an execution time limit of 1 min. Table 10 shows GVNS using the Best Improvement search strategy and an execution time limit of 1 min.