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)$.{{Cite conference|title=Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem|last1=Blazinskas|first1=Andrius|last2=Misevicius|first2=Alfonsas|s2cid=15324387|date=2011|conference=17th International Conference on Information and Software Technologies |location=Kaunas, Lithuania |conference-url=https://isd.ktu.lt/it2011/ |url=https://isd.ktu.lt/it2011/material/Proceedings/1_AI_5.pdf}} Iterated 3-opt, in which passes are repeated until no more improvements can be found, has a higher time complexity.