# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline
**Type** & **Size** & \multicolumn{4}{c}{**Time (S)**} & \multicolumn{4}{c}{**Number of Evaluated Triples**} & \multicolumn{4}{c}{**Ratio Against the Previous Size**} \\ \hline  & & **BF\_avg** & **SF\_avg** & **Speed-up** & **BF** & **SF\_avg** & **Reduction** & **SF\_time** & **SF\_eval** & **BF\_time** & **BF\_eval** \\ \hline  & 400 & 0.65 & 0.01 & 75\(\times\) & 41,712,000 & 177,247 & 235\(\times\) & & & & \\  & 566 & 1.80 & 0.01 & 136\(\times\) & 118,966,408 & 352,174 & 337\(\times\) & 1.53 & 1.98 & 2.79 & 2.85 \\  & 800 & 5.08 & 0.03 & 187\(\times\) & 337,50



\begin{table}
\begin{tabular}{l l c c c c c c c} \hline \hline
**Type** & **Name** & **Size** & \multicolumn{3}{c}{**Time (S)**} & \multicolumn{3}{c}{**Number of Evaluated Triples**} \\ \hline  & & & **BF\_avg** & **SF\_avg** & **Speed-up** & **BF** & **SF\_avg** & **Reduction** \\ \hline euc2d & u159 & 159 & 0.03 & 0.01 & 3\(\times\) & 2,530,220 & 127,254 & 19\(\times\) \\ explicit & si175 & 175 & 0.03 & 0.01 & 3\(\times\) & 3,391,500 & 48,981 & 69\(\times\) \\ explicit & brg180 & 180 & 0.03 & 0.01 & 3\(\times\) & 3,696,000 & 33,125 & 111\(\times\) \\ euc2d & rat195 & 195 & 0.05 & 0.01 & 5\(\times\) & 4,717,700 & 196,516 & 24\(\times\) \\ euc2d & d198 & 198 & 0.04 & 0.02 & 2\(\times\) & 4,942,344 & 483,916 & 10\(\times\) \\ euc2d & kroA200 & 200 & 0.04 & 0.01 & 4\(\times\) & 5,096,000 & 221,364 & 23\(\times\) \\ euc2d & kroB200 & 200 & 0.04 & 0.01 & 4\(\times\) & 5,096,000 & 189,160 & 26\(\times\) \\ geo & gr202 & 202 & 0.04 & 0.01 & 4\(\times\) & 5,252,808 & 150,173 & 34\(\times\) \\ euc2d & ts225 & 225 & 0.05 & 0.01 & 5\(\times\) & 7,293,000 & 110,879 & 65\(\times\) \\ euc2d & tsp225 & 225 & 0.05 & 0.01 & 5\(\times\) & 7,293,000 & 141,260 & 51\(\times\) \\ euc2d & pr226 & 226 & 0.06 & 0.01 & 6\(\times\) & 7,392,008 & 215,307 & 34\(\times\) \\ geo & gr229 & 229 & 0.06 & 0.01 & 6\(\times\) & 7,694,400 & 233,132 & 33\(\times\) \\ euc2d & gil262 & 262 & 0.09 & 0.01 & 9\(\times\) & 11,581,448 & 190,348 & 60\(\times\) \\ euc2d & pr264 & 264 & 0.09 & 0.03 & 3\(\times\) & 11,851,840 & 1,248,519 & 9\(\times\) \\ euc2d & a280 & 280 & 0.10 & 0.02 & 5\(\times\) & 14,168,000 & 465,152 & 30\(\times\) \\ euc2d & pr299 & 299 & 0.12 & 0.02 & 6\(\times\) & 17,288,180 & 696,974 & 24\(\times\) \\ euc2d & lin318 & 318 & 0.17 & 0.02 & 8\(\times\) & 20,835,784 & 408,556 & 50\(\times\) \\ euc2d & rd400 & 400 & 0.31 & 0.02 & 15\(\times\) & 41,712,000 & 579,874 & 71\(\times\) \\ euc2d & fl417 & 417 & 0.37 & 0.09 & 4\(\times\) & 47,303,368 & 5,164,545 & 9\(\times\) \\ euc2d & pr439 & 439 & 0.38 & 0.03 & 12\(\times\) & 55,252,540 & 1,528,226 & 36\(\times\) \\ euc2d & pcb442 & 442 & 0.43 & 0.03 & 14\(\times\) & 56,400,968 & 759,689 & 74\(\times\) \\ euc2d & d493 & 493 & 0.60 & 0.06 & 10\(\times\) & 78,430,384 & 3,381,605 & 23\(\times\) \\ explicit & si535 & 535 & 0.73 & 0.07 & 10\(\times\) & 100,376,700 & 4,008,177 & 25\(\times\) \\ geo & ali535 & 535 & 0.84 & 0.05 & 16\(\times\) & 100,376,700 & 2,472,210 & 40\(\times\) \\ explicit & pa561 & 561 & 1.11 & 0.03 & 37\(\times\) & 115,824,808 & 1,041,688 & 111\(\times\) \\ euc2d & u574 & 574 & 1.08 & 0.05 & 21\(\times\) & 124,110,280 & 2,914,483 & 42\(\times\) \\ euc2d & rat575 & 575 & 0.93 & 0.08 & 11\(\times\) & 124,763,500 & 3,654,861 & 34\(\times\) \\ euc2d & p654 & 654 & 1.29 & 0.36 & 3\(\times\) & 183,926,600 & 27,434,417 & 6\(\times\) \\ euc2d & d657 & 657 & 1.37 & 0.05 & 27\(\times\) & 186,481,128 & 2,548,932 & 73\(\times\) \\ geo & gr666 & 666 & 1.42 & 0.07 & 20\(\times\) & 194,866,408 & 4,045,491 & 48\(\times\) \\ euc2d & u724 & 724 & 1.86 & 0.09 & 20\(\times\) & 249,866,880 & 5,334,184 & 46\(\times\) \\ euc2d & rat783 & 783 & 2.41 & 0.13 & 18\(\times\) & 316,364,364 & 8,343,380 & 37\(\times\) \\ euc2d & pr1002 & 1002 & 6.91 & 0.24 & 28\(\times\) & 664,664,008 & 11,357,581 & 58\(\times\) \\ explicit & si1032 & 1032 & 8.01 & 0.10 & 80\(\times\) & 726,360,128 & 2,854,805 & 254\(\times\) \\ euc2d & u1060 & 1060 & 8.90 & 0.60 & 14\(\times\) & 787,283,200 & 31,809,054 & 24\(\times\) \\ euc2d & vm1084 & 1084 & 9.88 & 0.42 & 23\(\times\) & 842,137,920 & 19,784,522 & 42\(\times\) \\ euc2d & pcb1173 & 1173 & 13.46 & 0.31 & 43\(\times\) & 1,067,736,544 & 12,760,475 & 83\(\times\) \\ euc2d & tl291 & 1291 & 19.35 & 0.39 & 49\(\times\) & 1,424,473,908 & 14,188,288 & 100\(\times\) \\ euc2d & rl1304 & 1304 & 20.30 & 0.46 & 44\(\times\) & 1,468,043,200 & 16,276,240 & 90\(\times\) \\ euc2d & rl1323 & 1323 & 21.15 & 0.51 & 41\(\times\) & 1,533,305,844 & 18,847,965 & 81\(\times\) \\ euc2d & rwr1379 & 1379 & 24.52 & 0.89 & 27\(\times\) & 1,736,850,500 & 34,849,494 & 49\(\times\) \\ euc2d & fl1400 & 1400 & 25.92 & 6.93 & 3\(\times\) & 1,817,592,000 & 243,306,185 & 7\(\times\) \\ euc2d & u1432 & 1432 & 27.88 & 0.67 & 41\(\times\) & 1,945,377,728 & 25,930,124 & 75\(\times\) \\ euc2d & fl1577 & 1577 & 39.56 & 0.93 & 42\(\

### Experiment 2: Convergence to a Local Optimum

#### 5.3.1 Random Instances

A second set of experiments concerned the behavior of our algorithm over a sequence of iterations, i.e., in a full local search convergence starting from a random tour until a local optimum is reached.