# An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour
## 4 Experimental Results and Analysis
### Experiment with \(R\&R\)  
In this section, we present the experimental results of the 2-Opt++ algorithm along with the results of the well-known ruin and recreate algorithm implemented as Jsprint using similar settings [25]. Each test case involved 10, 100, 500, 1000, and 2000 iterations to draw the graph for convergence. We ran both algorithms a fixed number of times for every TSP problem. Moreover, we also recorded the time taken by each algorithm to provide the results for each problem.  
In the case of the 2-Opt++ algorithm, for small problems comprising 50 to 500 nodes, we decided to run the algorithm on 2000 iterations and with a full active matrix, which means that each and every node was active in the graph. In Table 2, we provide the results after experimenting on both algorithms with the details of individual TSP problems. The error formula is defined as  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**No.** & **Name** & **2-Opt++** & **NN** & **No.** & **Name** & **2-Opt++** & **NN** \\ \hline
20 & pr144 & 0.53 & 5.32 & 53 & d1291 & 7.31 & 17.99 \\ \hline
21 & ch150 & 2.68 & 8.42 & 54 & rl1304 & 4.94 & 34.33 \\ \hline
22 & kroa150 & 2.95 & 26.71 & 55 & rl1323 & 5.41 & 22.91 \\ \hline
23 & krob150 & 1.67 & 25.62 & 56 & pr2392 & 7.74 & 22 \\ \hline
24 & pr152 & 4.32 & 16.31 & 57 & fl1400 & 4.1 & 34.01 \\ \hline
25 & u159 & 3.37 & 29.92 & 58 & u1432 & 8.06 & 23.43 \\ \hline
26 & rat195 & 6.94 & 18.9 & 59 & fl1577 & 3.72 & 25.58 \\ \hline
27 & d198 & 2.22 & 14.46 & 60 & d1655 & 8.14 & 20.55 \\ \hline
28 & kroa200 & 3.72 & 21.9 & 61 & vm1748 & 6.43 & 21.25 \\ \hline
29 & krob200 & 2.25 & 25.63 & 62 & u1817 & 7.92 & 24.3 \\ \hline
30 & ts225 & 2.29 & 20.41 & 63 & rl1889 & 4.49 & 26.58 \\ \hline
31 & tsp225 & 3.25 & 23.31 & 64 & d2103 & 5.27 & 8.72 \\ \hline
32 & pr226 & 0.66 & 17.81 & 65 & pla33810 & 9.24 & 17.08 \\ \hline
33 & gil262 & 3.26 & 36.31 & 66 & pla85900 & 10.14 & 22.23 \\ \hline \hline \end{tabular}
\end{table}
Table 4: _Cont._\[Error=((result\ -\ opt)\ /\ opt)\times 100 \tag{10}\]  
In 29 out of 35 selected benchmarked problems, belonging to the small category, the 2-Opt++ algorithm performed better than \(R\&R\). In six problems, \(R\&R\) outperformed the 2-Opt++ algorithm. However, a key aspect of the 2-Opt++ algorithm in comparison to \(R\&R\) is that the error variance never increases more than 7%, while the \(R\&R\) algorithm produces a sub-par 42.7% error margin for the problem pr107. It is also evident from the results that there are many cases where the error percentage of the results produced by \(R\&R\) is more than 18%. Moreover, if we look at the execution time factor, the 2-Opt++ algorithm outperforms \(R\&R\) by a fair margin while still producing notably better results for all the tested problems. It is also worth mentioning that after applying graph compression for up to 100 nodes, i.e., \(k=100\), the time taken by the 2-Opt++ algorithm is improved even further. It is also shown in Figure 5, that the \(R\&R\) algorithm performed so poorly in terms of the computation time for the larger problems that we had to abort the computation of results for larger problems for comparison's sake. However, we recorded the results for the 2-Opt++ algorithm for all categories and they are presented in Table 4, for future reference.