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, ..., 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.…

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, ..., 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

References

Further reading

Text derived from https://en.wikipedia.org/w/index.php?oldid=1341143907 under CC BY-SA 4.0; modifications have been made.