Traveling Salesman Solver (TSP)

Find the shortest tour that visits every city exactly once and returns to the start. Exact dynamic programming (Held-Karp) for small instances and nearest-neighbor + 2-opt heuristics for larger ones. Accepts coordinates or a distance matrix and renders an animated SVG tour.

Quick examples:

5-city square+peak 8 random cities 8 EU capitals 4×4 matrix 10-city benchmark Triangle (open path)

⌖ Coordinates (x, y) ▦ Distance matrix

Cities or matrix

Coordinate lines: A, 10, 20 or 10 20. Matrix rows: 0 10 15 20 — one row per line, square, non-negative. Max 40 cities.

Matrix labels (optional)

Comma- or space-separated labels, one per matrix row. Defaults to A, B, C… if omitted.

Algorithm

Tour type

Embed Traveling Salesman Solver (TSP) Widget

About Traveling Salesman Solver (TSP)

The Traveling Salesman Solver is a practical, educational calculator for the classic Traveling Salesman Problem (TSP): given a set of cities and pairwise distances, find the shortest possible tour that visits every city exactly once and returns to the start. This solver accepts either planar coordinates or a custom distance matrix, selects the best algorithm automatically based on problem size, and renders the resulting tour as an animated SVG map.

What Is the Traveling Salesman Problem?

Formally, given a complete weighted graph G = (V, E) with vertex set V = {1, 2, ..., n} and edge weights d(i, j), TSP seeks a permutation π of the vertices that minimizes:

minimize Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

The final term closes the loop. TSP is one of the oldest and most studied problems in combinatorial optimization — it is NP-hard in the general case, meaning no known algorithm solves every instance in polynomial time. Despite that, it appears in countless real-world applications: vehicle routing, PCB drilling, DNA sequencing, warehouse picking routes, astronomical observation schedules, and even rural postal delivery.

How This Solver Works

Held–Karp Dynamic Programming (Exact)

For small instances (up to 12 cities) the solver computes the provably optimal tour using the Held–Karp algorithm, published independently by Richard Bellman and Michael Held & Richard Karp in 1962. The key recurrence, where C(S, j) is the shortest path from vertex 1 to vertex j visiting exactly the subset S:

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

The optimal tour cost is then min_j [C({1,...,n}, j) + d(j, 1)]. Held–Karp runs in O(2ⁿ · n²) time and O(2ⁿ · n) memory — a huge improvement over brute force n!, but still exponential. Past roughly 20 cities the memory footprint becomes impractical.

Nearest-Neighbor + 2-opt (Heuristic)

For larger instances the solver uses a two-stage heuristic. First, Nearest-Neighbor constructs a quick tour by greedily walking to the closest unvisited city from each starting vertex. The solver tries many starting vertices and keeps the best tour. Then 2-opt local search improves the tour by iteratively removing two edges and reconnecting the two resulting paths in the only other possible way:

Before: ... a — b ... c — d ... After 2-opt swap: ... a — c ... b — d ... If d(a,c) + d(b,d) < d(a,b) + d(c,d) → accept swap, reverse the subtour b..c

Geometrically, 2-opt removes every "crossing" in the tour: any two crossing segments can always be uncrossed for a shorter total length. The algorithm stops at a local optimum where no single swap helps, called a 2-optimal tour. On realistic Euclidean instances 2-opt typically finds tours within 2–5% of the true optimum in milliseconds.

Input Formats

Coordinate mode (x, y)

One city per line. Each line is label, x, y — label is optional. The solver computes Euclidean distances automatically and visualizes cities at their true positions.

A, 10, 20 B, 40, 70 C, 75, 30 Paris: 2.35, 48.86 10 20 ← auto-labeled C1

Distance matrix mode

An n × n square matrix of non-negative distances, one row per line, values separated by spaces or commas. Matrices may be symmetric or asymmetric — asymmetric matrices model one-way streets, flight prices with varying availability, and wind-dependent travel. Optionally provide labels in the Matrix labels field.

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

Algorithm Comparison

Algorithm	Time complexity	Memory	Result quality	Practical size
Brute force	O(n!)	O(n)	Optimal	n ≤ 10
Held–Karp DP	O(2ⁿ · n²)	O(2ⁿ · n)	Optimal	n ≤ 20
Nearest-Neighbor	O(n²)	O(n)	~25% worse than optimal	n ≤ thousands
NN + 2-opt	O(n² · passes)	O(n)	~2–5% worse than optimal	n ≤ hundreds

How to Use This Solver

Pick an input mode. Coordinates if your cities have meaningful (x, y) positions; Distance matrix if your costs are non-Euclidean or asymmetric.
Paste or type your data. One city or row per line. Click a quick-example button above the form to prefill a valid example.
Choose the algorithm. Leave on Auto for the right default: Held–Karp when the instance is small enough for provable optimality, NN + 2-opt otherwise. Force a specific algorithm if you want to compare.
Choose closed or open. A closed tour returns to the start — the traditional TSP. Open path mode solves the related Hamiltonian Path problem where the salesperson ends at a different city.
Click Solve. The result page shows the total tour length, an animated SVG of the route (click "Replay animation" to replay it), the full city sequence, a per-edge breakdown, and the distance matrix with tour edges highlighted.

Worked Example

Consider five cities — a rectangle plus a peak: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). The solver returns:

Tour: A → D → E → C → B → A
Length: 3 + √8 + √8 + 3 + 4 ≈ 15.66
Optimal? Yes — Held–Karp proves no shorter tour exists.
Why this order? The route traces the convex hull of the five points (A → D → E → C → B → A). A classical property of Euclidean TSP is that an optimal tour visits the points on the convex hull in their cyclic order; interior points slot in between adjacent hull neighbors. Any tour that crosses its own path, like A → C → B → D → E → A (length ≈ 21.8), can always be uncrossed by 2-opt for a shorter result.

Real-World Applications

Logistics & delivery — optimize a driver's daily route across 15 stops to minimize fuel and time.
Manufacturing — order the holes a CNC drill must make on a PCB to minimize head travel.
Genome assembly — order DNA fragments by overlap similarity, encoded as a distance matrix.
Astronomy — schedule telescope slews between target stars to maximize observation time.
Warehouse picking — sequence aisle visits to fulfil an order in fewest steps.
Tourism planning — plan a multi-city trip that minimizes travel time and fare cost.

Frequently Asked Questions

What is the Traveling Salesman Problem?

The Traveling Salesman Problem (TSP) asks for the shortest possible tour that visits every city exactly once and returns to the starting city. It is one of the most famous problems in combinatorial optimization and is NP-hard in the general case, meaning no known algorithm solves every instance in polynomial time.

What is the Held–Karp algorithm?

Held–Karp is a dynamic-programming algorithm that solves TSP exactly in O(2ⁿ · n²) time and O(2ⁿ · n) memory. It is dramatically faster than brute force (n factorial) but still exponential, so in practice it is only used for instances up to around 20 cities. This solver uses Held–Karp when there are 12 or fewer cities.

What is 2-opt and why is it used?

2-opt is a local-search heuristic that repeatedly removes two edges from the current tour and reconnects the two resulting paths in the other possible way. When the new tour is shorter, the swap is kept. 2-opt runs in polynomial time per iteration and consistently finds tours within a few percent of the optimal, which is why it is the classic go-to heuristic for larger TSP instances.

When should I use coordinates versus a distance matrix?

Use coordinates when your cities live in a plane with straight-line distances — for example points on a map, warehouse locations, or drill holes on a circuit board. Use a distance matrix when the pairwise cost is not Euclidean — for example flight prices, travel times with traffic, one-way road distances, or asymmetric costs. The matrix mode accepts any non-negative distances, even asymmetric ones.

Is the 2-opt solution optimal?

No, 2-opt returns a 2-optimal tour, meaning no single pair of edges can be swapped to produce a shorter route. This is a local optimum and usually within a few percent of the global optimum on well-behaved instances, but it is not guaranteed to be the global best. For a provably optimal tour on small instances, choose Held–Karp.

Does this tool support asymmetric distance matrices?

Yes. In Distance matrix mode you can enter any non-negative square matrix, including asymmetric ones where D[i][j] differs from D[j][i]. Held–Karp and 2-opt both handle asymmetric matrices correctly. This is useful for real-world routing problems with one-way streets, traffic, or wind-dependent flight costs.

Related MiniWebtools:

Adjacency Matrix CalculatorNew

Dijkstra's Shortest Path CalculatorNew

Graph Coloring CalculatorNew

Graph Degree Sequence ValidatorNew

Hamiltonian Path CheckerNew

Linear Programming SolverNew

Topological Sort CalculatorNew

Traveling Salesman Solver (TSP)

About Traveling Salesman Solver (TSP)

What Is the Traveling Salesman Problem?

How This Solver Works

Held–Karp Dynamic Programming (Exact)

Nearest-Neighbor + 2-opt (Heuristic)

Input Formats

Coordinate mode (x, y)

Distance matrix mode

Algorithm Comparison

How to Use This Solver

Worked Example

Real-World Applications

Frequently Asked Questions

What is the Traveling Salesman Problem?

What is the Held–Karp algorithm?

What is 2-opt and why is it used?

When should I use coordinates versus a distance matrix?

Is the 2-opt solution optimal?

Does this tool support asymmetric distance matrices?

Further Reading

Related MiniWebtools:

Advanced Math Operations:

Top & Updated: