## 5 Experimental Results
### GVNS versus Nearest Neighbor Variants  
In addition to the previous setup, we ran additional tests using the two most popular variants of the NN heuristic. These are the _repeated_ NN and the _improved_ NN. The Improved NN is a variant of the classic NN in which the starting pair of the route is the shortest edge in the distance matrix [42]. The remaining nodes are added to the route in a way identical to the simple NN method. Repeated or repetitive NN is another modification in which the NN algorithm is applied to every node. Finally, the route with the minimum total cost is selected as the best one. We compared GVNS with the improved NN and the repeated NN, and the experimental results are contained in Tables 2 and 3. These tables show the Benchmark Name, the improved NN tour cost, the repeated NN tour cost, the GVNS using BI tour cost, the GVNS using FI tour cost, and the Optimal Value (OV). For consistency, we ran the same experiments as before, but instead of the simple NN, we used the improved NN and the repeated NN, and we compared the results with GVNS and the OV. The improved NN and repeated NN achieve better results compared to the simple NN for each benchmark. However, the fact remains that GVNS using FI or using BI still outperforms these improved NN-based methods. Tables 2 and 3 confirm that GVNS using either BI or FI outperforms the improved NN and the repeated NN. Let us consider, for example, the benchmark _eil101_, which consists of 101 nodes. The computational results show that that the improved NN has a tour cost of 823, the repeated NN has a tour cost of 746, GVNS on first improvement has 649 and GVNS on best improvement has 647, while the optimal tour's cost Value is 629. It is clear that GVNS is marginally close to the OV and the gap between both versions of GVNS and both NN variants is relatively high. Other examples of benchmarks that highlight the superiority of GVNS are _bayg29_, _d198_, and _ch130_. Table 3 contains computational data that corroborate that GVNS performs better than the improved and the repeated NN. Characteristic examples are _gr229_, _lin105_, and _pr136_, which are benchmark instances of 229, 105, and 136 nodes, respectively. We can therefore conclude that GVNS is always close to the optimal value and clearly outperforms the NN variants. \begin{table}
\begin{tabular}{c c c c c c c} \hline
**Benchmark Name** & **NN** & **Gap** & **Gap GVNS** & **Gap GVNS** & **Gap GVNS** & **OV** \\
**Name** & **NN** & **NN vs. OV** & **GNN** & **BI vs. OV** & **GVNS FI** & **CV** \\ \hline lin105 & 20,356 & \(-\)0.4156 & 14,613 & \(-\)0.0163 & 14,607 & \(-\)0.0159 & 14,379 \\ lin318 & 54,019 & \(-\)0.2852 & 45,018 & \(-\)0.0711 & 45,179 & \(-\)0.0749 & 42,029 \\ pcb442 & 61,979 & \(-\)0.2205 & 55,416 & \(-\)0.0913 & 55,804 & \(-\)0.0990 & 50,778 \\ pr76 & 153,462 & \(-\)0.4188 & 109,103 & \(-\)0.0087 & 109,421 & \(-\)0.0117 & 108,159 \\ pr107 & 46,680 & \(-\)0.0536 & 45,183 & \(-\)0.0199 & 45,464 & \(-\)0.0262 & 44,303 \\ pr124 & 69,297 & \(-\)0.1739 & 59,705 & \(-\)0.0114 & 59,742 & \(-\)0.0121 & 59,030 \\ pr136 & 120,769 & \(-\)0.2479 & 99,622 & \(-\)0.0295 & 100,718 & \(-\)0.0408 & 96,772 \\ pr144 & 61,652 & \(-\)0.0532 & 58,776 & \(-\)0.0041 & 58,991 & \(-\)0.0078 & 58,537 \\ pr152 & 85,699 & \(-\)0.1630 & 74,703 & \(-\)0.0139 & 74,943 & \(-\)0.0171 & 73,682 \\ pr226 & 94,683 & \(-\)0.1781 & 81,379 & \(-\)0.0126 & 81,781 & \(-\)0.0176 & 80,369 \\ \hline \end{tabular}
\end{table} 
Table 1: _Cont._