Solving the Traveling Salesman Problem: Nearest Neighbor, 2-Opt, 3-Opt and Tabu Search

The Traveling Salesman Problem is easy to state: given a set of cities and the distance between each pair, find the shortest tour that visits every city once and returns to the starting point.

The difficulty is not understanding the objective. It is the number of possible tours.

For a symmetric problem with n cities, there are:

(n − 1)! / 2

distinct tours. With only 20 cities, this already represents more than 60 quadrillion possibilities. Exhaustively checking every route quickly becomes impractical.

Practical TSP solvers therefore tend to build a reasonable tour quickly, improve it through local search, and then broaden the search if the solution becomes trapped in a local optimum.

The progression from nearest neighbor to 2-opt, 3-opt and tabu search illustrates this process particularly well. It also connects directly to published research on bee colony optimization, local search and pruning strategies for the TSP.

This article is a focused follow-up to Optimization Problems Explained: Traveling Salesman, Job Shop Scheduling, and the Knight’s Tour, which introduces the wider family of combinatorial optimization problems.

1. Nearest Neighbor: Build a Tour Quickly

The nearest-neighbor heuristic starts from one city and repeatedly visits the closest city that has not yet been visited. When no unvisited cities remain, the route returns to the starting point.

choose a starting city
mark it as visited

while an unvisited city remains:
    move to the nearest unvisited city
    mark it as visited

return to the starting city

With a distance matrix, a straightforward implementation takes roughly O(n²) time. This makes nearest neighbor attractive when a usable route is needed immediately.

Its weakness is that every decision is local and usually irreversible.

A short edge selected early may force a very expensive connection near the end. The method is also sensitive to the starting city: running it from several starting points can produce very different tours.

One simple improvement is therefore to run nearest neighbor once from every possible starting city and retain the shortest result. This increases the computational cost but often produces a better initial tour.

Nearest neighbor should still be treated as a construction heuristic rather than a finished solver. Its purpose is to give the improvement methods a sensible place to start.

2. 2-Opt: Remove Bad Pairs of Edges

A nearest-neighbor tour often contains unnecessary detours or, on a Euclidean map, visibly crossed edges.

The 2-opt heuristic improves the tour by removing two edges and reconnecting the resulting paths differently.

Suppose the tour contains edges (a, b) and (c, d). A 2-opt move removes those edges and adds (a, c) and (b, d), reversing the route segment between b and c.

The change in tour length can be calculated as:

Δ = distance(a, c) + distance(b, d)
    − distance(a, b) − distance(c, d)

If Δ is negative, the new tour is shorter.

A typical 2-opt search repeatedly examines pairs of non-adjacent edges and applies one of two strategies:

• First improvement: accept the first shorter reconnection found.
• Best improvement: examine the entire neighborhood and apply the best available move.

First improvement is usually faster because the search can restart as soon as an improvement is found. Best improvement performs more work per iteration but may take a larger step toward a shorter route.

For a symmetric Euclidean TSP, 2-opt also has a useful geometric interpretation. If two edges cross, uncrossing them produces a shorter tour.

Removing every crossing does not, however, guarantee the global optimum.

The search eventually reaches a 2-opt local optimum: a tour where no single 2-opt move produces an improvement, even though a better tour may exist elsewhere in the search space.

There is also an important modelling limitation. In an asymmetric TSP, the cost of travelling from a to b may differ from the cost of travelling from b to a. Reversing a segment then changes the direction and cost of every edge inside that segment, so the simple symmetric delta calculation is no longer sufficient.

3. 3-Opt: Search a Larger Neighborhood

If 2-opt cannot improve a tour, 3-opt may still be able to do so.

Instead of removing two edges, 3-opt removes three. The resulting path segments can then be reconnected in a different order or orientation.

Suppose three edges are removed:

• (a, b)
• (c, d)
• (e, f)

This divides the tour into three segments. Several reconnections are possible after excluding the original arrangement.

Some reconnections are equivalent to 2-opt moves. Others are genuine 3-opt rearrangements that 2-opt cannot produce in a single step.

The larger neighborhood is both the advantage and the cost:

• 2-opt examines O(n²) edge pairs per complete pass.
• A naïve 3-opt search examines O(n³) edge triples.

For moderate instances, the additional search may be worthwhile. For large instances, evaluating every possible triple can become expensive.

Practical implementations normally reduce the work by:

• considering only geographically close edges;
• using candidate lists based on nearest neighbors;
• applying 3-opt only after 2-opt has converged;
• stopping after the first acceptable improvement; or
• limiting the number of 3-opt passes.

Even 3-opt remains a local search method. It can stop at a 3-opt local optimum while a better tour remains separated by one or more temporarily worse moves.

At that point, a solver needs more than a larger neighborhood. It needs permission to move temporarily in the wrong direction.

4. Tabu Search: Escape the Local Optimum

Ordinary hill climbing accepts only improving moves. Once every neighboring solution is worse, the search stops.

Tabu search changes this rule. It may accept a worse move now if doing so creates a path to a better region later.

Allowing worse moves introduces another problem. Without memory, the search can immediately reverse its previous move and cycle between the same few tours.

Tabu search prevents this with a short-term memory called the tabu list.

A TSP tabu-search iteration can work as follows:

1. Generate candidate moves, commonly using 2-opt or 3-opt.
2. Evaluate the resulting tours.
3. Choose the best admissible move, even if it worsens the current tour.
4. Record an attribute of the move as tabu for a limited number of iterations.
5. Preserve the best tour found across the entire search.

The recorded attribute might be:

• an edge that was removed;
• an edge that was added;
• a pair of cities that was exchanged; or
• the reversal of a particular segment.

The tabu tenure determines how long the attribute remains forbidden.

If the tenure is too short, cycling may return. If it is too long, too much of the useful neighborhood may be blocked.

An aspiration criterion provides an exception. A tabu move may be accepted if it produces a new best-known solution.

Longer searches can also use two complementary strategies:

• Intensification searches more deeply around promising tours or frequently occurring high-quality edges.
• Diversification encourages exploration of less-visited edges or regions of the search space.

Tabu search does not guarantee the global optimum. Its contribution is controlled exploration: local-search moves, a memory of where the search has been, and a mechanism for crossing valleys between local optima.

5. How the Methods Fit Together

Nearest neighbor, 2-opt, 3-opt and tabu search are complementary rather than competing methods.

Method	Primary role	Search cost	Accepts a worse move?
Nearest neighbor	Construct an initial tour	O(n²) overall	No
2-opt	Remove simple edge defects	O(n²) per full pass	Usually no
3-opt	Make deeper rearrangements	O(n³) per naïve pass	Usually no
Tabu search	Move between local optima	Depends on candidate list	Yes

A practical pipeline is:

nearest-neighbor tour
        ↓
2-opt until locally optimal
        ↓
selective 3-opt refinement
        ↓
tabu search using restricted 2-opt or 3-opt candidates
        ↓
best tour found within the available time

The stopping rule should reflect the application.

A route-planning service may have only a few seconds. A factory-layout or PCB-drilling study may run for hours because a small improvement will be repeated thousands of times in production.

This difference is important. A theoretically stronger heuristic is not necessarily the better engineering choice if its additional computation exceeds the value of the improvement.

6. Related Research

The same architecture—construct solutions, improve them locally and avoid spending computation on unpromising candidates—appears in published research on bee colony optimization.

The 2010 paper “Bee Colony Optimization with Local Search for Traveling Salesman Problem” integrated bee colony optimization with a fixed-radius near-neighbor 2-opt heuristic.

A frequency-based pruning strategy limited local optimization to promising solutions rather than applying it indiscriminately. Across 84 benchmark problems, the method reported an overall average solution quality 0.31% from the known optimum and performance comparable with ant colony and particle swarm approaches. Read the journal paper.

The earlier IEEE INDIN 2009 paper “An Efficient Bee Colony Optimization Algorithm for Traveling Salesman Problem Using Frequency-Based Pruning” addressed the same practical question: local search can improve solution quality, but applying it to every candidate solution creates substantial computational overhead. View the IEEE paper.

A later study, “A Bee Colony Optimisation Algorithm with a Sequential-Pattern-Mining-Based Pruning Strategy for the Travelling Salesman Problem,” used top-k sequential-pattern mining to identify recurring building blocks during the search.

The method was evaluated on 19 benchmark instances ranging from 318 to 1,291 cities. The reported results showed reduced computational time while producing tour lengths similar to two comparison approaches. Read the 2020 paper.

A generic bee colony framework was also applied to a concrete Hamiltonian-circuit problem in “Finding the Shortest Hamiltonian Circuit of Selected Places in Penang.”

This study provides a bridge between the abstract city-and-distance formulation and an actual geographic route. View the IEEE record.

Related tabu-search research demonstrates how the same memory-based principle transfers beyond the TSP.

Applications include heterogeneous directed-acyclic-graph scheduling and the multi-objective optimization of large containership stowage plans.

The solution representation changes between routing, scheduling and stowage planning, but the underlying principle remains similar: define a neighborhood, retain memory to prevent cycling, and search beyond the nearest local optimum.

The complete bibliography is available on the Publications page.

7. Choosing an Appropriate Method

Nearest neighbor is suitable when speed matters much more than route quality, or when a baseline solution is required.

2-opt is a natural next step for most symmetric TSP implementations. It is relatively simple, computationally manageable and often removes the most obvious defects in a constructed tour.

3-opt becomes useful when the problem size is moderate, 2-opt quality is insufficient, and additional computation is affordable. Candidate restrictions become increasingly important as the number of cities grows.

Tabu search is appropriate when repeated local search becomes trapped and the available computation time permits broader exploration.

Its effectiveness depends on several design choices:

• the underlying move operator;
• the tabu tenure;
• the aspiration criterion;
• the candidate-list size;
• the intensification strategy; and
• the diversification strategy.

Merely maintaining a list of forbidden moves is not enough. The list must prevent unproductive cycling without blocking too much of the useful search space.

For very large problems, the central engineering question is often not “Which single heuristic is best?” but “Where should computation be spent?”

Candidate-edge restrictions and pruning strategies address exactly this issue.

Conclusion

Nearest neighbor, 2-opt, 3-opt and tabu search form a natural ladder of sophistication.

Nearest neighbor makes fast, greedy decisions.
2-opt repairs pairs of edges.
3-opt searches deeper rearrangements.
Tabu search adds memory and the willingness to accept temporary deterioration in order to escape a local optimum.

None of these methods proves that the final tour is globally optimal.

Their value is practical: they transform an impossible exhaustive search into a sequence of increasingly informed decisions, producing strong routes within a realistic time budget.

That pattern extends well beyond the Traveling Salesman Problem. Construct, improve, remember and diversify is a recurring design language across routing, scheduling, stowage planning and many other combinatorial optimization problems.

References

1. G. A. Croes, “A Method for Solving Traveling-Salesman Problems,” Operations Research, 6(6), 791–812, 1958. https://doi.org/10.1287/opre.6.6.791
2. Shen Lin, “Computer Solutions of the Traveling Salesman Problem,” Bell System Technical Journal, 44(10), 2245–2269, 1965. https://doi.org/10.1002/j.1538-7305.1965.tb04146.x
3. D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis II, “An Analysis of Several Heuristics for the Traveling Salesman Problem,” SIAM Journal on Computing, 6(3), 563–581, 1977. https://doi.org/10.1137/0206041
4. Fred Glover, “Tabu Search—Part I,” ORSA Journal on Computing, 1(3), 190–206, 1989. https://doi.org/10.1287/ijoc.1.3.190
5. Li-Pei Wong, Malcolm Yoke Hean Low and Chin Soon Chong, “Bee Colony Optimization with Local Search for Traveling Salesman Problem,” International Journal on Artificial Intelligence Tools, 19(3), 305–334, 2010. https://doi.org/10.1142/S0218213010000200
6. Shin Siang Choong, Li-Pei Wong, Malcolm Yoke Hean Low and Chin Soon Chong, “A Bee Colony Optimisation Algorithm with a Sequential-Pattern-Mining-Based Pruning Strategy for the Travelling Salesman Problem,” International Journal of Bio-Inspired Computation, 15(4), 239–253, 2020. https://doi.org/10.1504/IJBIC.2020.108591