# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure
per move** & \\ \hline
1131 & BF time & 13,920 & 13,840 & 13,840 & 13,900 & 13,940 & 13,930 & 13,930 & 14,030 & 13,890 & 13,810 & 14,502.100 & 13.904 & \\  & SF time & 170 & 170 & 170 & 170 & 190 & 200 & 210 & 220 & 230 & 240 & 204.559 & 0.196 & 70\(\times\) \\  & SF heap & 162,645 & 161,897 & 134,756 & 124,316 & 82,993 & 49,690 & 31,861 & 22,490 & 17,348 & 14,658 & & & \\  & SF exps & 5223 & 5135 & 5164 & 4960 & 6297 & 7158 & 8025 & 8955 & 9613 & 10,466 &



That is, for each convergence \(i=1,\ldots,100\) and step \(k=1,\ldots,100\) we have determined \(h_{k}^{i}\) (the average heap size in the interval from \(k-1\) to \(k\) percent of the \(i\)-th convergence), \(e_{k}^{i}\) (the average number of expansions in the same interval) and \(i_{k}^{i}\) (the average time for a move in the interval). Once all the convergences have been normalized to have the same length, we have taken the average of values \(h,e\) and \(t\) over all convergences in each of the 100 intervals. For each interval \(k\), let \(\bar{h}_{k}\) be the average of \(h_{k}^{i}\) over all \(i\), and define similarly the averages \(\bar{e}_{k}\) and \(\bar{t}_{k}\). The plots of \(\bar{h}\), \(\bar{e}\) and \(\bar{t}\) are shown in Figure 3. The \(x\) axis is labeled by the 100 intervals. The \(y\)-axis is labeled by the number of elements (left) and by the time in seconds (right). It can be seen that the heap size starts by staying more or less constant for about 20% of the convergence and then starts to rapidly decrease (with the exception of a peak at around 40%). The number of expansions stays more or less constant for about one-third of the convergence and then starts to increase in a linear fashion. The time for each move follows a similar curve, since \(\bar{t}\) is proportional (with a factor \(n\)) to \(\bar{e}\). The two curves for \(\bar{h}\) and \(\bar{e}\) approach each other until they almost touch at the end, when, basically, all of the heap elements must be expanded and pruning is ineffective. Overall, as shown by Table 4, the use of SF over BF allows for speed-up factors of about two orders of magnitude on instances of 1600 nodes. #### 5.3.2 TSPLIB Instances

We then performed the same type of experiment on the TSPLIB instances previously described. For each instance we ran a local search all to way to convergence to a local optimum, starting from 100 random tours. The results are reported in Table 6. This type of experiment is extremely time-consuming when BF is run on large graphs. For this reason, not all the times for BF are actual real values, but the results for graphs with \(n\geq 3000\) are actually estimates of the running times. In particular, when \(n\geq 3000\), BF would have to evaluate more than 18 billion triples at each move. Say the exact number is \(T_{n}\). Then we only evaluate the first \(T_{0}:=100,000,000\) triples. Assume this takes time \(t_{0}\) (usually less

Figure 3: Uniform (UNI) n = 1600, averages on 100 convergences, each of 100 steps (obtained by normalizing convergences of different lengths). than 2 s on our computer). Then we estimate the actual time of a move as \(t_{n}:=t_{0}(T_{n}/T_{0})\). This is indeed a lower bound since in computing \(t_{0}\) we do not account for updates to the current best triple (i.e., we removed the if and its body from the nested for loop of BF). From Table 6 we can see that SF outperforms BF with improvements that range from 500% faster to more than 20,000% faster (instance pcb3038). These improvements are smaller than those for random graphs, but still, the experiment shows how with our method it is now possible to run a local search by using the 3-OPT neighborhood on TSPLIB instances that were previously impossible to tackle. For instance, reaching a 3-OPT local optimum for pcb3038 with the BF nested-for procedure would have taken at least two weeks (!)