# Finding the Best 3-OPT Move in Subcubic Time
## 4 Searching the 3-OPT Neighborhood
### Implementing the Search Procedure
\begin{array}{l}f_{75}^{12}:(x,y)\in\mathcal{S}_{12}\mapsto\tau^{+}(y,x)+\tau^{-} (y,x)\\ f_{75}^{23}:(x,y)\in\mathcal{S}_{23}\mapsto\tau^{+}(y,x)+\tau^{-}(y,x)\\ f_{75}^{13}:(x,y)\in\mathcal{S}_{13}\mapsto\tau^{+}(x,y)+\tau^{-}(x,y)\\ \end{array} \]

Similarly, a move \(((i_{1},i_{2},i_{3}),r_{6})\) has value \(\Delta((i_{1},i_{2},i_{3}),r_{6})=\)

\[ \begin{array}{l}=[c(i_{1}\odot 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}\odot 1)+c(i_{1},i_{2}\oplus 1)+c(i_{2},i_{3}\odot 1)+c(i_{ 2},i_{3}\oplus 1)+c(i_{3},i_{1}\oplus 1)+c(i_{3},i_{1}\oplus 1)]\\ =[\tau^{+}(i_{1},i_{2})+\tau^{-}(i_{1},i_{2})]+[\tau^{+}(i_{2},i_{3})+\tau^{-} (i_{2},i_{3})]+[\tau^{+}(i_{3},i_{1})+\tau^{-}(i_{3},i_{1})]\\ =f_{76}^{12}(i_{1},i_{2})+f_{76}^{23}(i_{2},i_{3})+f_{76}^{13}(i_{1},i_{3}), \end{array} \]

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

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

Let us now consider the case of the above move when we keep the order \(A\), \(B\), \(C\), but we also allow for reversing either \(B\) or \(C\). 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}\odot 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}\odot 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_{r}^{\alpha}\) as

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

Finally, let us consider one last example of these special 6-OPT moves, in which we rearrange the permutation of segments and nodes, namely (see Figure 4)

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

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

\[ \begin{array}{l}=[c(i_{1}\odot 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}\odot 1,i_{3}\odot 1)+c(i_{1},i_{3})+c(i_{2}\odot 1,i_{3})+c(i_{ 2},i_{3}\oplus 1)+c(i_{1},i_{2})+c(i_{1}\oplus 1,i_{2}\oplus 1)]\\ =[\tau^{-}(i_{1}\oplus 1,i_{2}\oplus 2)+\tau^{-}(i_{2},i_{1}\oplus 1)]+[\tau^{+}(i_{ 2},i_{3})+\tau^{-}(i_{3},i_{2})]+[\tau^{+}(i_{1}\ominus 1,i_{3}\ominus 2)+\tau^{+}(i_{3},i_{1} \ominus 1)]\\ =f_{78}^{12}(i_{1},i_{2})+f_{78}^{23}(i_{2},i_{3})++f_{78}^{13}(i_{1},i_{3}), \end{array} \]

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

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

Let us now consider the case of the above move when we keep the order \(A\), \(B\), \(C\), but we also allow for reversing either \(B\) or \(C\).