TSP Solver Online

Pseudocode

There is no fast exact algorithm for the travelling salesman problem, so the practical answer is a two-stage one: build a decent tour quickly, then improve it locally until it stops improving.

// Stage 1: nearest neighbour, builds a tour in O(n squared)
tour = [start]
while some city is unvisited:
    next = unvisited city closest to tour.last
    tour.append(next)
tour.append(start)              // close the loop

// Stage 2: 2-opt, removes crossings until no move helps
repeat until no improvement:
    for each pair of edges (a,b) and (c,d) in tour:
        if dist(a,c) + dist(b,d) < dist(a,b) + dist(c,d):
            reverse the tour segment between b and c

// Exact, for small n: Held-Karp dynamic programming
dp[S][j] = min over k in S\{j} of dp[S\{j}][k] + dist(k, j)

The 2-opt move is worth understanding geometrically. If two edges of a tour cross, swapping their endpoints and reversing the segment between them always shortens the tour by the triangle inequality. So 2-opt is, quite literally, the operation of pulling the knots out of a loop of string.

Worked example, step by step

Run nearest neighbour then 2-opt on four cities placed at the corners of a rectangle, where the greedy choice provably goes wrong.

Example graph: Cities A(0,0), B(0,3), C(4,3), D(4,0). Distances: A-B 3, B-C 4, C-D 3, A-D 4, and the diagonals A-C and B-D both 5.

1. Nearest neighbour from A. The closest city to A is B at 3. Move to B.
2. From B. Unvisited are C at 4 and D at 5. Take C.
3. From C. Only D remains, at 3. Take it, then close back to A at 4.
4. Greedy result. Tour A to B to C to D to A costs 3 + 4 + 3 + 4 = 14. This happens to be optimal here, so perturb it: suppose the heuristic had produced A to C to B to D to A, costing 5 + 4 + 5 + 4 = 18, a tour whose edges cross.
5. 2-opt repair. Examine edges A-C and B-D. Currently they contribute 5 + 5 = 10. Reconnecting as A-B and C-D gives 3 + 3 = 6, an improvement of 4, so reverse the segment between C and B. The tour becomes A to B to C to D to A at cost 14, and no further 2-opt move helps.

The optimal tour is the rectangle perimeter at 14, not either diagonal-crossing tour at 18. This is the whole story of TSP heuristics in miniature: a fast constructive pass gets close, and local search removes the crossings that the greedy choice introduced.

Complexity, and where it comes from

Time: O(n squared) heuristic, O(n squared times 2^n) exact · Space: O(n squared) heuristic, O(n times 2^n) exact

Nearest neighbour scans all remaining cities at each of n steps, giving O(n squared). Each 2-opt sweep tests all O(n squared) pairs of edges and repeats until no improvement, which is fast in practice but has no useful worst-case bound. Held-Karp is exact and fills a table indexed by subset and endpoint: there are 2^n subsets times n endpoints, and each entry takes O(n) to compute, hence O(n squared times 2^n) time and O(n times 2^n) memory. That is a hard wall around n = 20 to 25, since 2^25 times 25 already exceeds a billion table entries. Brute force over all permutations is far worse at O(n!).

When to use Traveling Salesman Problem, and when not to

The right method depends almost entirely on how many cities you have and whether you need a provable optimum.

Common pitfalls

• Expecting an exact answer at scale. TSP is NP-hard. There is no known algorithm that solves 1,000 cities exactly in reasonable time, and finding one would settle P versus NP. If a tool claims an exact optimum on a large instance quickly, it is returning a heuristic tour.
• Trusting nearest neighbour alone. Greedy construction is typically 25 percent worse than optimal and can be arbitrarily bad in the worst case, because the last few cities left over force very long edges. Always follow it with local search.
• Applying Christofides to non-metric distances. Its 1.5 approximation guarantee depends on the triangle inequality. With one-way streets, asymmetric costs or prohibited routes, the bound simply does not hold.
• Confusing TSP with the vehicle routing problem. TSP is one vehicle, no capacity, no time windows. The moment you add a fleet or load limits, you need VRP or CVRP methods; a TSP tour split into chunks is not a valid VRP solution.
• Ignoring that the start city does not matter. A TSP tour is a cycle, so rotating it changes nothing. Implementations that treat the start as meaningful waste work and can report different costs for identical tours.

Frequently asked questions

What is the travelling salesman problem?

Given a set of cities and the distance between each pair, TSP asks for the shortest possible route that visits every city exactly once and returns to the start. It is one of the most studied problems in combinatorial optimization and is NP-hard, meaning no polynomial-time exact algorithm is known.

Why is TSP so hard to solve?

The number of distinct tours grows as (n-1)!/2, so 20 cities already allow about 60 quadrillion tours. No known algorithm avoids exponential work in the worst case. The best exact method, Held-Karp dynamic programming, runs in O(n squared times 2^n) and becomes impractical past roughly 25 cities.

What is the best algorithm for TSP?

It depends on size. Under about 20 cities, Held-Karp gives an exact optimum. For metric instances, Christofides guarantees a tour within 1.5 times optimal. For large real instances, Lin-Kernighan or nearest neighbour followed by 2-opt gives tours within a few percent of optimal in seconds.

What does 2-opt actually do?

It repeatedly removes two edges from the tour and reconnects the two resulting paths the other way round, keeping the change if the tour gets shorter. Geometrically it removes crossings: whenever two edges of a tour cross, the uncrossed reconnection is shorter by the triangle inequality.

What is the difference between TSP and the vehicle routing problem?

TSP routes a single vehicle through every city with no constraints beyond visiting each once. VRP routes a fleet from a depot, usually with capacity limits, and often time windows and driver shifts. TSP is the special case of VRP with one vehicle and unlimited capacity.