What is the Traveling Salesman Problem (TSP)?

The Traveling Salesman Problem asks for the shortest possible tour that visits each city exactly once and returns to the starting city, given pairwise distances between cities. It is a classic NP-hard optimization problem in combinatorial optimization and operations research.

Which algorithms does this TSP calculator use?

For small instances (up to 12 cities), the calculator can use the Held–Karp dynamic programming algorithm to find an exact optimal tour. For larger instances it uses a two-stage heuristic: a nearest-neighbor construction followed by 2-opt local search to improve the tour.

How many cities can I solve optimally with this tool?

The exact Held–Karp solver in this tool is limited to 12 cities to keep computations fast in the browser. The heuristic method can handle more cities (typically up to a few dozen) but does not guarantee optimality.

Can I enter a custom distance matrix instead of coordinates?

Yes. In Distance matrix mode you can enter an arbitrary symmetric or asymmetric distance matrix. The calculator will treat the distances as given and solve the TSP on that matrix.

Does the TSP calculator support Euclidean distances from coordinates?

Yes. In Coordinates mode you enter X and Y coordinates for each city. The calculator builds a symmetric distance matrix using Euclidean distances between the points and then runs the selected algorithm.

Traveling Salesman Problem (TSP) Calculator

Build and solve small instances of the Traveling Salesman Problem (TSP). Enter city coordinates (X, Y) or a full distance matrix, choose an exact Held–Karp solver for up to 12 cities or a nearest-neighbor + 2-opt heuristic for larger cases, and visualize the resulting tour.

This tool is ideal for teaching, coursework and quick what-if analyses in operations research, logistics and graph theory.

Input mode

Number of cities (n)

For exact optimization, keep n ≤ 12.

City coordinates

Each row is one city. Labels are assigned automatically (A, B, C, ...). Coordinates are arbitrary: you can treat them as X/Y on a plane or as projected longitude / latitude.

Algorithm

Exact solver guarantees optimality; heuristic scales better but is approximate.

Decimals in output

Use dot or comma as decimal separator. Empty cells are treated as missing values and will cause an error.

TSP tour results

Tour information

Distance breakdown

Step	Edge	Distance

Route visualization (coordinates mode)

Points represent cities; lines show the tour starting and ending at city A. If coordinates are not available (distance matrix mode), the SVG is left empty.

What is the Traveling Salesman Problem?

The Traveling Salesman Problem (TSP) is a fundamental problem in combinatorial optimization: given a list of cities and pairwise distances, find the shortest possible tour that visits each city exactly once and returns to the starting city.

Formally, given a complete graph with vertex set \(V\) and edge weights \(d(i, j)\), we seek a minimum-weight Hamiltonian cycle.

TSP as an optimization problem

Minimize \( \displaystyle L = \sum_{i=1}^{n} d(c_i, c_{i+1}) \)

subject to \( (c_1, c_2, \dots, c_n) \) being a permutation of the cities and \( c_{n+1} = c_1 \) (tour returns to start).

The TSP is NP-hard, which means that no known algorithm can guarantee optimal solutions in polynomial time for arbitrary large instances. However, many efficient exact and approximate algorithms exist for small and medium-sized problems.

Algorithms implemented in this TSP calculator

1. Held–Karp dynamic programming (exact)

For up to about 12 cities, the calculator can use the classic Held–Karp algorithm, which runs in \(O(n^2 2^n)\) time. It represents partial tours as subsets of cities and uses dynamic programming to propagate the best cost to each state.

\( C(S, j) = \min_{i \in S, i \ne j} \bigl[ C(S \setminus \{j\}, i) + d(i, j) \bigr] \)

where \(S\) is a subset of cities that includes the start and \(j\), and \(C(S, j)\) is the best path cost from the start to \(j\) visiting exactly the cities in \(S\).

2. Nearest-neighbor + 2-opt heuristic

For larger instances, the calculator offers a two-stage heuristic:

Nearest neighbor builds a tour greedily: from the current city, move to the nearest unvisited city.
2-opt then iteratively improves the tour by swapping two edges when it reduces the total length.

Heuristics are fast and often find good tours, but they do not guarantee optimality.

Coordinate vs distance matrix input

Coordinates mode: you specify planar coordinates \((x_i, y_i)\). The calculator builds a symmetric distance matrix using Euclidean distances \( d(i, j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \).
Matrix mode: you directly specify all distances. This is useful when distances are road travel times, costs or any other metric that is not simple Euclidean distance.

Typical use cases

Teaching TSP and NP-hardness in algorithms or operations research courses.
Demonstrating dynamic programming and local search heuristics.
Small “toy” routing problems in logistics, field service or sales territory planning.
Graph theory experiments in research and student projects.