3-opt

In optimization, 3-opt is a simple local search heuristic for finding approximate solutions to the travelling salesperson problem and related network optimization problems. Compared to the simpler 2-opt algorithm, it is slower but can generate higher-quality solutions.

3-opt analysis involves deleting three edges from the current solution to the problem, creating three sub-tours. There are eight ways of connecting these sub-tours back into a single tour, one of which consists of the three deleted edges. These reconnections are analysed to find the optimum one. This process is then repeated for a different set of 3 connections, until all possible combinations have been tried in a network. A single pass through all triples of edges has a time complexity of $O(n^3)$. Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity.

In an array representation of a tour with $k$ nodes $S=[n_0,n_1,n_2,\mathrm{...},n_{k-1},n_k]$, where $n_0=n_k$, deleting three edges separates $S$ into four segments $S_1$, $S_2$, $S_3$ and $S_4$. Note that the segments $S_1$ and $S_4$ are connected. The reconnection of the Subtours is done by a combination of reversing one or both of $S_2$ and $S_3$ and switching their respective positions. The 8 possible new tours are $[S_1,S_2,S_3,S_4]$, $[S_1,\overleftrightarrow{S_2},S_3,S_4]$, $[S_1,S_2,\overleftrightarrow{S_3},S_4]$, $[S_1,\overleftrightarrow{S_2},\overleftrightarrow{S_3},S_4]$, $[S_1,S_3,S_2,S_4]$, $[S_1,\overleftrightarrow{S_3},S_2,S_4]$, $[S_1,S_3,\overleftrightarrow{S_2},S_4]$ and $[S_1,\overleftrightarrow{S_3},\overleftrightarrow{S_2},S_4]$. Here $\overleftrightarrow{S_i}$ indicates that segment $i$ is reversed.

See also

• 2-opt
• Local search
• Lin–Kernighan heuristic