# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure
It turns out that, over all the signings of \(B\) and \(C\) and permutations of \(i_{1},i_{2},i_{3}\), there is only one possible reinsertion scheme, namely (see Figure 4)

\[r_{7}:=<A^{+},i_{3},B^{-},i_{2},C^{-},i_{1}>.\]

The value of a move \(((i_{1},i_{2},i_{3}),r_{7})\) is \(\Delta((i_{1},i_{2},i_{3}),r_{7})=\)

\[ \begin{array}{l}=[c(i_{1}\ominus 1,i_{1})+c(i_{1},i_{1}\oplus 1)+c(i_{2} \odot 1,i_{2})+c(i_{2},i_{2}\oplus 1)+c(i_{3}\odot 1,i_{3})+c(i_{3},i_{3}\oplus 1)]-\\ \qquad[c(i_{1},i_{2}\oplus 1)+c(i_{1},i_{3}\oplus 1)+c(i_{2},i_{1}\oplus 1)+c(i_{2},i_{3} \ominus 1)+c(i_{3},i_{1}\ominus 1)+c(i_{3},i_{2}\ominus 1)]\\ =[\tau^{+}(i_{1},i_{2})+\tau^{+}(i_{2},i_{1})]+[\tau^{-}(i_{2},i_{3})+\tau^{-}(i_ {3},i_{2})]+[\tau^{+}(i_{1}\ominus 1,i_{3}\ominus 1)+\tau^{-}(i_{3}\oplus 1,i_{1}\oplus 1)]\\ =f_{77}^{12}(i_{1},i_{2})+f_{77}^{23}(i_{2},i_{3})++f_{77}^{13}(i_{1},i_{3}), \end{array} \]

where we have defined the three functions \(f_{7}^{\alpha}\) as

\[\begin{array}{l}fTo finish this section let us consider another type of cubic move, for example, a special 5-OPT move. In particular, let the removed edges be

\[\{i_{1}\ominus 1,i_{1}\},\ \{i_{1},i_{1}\ominus 1\},\ \{i_{2}\ominus 1,i_{2}\},\ \{i_{2},i_{2}\oplus 1\},\ \{i_{3},i_{3}\oplus 1\}.\]

The tour is then reconnected in any way that excludes the removed edges (clearly there are many possibilities, we will just look at one of them). By using the previous notation for the reinsertion schemes, let us consider the scheme (see Figure 4)

\[r_{9}:=<A^{+},i_{2},B^{+},i_{1},C^{-}>.\]

The value of a move \(((i_{1},i_{2},i_{3}),r_{9})\) is \(\Delta((i_{1},i_{2},i_{3}),r_{9})=\)

\[= [c(i_{1}\ominus 1,i_{1})+c(i_{1},i_{1}\oplus 1)+c(i_{2}\ominus 1,i_ {2})+c(i_{2},i_{2}\oplus 1)+c(i_{3},i_{3}\oplus 1)]-\] \[[c(i_{1}\ominus 1,i_{2})+c(i_{1},i_{2}\ominus 1)+c(i_{1}\oplus 1,i_ {2})+c(i_{2}\oplus 1,i_{3}\oplus 1)+c(i_{3},i_{1})]\] \[= [\tau^{-}(i_{1}\ominus 1,i_{2}\oplus 1)+\tau^{+}(i_{1}\ominus 1,i_ {2}\ominus 1)+\tau^{+}(i_{2}\ominus 1,i_{1}\ominus 1)]+\tau^{-}(i_{2}\oplus 1,i_ {3}+2)+\tau^{+}(i_{3},i_{1}\ominus 1)\] \[= f_{r_{9}}^{12}(i_{1},i_{2})+f_{r_{9}}^{23}(i_{2},i_{3})+f_{r_{9} }^{13}(i_{1},i_{3}),\]

where we have defined the three functions \(f_{r}^{\alpha}\) as

\[ \begin{array}{l}f_{r_{9}}^{12}:(x,y)\in\mathcal{S}_{12}\mapsto\tau^{-}(x \oplus 1,y\oplus 1)+\tau^{+}(x\ominus 1,y\ominus 1)+\tau^{+}(y\ominus 1,x\ominus 1)\\ f_{r_{9}}^{23}:(x,y)\in\mathcal{S}_{23}\mapsto\tau^{-}(x\oplus 1,y\ominus 2)\\ f_{r_{9}}^{13}:(x,y)\in\mathcal{S}_{13}\mapsto\tau^{+}(y,x\ominus 1)\end{array} \]

It should be clear that, to find the best move of the special types described in this section, we can put the partial moves in a heap and use the same strategy we have developed in Section 4. The algorithm is the same as before, with the difference that in line 2 of procedure BuildHeap we iterate over the schemes \(r_{5},\ldots,r_{9}\) instead of \(r_{1},\ldots,r_{4}\). ## 7 Conclusions

In this work, we have described an algorithmic strategy for optimizing the 3-OPT neighborhood in an effective way. Our strategy relies on a particular order of enumeration of the triples which allows us to find the best 3-OPT move without having to consider all the possibilities. This is achieved by a pruning rule and by the use of the max-heap as a suitable data structure for finding in a quick way good candidates for the best move. Extensive computational experiments prove that this strategy largely outperforms the classical \(\Theta(n^{3})\) \"nested-for\" approach on average. In particular, our approach exhibits a time complexity bounded by \(O(n^{2.5})\) on various types of random graphs. The goal of our work was to show how the use of the 3-OPT neighborhood can be extended to graphs of much larger size than before. We did not try to assess the effectiveness of this neighborhood in finding good-quality tours, nor possible refinements to 3-OPT local search (such as restarts, perturbations, the effectiveness of the other type of 3-OPT moves we introduced, etc.).