## 3 Computational Analysis
### Computational Results  
This section presents the computational results of the different perturbation strategies for each class of experiments. The GVNS schemes with the different shaking methods were applied on TSPLIB instances. The TSP is one of the most famous NP-hard combinatorial optimization problems. Solving the TSP means finding the minimum cost route so that the salesman starts from a particular node and returns to that node after passing from all the other nodes once. All experiments were executed 5 times and the average value of all runs was computed. Tables 1 and 2 contain the aggregated experimental results. Specifically, they show the benchmark name, the optimal value (zOpt), the cost of the three GVNS schemes (GVNS_1, GVNS_2 and GVNS_3) and their corresponding gaps from the optimal value. The results depicted in Table 1 were obtained using the First Improvement search strategy and an execution time limit of 1 min, whereas the results in Table 2 were obtained using the Best Improvement search strategy and the same execution time of 1 min. As mentioned earlier, the cost of each GVNS scheme is the average of 5 runs for each problem. The reported gap is computed as follows: given the outcome \(x\), its gap from the optimal value \(OV\) is given by the formula \(\frac{100\times(x-OV)}{OV}\). The results in Table 1 indicate a definite pattern, namely that both GVNS_1 and GVNS_2 outperform GVNS_3 in most cases. Recall that GVNS_3 is a shuffle perturbation strategy. For example, consider benchmark ftv47; we can see that the cost of GVNS_1 is 1821, the cost of GVNS_2 is 1992 and of GVNS_3 is 2101. GVNS_1 and GVNS_2 both outperform GVNS_3 and are also relatively close to the optimal value (1778). \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 \\ _fb53.atsp_ & 6905 & 7189 & 7328 & 7737 & 4.11 & 6.13 & 12.05 \\ _fb70.atsp_ & 38673 & 39782 & 40691 & 40537 & 2.87 & 5.22 & 4.82 \\ _fb733.atsp_ & 1286 & 1318 & 1339 & 1450 & 2.49 & 4.12 & 12.75 \\ _fb735.atsp_ & 1473 & 1484 & 1499 & 1596 & 0.75 & 1.77 & 8.35 \\ _fb738.atsp_ & 1530 & 1546 & 1585 & 1579 & 1.05 & 3.59 & 3.20 \\ _fb744.atsp_ & 1613 & 1651 & 1760 & 1797 & 2.36 & 9.11 & 11.41 \\ _fb747.atsp_ & 1778 & 1821 & 1992 & 2101 & 2.42 & 12.04 & 18.17 \\ _fb55.atsp_ & 1608 & 1666 & 1985 & 1912 & 3.61 & 23.45 & 18.91 \\ _fb764.atsp_ & 1839 & 1961 & 2382 & 2395 & 6.63 & 29.53 & 30.23 \\ _fb70.atsp_ & 1950 & 2136 & 2557 & 2484 & 9.54 & 31.13 & 27.38 \\ _fb710.atsp_ & 2755 & 3487 & 3923 & 3923 & 26.57 & 42.40 & 42.40 \\ _bro124p.atsp_ & 36230 & 39024 & 43187 & 40259 & 7.71 & 19.20 & 11.12 \\ _pd3.atsp_ & 5620 & 5620 & 5623 & 5658 & 0.00 & 0.05 & 0.68 \\ _rb323.atsp_ & 1325 & 1516 & 1563 & 1626 & 14.32 & 17.87 & 22.62 \\ _rb358.atsp_ & 1163 & 1347 & 1437 & 1404 & 15.82 & 23.55 & 20.72 \\ _rbg403.atsp_ & 2465 & 2535 & 2587 & 2565 & 9.78 & 4.42 & 11.76 \\ _rbg443.atsp_ & 2720 & 2814 & 2859 & 2814 & 3.46 & 5.11 & 3.46 \\ _ry48p.atsp_ & 14422 & 14549 & 14901 & 14738 & 0.88 & 3.32 & 2.19 \\ \hline
**Average** & **6599.74** & **6920.26** & **7328.37** & **7190.21** & **12.33** & **12.64** & **24.10** \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The results shown here were obtained using the First Improvement search strategy and an execution time limit of 1 min [14]. In addition, the provided results in Table 2 lead to the same statement that both GVNS_1 and GVNS_2 produce better results than GVNS_3 in most cases. Table 3 shows the results of the GVNS schemes within a 2 min run time limit and the First Improvement as search strategy. The results of Table 3 mention that GVNS_1 outperform GVNS_2 and GVNS_3 in most cases. However, the main difference from the results of Tables 1 and 2 is that now the behavior of GVNS_2 is closer to that of GVNS_3 solution approach.