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 .[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 nodes , where , deleting three edges separates into four segments , , and . Note that the segments and are connected. The reconnection of the Subtours is done by a combination of reversing one or both of and and switching their respective positions. The 8 possible new tours are , , , , , , and . Here indicates that segment is reversed.
![{\displaystyle S=[n_{0},n_{1},n_{2},...,n_{k-1},n_{k}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50a0c58a0ed12ab7b5dcd7fa49966d96ba6bb535)
![{\displaystyle [S_{1},S_{2},S_{3},S_{4}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1232233c4177b3a1668421880240d2fc4b6bc030)
![{\displaystyle [S_{1},{\overleftrightarrow {S_{2}}},S_{3},S_{4}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c994dcdf3c9ea40c617c783a27611147937fa5e)
![{\displaystyle [S_{1},S_{2},{\overleftrightarrow {S_{3}}},S_{4}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b62d391a08ab9ebaddf916781119a7dc7ba23da)
![{\displaystyle [S_{1},{\overleftrightarrow {S_{2}}},{\overleftrightarrow {S_{3}}},S_{4}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a66a3750600d13c95d029ce850716d80fdd91ec)
![{\displaystyle [S_{1},S_{3},S_{2},S_{4}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39fe0e4d4030a288d2d98b8d0e17b98b9f823e9d)
![{\displaystyle [S_{1},{\overleftrightarrow {S_{3}}},S_{2},S_{4}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/824804745f8b93d7c5eac89e6616fcd2f58cd2e8)
![{\displaystyle [S_{1},S_{3},{\overleftrightarrow {S_{2}}},S_{4}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9ab54aba9df5c0e73e2c3e597781f658fd75065)
![{\displaystyle [S_{1},{\overleftrightarrow {S_{3}}},{\overleftrightarrow {S_{2}}},S_{4}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c39991a3352dae4a17dcc0e327590f1fe4e6c94)
See also
[edit source]References
[edit source]- ↑ Blazinskas, Andrius; Misevicius, Alfonsas (2011). Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem (PDF). 17th International Conference on Information and Software Technologies. Kaunas, Lithuania. S2CID 15324387.
Further reading
[edit source]- BOCK, F. (1958). "An algorithm for solving traveling-salesman and related network optimization problems". Operations Research. 6 (6).
- Lin, Shen (1965). "Computer Solutions of the Traveling Salesman Problem". Bell System Technical Journal. 44 (10). Institute of Electrical and Electronics Engineers (IEEE): 2245–2269. doi:10.1002/j.1538-7305.1965.tb04146.x. ISSN 0005-8580.
- Lin, S.; Kernighan, B. W. (1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem". Operations Research. 21 (2). Institute for Operations Research and the Management Sciences (INFORMS): 498–516. doi:10.1287/opre.21.2.498. ISSN 0030-364X.
- Sipser, Michael (2006). Introduction to the theory of computation. Boston: Thomson Course Technology. ISBN 0-534-95097-3. OCLC 58544333.