Editing Travelling salesman problem (section)

==== Pairwise exchange ====
[[File:Showing a step of the two-opt heuristic.png|thumb|right|An example of a 2-opt iteration]]

The pairwise exchange or ''[[2-opt]]'' technique involves iteratively removing two edges and replacing them with two different edges that reconnect the fragments created by edge removal into a new and shorter tour. Similarly, the [[3-opt]] technique removes 3 edges and reconnects them to form a shorter tour. These are special cases of the ''k''-opt method. The label ''Lin–Kernighan'' is an often heard misnomer for 2-opt; Lin–Kernighan is actually the more general ''k''-opt method.

For Euclidean instances, 2-opt heuristics give on average solutions that are about 5% better than those yielded by Christofides' algorithm. If we start with an initial solution made with a [[greedy algorithm]], then the average number of moves greatly decreases again and is {{tmath|O(n)}}; however, for random starts, the average number of moves is {{tmath|O(n  \log (n))}}. While this is a small increase in size, the initial number of moves for small problems is 10 times as big for a random start compared to one made from a greedy heuristic. This is because such 2-opt heuristics exploit 'bad' parts of a solution such as crossings. These types of heuristics are often used within [[vehicle routing problem]] heuristics to re-optimize route solutions.<ref name=johnson>{{cite book |last1=Johnson|first1=D. S.|author1-link=David S. Johnson|last2=McGeoch|first2=L. A.|chapter=The Traveling Salesman Problem: A Case Study in Local Optimization|title=Local Search in Combinatorial Optimisation|editor1-first=E. H. L.|editor1-last=Aarts|editor2-first=J. K.|editor2-last=Lenstra|editor2-link=Jan Karel Lenstra|publisher=John Wiley and Sons Ltd.|date=1997 |location=London|pages=215–310 |chapter-url=https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf}}</ref>