# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure
#### 5.2.2 TSPLIB Instances

We have then run the same type of experiment on instances from the TSPLIB. For each instance, we generated 1000 random starting tours and found the best 3-OPT move. The results are reported in Table 4. The instances are all the Euclidean, Geographical and Explicit instances (according to TSPLIB categories) with sizes up to 6000 nodes. Smaller-size instances were ignored since the running times are too little, for both SF and BF, even to be measured precisely. Indeed, for \(n\leq 200\) finding the best move by SF yields only a small advantage (in the running time) over the BF approach. The effect increases with increasing \(n\), and we can get about a factor-50 speed-up for instances with \(3000\leq n\leq 6000\). The largest improvement is achieved on one instance of size \(n=2319\) where SF is 77 times faster than BF, and finds the best move in about two seconds versus two and a half minutes. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Type** & **Name** & **Size** & \multicolumn{4}{c}{**Time (S)**} & \multicolumn{4}{c}{**Number of Evaluated Triples**} \\ \hline  & & & **BF\_avg** & **SF\_avg** & **Speed-up** & **BF** & **SF\_avg** & **Reduction** \\ \hline euc2d & kroA100 & 100 & 0.01 & 0.01 & 1\(\times\) & 608,000 & 33,124 & 18\(\times\) \\ euc2d & kroB100 & 100 & 0.01 & 0.01 & 1\(\times\) & 608,000 & 34,449 & 17\(\times\) \\ euc2d & kroC100 & 100 & 0.01 & 0.01 & 1\(\times\) & 608,000 & 36,688 & 16\(\times\) \\ euc2d & kroD100 & 100 & 0.01 & 0.01 & 1\(\times\) & 608,000 & 28,025 & 21\(\times\) \\ euc2d & kroE100 & 100 & 0.01 & 0.01 & 1\(\times\) & 608,000 & 39,838 & 15\(\times\) \\ euc2d & rd100 & 100 & 0.01 & 0.01 & 1\(\times\) & 608,000 & 20,005 & 30\(\times\) \\ euc2d & eil101 & 101 & 0.01 & 0.01 & 1\(\times\) & 627,008 & 20,652 & 30\(\times\) \\ euc2d & lin105 & 105 & 0.01 & 0.01 & 1\(\times\) & 707,000 & 38,662 & 18\(\times\) \\ euc2d & pr107 & 107 & 0.01 & 0.01 & 1\(\times\) & 749,428 & 99,522 & 7\(\times\) \\ explicit & gr120 & 120 & 0.02 & 0.01 & 2\(\times\) & 1,067,200 & 52,980 & 20\(\times\) \\ euc2d & pr124 & 124 & 0.02 & 0.01 & 2\(\times\) & 1,180,480 & 46,661 & 25\(\times\) \\ euc2d & bier127 & 127 & 0.02 & 0.01 & 2\(\times\) & 1,270,508 & 57,122 & 22\(\times\) \\ euc2d & ch130 & 130 & 0.02 & 0.01 & 2\(\times\) & 1,365,000 & 31,714 & 43\(\times\) \\ euc2d & pr136 & 136 & 0.02 & 0.01 & 2\(\times\) & 1,567,808 & 58,883 & 26\(\times\) \\ geo & gr137 & 137 & 0.02 & 0.01 & 2\(\times\) & 1,603,448 & 86,440 & 18\(\times\) \\ euc2d & pr144 & 144 & 0.02 & 0.01 & 2\(\times\) & 1,868,160 & 51,295 & 36\(\times\) \\ euc2d & ch150 & 150 & 0.02 & 0.01 & 2\(\times\) & 2,117,000 & 47,146 & 44\(\times\) \\ euc2d & kroA150 & 150 & 0.02 & 0.01 & 2\(\times\) & 2,117,000 & 93,533 & 22\(\times\) \\ euc2d & kroB150 & 150 & 0.02 & 0.01 & 2\(\times\) & 2,117,000 & 120,822 & 17\(\times\) \\ euc2d & pr152 & 152 & 0.02 & 0.01 & 2\(\times\) & 2,204,608 & 63,987 & 34\(\times\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparing SF and BF in finding one Best Improving move on Traveling Salesman Problem Library (TSPLIB) instances starting from a random tour (averaged over 1000 attempts).