## 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 ar9152.tsp & 837479 & 1317886 & 1648596 & 1648596 & 57.36 & 96.85 & 96.85 \\ gr9882.tsp & 300899 & 368968 & 388944 & 388944 & 22.62 & 29.26 & 29.26 \\ eg7146.tsp & 172387 & 206756 & 220315 & 220315 & 19.94 & 27.80 & 27.80 \\ fi10639.tsp & 520527 & 625547 & 649604 & 649604 & 20.18 & 24.80 & 24.80 \\ ho14473.tsp & 177105 & 362827 & 484812 & 459459 & 104.87 & 173.74 & 159.43 \\ ei8246.tsp & 206171 & 246249 & 258889 & 258889 & 19.44 & 25.57 & 25.57 \\ ja9847.tsp & 491924 & 595913 & 612304 & 612304 & 21.14 & 24.47 & 24.47 \\ kz9976.tsp & 1061882 & 1296253 & 1358247 & 1358247 & 22.07 & 27.91 & 27.91 \\ lu980.tsp & 11340 & 12052 & 12388 & 12530 & 6.28 & 9.24 & 10.49 \\ mo14185.tsp & 427377 & 514995 & 529729 & 529729 & 20.50 & 23.95 & 23.95 \\ nu3496.tsp & 96132 & 108839 & 108639 & 108685 & 13.22 & 13.01 & 13.06 \\ mu1979.tsp & 86891 & 93453 & 95413 & 93433 & 7.55 & 9.81 & 7.53 \\ qa194.tsp & 9352 & 9468 & 9717 & 9791 & 1.24 & 3.90 & 4.69 \\ rw1621.tsp & 26051 & 28360 & 28866 & 29127 & 8.86 & 10.81 & 11.81 \\ tz6117.tsp & 394718 & 478074 & 483082 & 445901 & 21.12 & 22.39 & 12.97 \\ uy734.tsp & 79114 & 83595 & 86201 & 84628 & 5.66 & 8.96 & 6.97 \\ wi29.tsp & 27603 & 27603 & 27603 & 27603 & 0.00 & 0.00 & 0.00 \\ ym7663.tsp & 238314 & 291939 & 308747 & 308747 & 22.50 & 29.55 & 29.55 \\ zi929.tsp & 95345 & 100461 & 103557 & 100474 & 5.37 & 8.61 & 5.38 \\ ca4663.tsp & 1290319 & 1532650 & 1463565 & 1428402 & 18.78 & 13.43 & 10.70 \\ \hline
**Average** & **327546.50** & **415094.40** & **443960.90** & **438770.40** & **20.93** & **29.20** & **27.66** \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Results using the Best Improvement search strategy and an execution time limit of 1 min. \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 ar9152.tsp & 837479 & 1648304 & 1648596 & 1648596 & 96.82 & 96.85 & 96.85 \\ gr9882.tsp & 300899 & 388916 & 388944 & 388944 & 29.25 & 29.26 & 29.26 \\ eg7146.tsp & 172387 & 220290 & 220315 & 220315 & 27.79 & 27.80 & 27.80 \\ fi10639.tsp & 520527 & 649604 & 649604 & 24.80 & 24.80 & 24.80 \\ ho14473.tsp & 177105 & 484793 & 484812 & 484812 & 173.73 & 173.74 & 173.74 \\ ei8246.tsp & 206171 & 258867 & 258889 & 258889 & 25.56 & 25.57 & 25.57 \\ ja9847.tsp & 491924 & 612304 & 612304 & 612304 & 24.47 & 24.47 \\ kz9976.tsp & 1061882 & 1358246 & 1358247 & 1358247 & 27.91 & 27.91 \\ lu980.tsp & 11340 & 20909 & 23688 & 14382 & 84.38 & 108.89 & 26.83 \\ mo14185.tsp & 427377 & 529699 & 529729 & 529729 & 23.94 & 23.95 & 23.95 \\ nu3496.tsp & 96132 & 221466 & 221920 & 221920 & 130.38 & 130.85 & 130.85 \\ mu1979.tsp & 86891 & 119586 & 120908 & 120908 & 37.63 & 39.15 & 39.15 \\ qa194.tsp & 9352 & 9543 & 9811 & 9731 & 2.04 & 4.91 & 4.05 \\ rw1621.tsp & 26051 & 56293 & 58148 & 58148 & 116.09 & 123.21 & 123.21 \\ tz6117.tsp & 394718 & 501137 & 501184 & 501184 & 26.96 & 26.97 & 26.97 \\ uy734.tsp & 79114 & 85036 & 99005 & 83383 & 7.49 & 25.14 & 5.40 \\ wi29.tsp & 27603 & 27603 & 27603 & 27701 & 0.00 & 0.00 & 0.36 \\ ym7663.tsp & 238314 & 308713 & 308747 & 308747 & 29.54 & 29.55 & 29.55 \\ zi929.tsp & 95345 & 104572 & 113927 & 101795 & 9.68 & 19.49 & 6.76 \\ ca4663.tsp & 1290319 & 1645854 & 1646889 & 1646889 & 27.55 & 27.63 & 27.63 \\ \hline
**Average** & **327546.50** & **462586.75** & **464163.50** & **462311.40** & **46.30** & **49.51** & **43.76** \\ \hline \hline \end{tabular}
\end{table} 
Table 11: Results using the First Improvement search strategy and an execution time limit of 2 min.