Most algorithms that solve the traveling salesman problem (TSP) in practice are search heuristics from operations research and AI: build a tour with a rule such as nearest neighbor, then improve it with moves such as 2-opt or Lin-Kernighan. In the 2001 DIMACS benchmark of 10,000-city random instances, nearest neighbor ended 24.79 percent above the Held-Karp lower bound, 2-opt 4.70 percent, Lin-Kernighan 2.00 percent, and a refined Lin-Kernighan code by Keld Helsgaun 0.69 percent. Metaheuristics such as simulated annealing, tabu search, and ant colony optimization sit on top of these ideas.
Key takeaways
- A tour-construction rule gives a fast first answer, and a local-search move then shortens it by swapping edges.
- Nearest neighbor can be off by a factor that grows with the logarithm of the number of cities in the worst case, according to the Johnson and McGeoch survey.
- Lin-Kernighan, published in 1973, remains the base of the best-performing heuristics in that survey.
- Better tours cost more time: a tabu search entry reached 1.48 percent excess but needed 18,830 normalized seconds.
- The worked example below is illustrative and uses six invented points.
Step one: building a tour
A construction heuristic produces a complete tour without trying to prove anything about it. Nearest neighbor starts at one city and always moves to the closest unvisited one, ending by returning to the start. It is quick and easy to code. Johnson and McGeoch note in their survey that when distances obey the triangle inequality, nearest neighbor can be longer than the optimum by a factor of order log N, a worst-case result from a 1977 paper by Rosenkrantz, Stearns, and Lewis. Greedy edge selection, the savings method, and Christofides' algorithm are other construction rules.
Christofides' algorithm is notable because it carries a proof: for distances obeying the triangle inequality, the tour is at most 1.5 times the optimum. The OR-Tools documentation lists a Christofides option and warns that its version uses a maximal matching instead of a maximum one, so it does not keep the 3/2 guarantee. A name on a menu does not always mean the textbook algorithm.
Step two: improving a tour with edge swaps
Local search takes an existing tour and tests small changes. The 2-opt move, described by G. A. Croes in 1958, removes two edges and reconnects the tour by reversing the segment between them. If the new tour is shorter, it is kept. 3-opt removes three edges. Lin and Kernighan's 1973 paper in Operations Research generalized this by chaining swaps to a variable depth, so the search decides how far to go for each improvement. Helsgaun's 2000 paper in the European Journal of Operational Research describes a refined implementation, widely known as LKH.
The table is an illustrative example, not a benchmark. It uses six points on a grid, with coordinates in arbitrary units, and straight-line distances computed from them.
| Tour | Edges removed or added | Length |
|---|---|---|
| Nearest neighbor from A: A, E, B, D, F, C | Start: A (8,5), B (2,5), C (4,8), D (1,4), E (5,4), F (2,1) | about 23.2 |
| After one 2-opt move: A, E, F, D, B, C | Remove E-B (3.16) and F-C (7.28); add E-F (4.24) and B-C (3.61) | about 20.6 |
| Best tour found by checking all 120 orderings | A, C, B, D, F, E, which is the same cycle as the 2-opt result | about 20.6 |
Nearest neighbor was trapped by its short-sighted choices: after visiting F, the only city left was C, 7.28 units away, so the last leg was long. One 2-opt move reached the optimum. On larger inputs a single pass seldom does so, and local search stops at a local minimum, a tour no single move can shorten.
Step three: metaheuristics that escape local minima
Metaheuristics add a rule for moving past those dead ends. Kirkpatrick, Gelatt, and Vecchi's 1983 paper in Science proposed simulated annealing, which sometimes accepts a worse tour with a probability that shrinks over time, and used the TSP among its test problems. Dorigo and Gambardella's 1997 paper in IEEE Transactions on Evolutionary Computation described Ant Colony System, in which simulated agents deposit and follow pheromone on edges; the authors reported it compared favorably with simulated annealing and evolutionary methods on the instances they tested. The OR-Tools routing options page lists guided local search, simulated annealing, and tabu search, and calls guided local search generally the most efficient of the three for vehicle routing.
These methods trade time for tour quality. The next table repeats the survey's averages for 10,000-city random uniform Euclidean instances, as reported in the Johnson and McGeoch chapter on the DIMACS challenge.
| Heuristic (survey label) | Excess over Held-Karp bound | Normalized time, seconds |
|---|---|---|
| Nearest neighbor (NN) | 24.79 percent | 0.28 |
| Greedy | 16.42 percent | 0.20 |
| Christofides variant (Christo-S) | 9.81 percent | 1.04 |
| 2-opt (2opt-JM) | 4.70 percent | 1.41 |
| 3-opt (3opt-JM) | 2.88 percent | 1.50 |
| Lin-Kernighan (LK-JM) | 2.00 percent | 2.06 |
| Tabu search (Tabu-SC-SC) | 1.48 percent | 18,830 |
| Helsgaun's code (Helsgaun-.1N) | 0.69 percent | 1,840 |
Times were normalized to a 500 MHz Alpha processor from 2001, so only the ratios between rows carry meaning. The Held-Karp bound is a lower bound on the optimal tour, which means the excess over the true optimum is somewhat smaller than these percentages.
Where learned models fit
Neural methods are a separate line of work and are covered on this site in the article on what AI solves for the salesman problem today. For the algorithms above, no training data are needed: they run on the distance matrix alone. Real delivery routing usually adds capacities and time windows, which moves the task into vehicle routing, where solvers such as OR-Tools apply these same building blocks.
FAQ
Is nearest neighbor ever the right choice?
It suits a quick starting tour that a local search will then improve. On its own it was the weakest of the common construction rules in the survey table, at 24.79 percent above the bound on 10,000 cities.
What is the difference between 2-opt and Lin-Kernighan?
2-opt makes one fixed type of swap, while Lin-Kernighan chains swaps and decides at each step whether to go deeper. In the survey table, that moved the average from 4.70 to 2.00 percent excess, with normalized time rising from 1.41 to 2.06 seconds.
Does a metaheuristic guarantee the shortest tour?
No. Simulated annealing, tabu search, and ant colony methods return good tours but give no proof of optimality. Proofs come from exact methods, which are a separate topic.
Why is the survey from 2001 still useful?
Its relative results on the same instances are still a clear comparison of method families. Its running times are not, because hardware has changed.
Related reading
- The salesman problem in AI: strategies and directions
- Solving the notorious salesman puzzle
- AI and route optimization
- Heuristics in artificial intelligence
More in Traveling salesman problem.
Last verified: October 2026
Sources
- Johnson DS, McGeoch LA. Experimental Analysis of Heuristics for the STSP, in The Traveling Salesman Problem and Its Variations, Kluwer, 2002 (draft hosted by the DIMACS TSP Challenge)
- Rosenkrantz DJ, Stearns RE, Lewis PM. An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM Journal on Computing, 1977
- Croes GA. A Method for Solving Traveling-Salesman Problems, Operations Research, 1958
- Lin S, Kernighan BW. An Effective Heuristic Algorithm for the Traveling-Salesman Problem, Operations Research, 1973
- Helsgaun K. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic, European Journal of Operational Research, 2000
- Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by Simulated Annealing, Science, 1983
- Dorigo M, Gambardella LM. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, 1997
- Routing options, OR-Tools documentation, Google Developers, 2026