latitude. Number of cities (n) Larger n increases compute time for heuristics; exact solver limited to n ≤ 12. Rebuild matrix Load symmetric example Distance matrix Cell (i, j) is the distance from city i to city j. Diagonal entries are ignored. The matrix may be
asymmetric; the solver will treat it as a directed TSP. Algorithm Exact Held–Karp (n ≤ 12) Nearest-neighbor + 2-opt heuristic Exact solver guarantees optimality; heuristic scales better but is approximate. Decimals in output Calculate tour Clear all 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. Traveling Salesman Problem – FAQ Why is the TSP considered difficult (NP-hard)? + The number of possible tours through n cities is \((n-1)!/2\) in the symmetric case, which grows
faster than exponentially. NP-hardness means that unless P = NP, no algorithm can solve all
instances optimally in polynomial time. Exact methods must exploit structure and pruning to
handle realistic sizes. Is the tour produced by the heuristic guaranteed to be optimal? + No. Heuristics like nearest neighbor and 2-opt are designed to be fast and usually produce good
tours, but they can get trapped in local minima. Only the exact Held–Karp solver guarantees that
the tour is globally optimal for the instance provided. Can I change the starting city of the tour? + This calculator always labels cities A, B, C, … and uses A as the nominal starting point. For a
symmetric TSP, rotating the tour to start at a different city does not change its total length.
You can therefore re-index the tour manually to your preferred starting city. How accurate is the Euclidean distance when using geographic coordinates? + If you plug raw latitude and longitude degrees into the coordinate fields, Euclidean distance is
only an approximation. For planning on the Earth’s surface, you should convert coordinates to a
suitable projected system (e.g. UTM) or work with precomputed distance matrices that reflect
real travel times or distances. Core Math & Algebra tools Standard Form Calculator Percent Error Calculator Effect Size (Cohen’s d) G-test (Likelihood-Ratio Test) FOIL Method Calculator Graph Adjacency Matrix Speed, Distance, Time Friedman Test Traveling Salesman Problem – you are here Stem-and-Leaf Plot Generator Optimization & graph tools Shortest Path (Dijkstra) Minimum Spanning Tree Max Flow
1 calculators