3-opt explained
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
.
[1] Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity.
See also
Further reading
- F. . BOCK . 1958 . An algorithm for solving traveling-salesman and related network optimization problems . Operations Research . 6 . 6.
- Lin . Shen . Computer Solutions of the Traveling Salesman Problem . Bell System Technical Journal . Institute of Electrical and Electronics Engineers (IEEE) . 44 . 10 . 1965 . 0005-8580 . 10.1002/j.1538-7305.1965.tb04146.x . 2245–2269.
- Lin . S. . Kernighan . B. W. . An Effective Heuristic Algorithm for the Traveling-Salesman Problem . Operations Research . Institute for Operations Research and the Management Sciences (INFORMS) . 21 . 2 . 1973 . 0030-364X . 10.1287/opre.21.2.498 . 498–516.
- Book: Sipser, Michael . Introduction to the theory of computation . Thomson Course Technology . Boston . 2006 . 0-534-95097-3 . 58544333 .
Notes and References
- Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem. Blazinskas. Andrius. Misevicius. Alfonsas. 15324387. 2011. 17th International Conference on Information and Software Technologies . Kaunas, Lithuania . https://isd.ktu.lt/it2011/ .
