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 ${\displaystyle O(n^{3})}$.^[1] 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 ${\displaystyle k}$ nodes ${\displaystyle S=[n_{0},n_{1},n_{2},...,n_{k-1},n_{k}]}$, where ${\displaystyle n_{0}=n_{k}}$, deleting three edges separates ${\displaystyle S}$ into four segments ${\displaystyle S_{1}}$, ${\displaystyle S_{2}}$, ${\displaystyle S_{3}}$ and ${\displaystyle S_{4}}$. Note that the segments ${\displaystyle S_{1}}$ and ${\displaystyle S_{4}}$ are connected. The reconnection of the Subtours is done by a combination of reversing one or both of ${\displaystyle S_{2}}$ and ${\displaystyle S_{3}}$ and switching their respective positions. The 8 possible new tours are ${\displaystyle [S_{1},S_{2},S_{3},S_{4}]}$, ${\displaystyle [S_{1},{\overleftrightarrow {S_{2}}},S_{3},S_{4}]}$, ${\displaystyle [S_{1},S_{2},{\overleftrightarrow {S_{3}}},S_{4}]}$, ${\displaystyle [S_{1},{\overleftrightarrow {S_{2}}},{\overleftrightarrow {S_{3}}},S_{4}]}$, ${\displaystyle [S_{1},S_{3},S_{2},S_{4}]}$, ${\displaystyle [S_{1},{\overleftrightarrow {S_{3}}},S_{2},S_{4}]}$, ${\displaystyle [S_{1},S_{3},{\overleftrightarrow {S_{2}}},S_{4}]}$ and ${\displaystyle [S_{1},{\overleftrightarrow {S_{3}}},{\overleftrightarrow {S_{2}}},S_{4}]}$. Here ${\displaystyle {\overleftrightarrow {S_{i}}}}$ indicates that segment ${\displaystyle i}$ is reversed.

See also

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