A traveling salesman solver does not guarantee the globally shortest route — it returns an approximate closed tour built with a heuristic and improved under local two-edge exchanges. The Traveling Salesman Solver on this site is explicit about that limitation: it combines nearest-neighbor construction with deterministic 2-opt improvement, then reports the result without claiming global optimality. That honesty matters because the underlying traveling salesman problem is NP-hard: as the number of cities grows, finding a true shortest tour can require computation that explodes factorially, so practical tools rely on heuristics that may stop at a local minimum. A locally optimal tour under 2-opt means no single two-edge swap makes the route shorter, which is a much weaker condition than being the shortest route that visits every point once. Knowing the difference between "locally improved" and "globally shortest" is the first thing to confirm before trusting any TSP result for planning, dispatch, or cost commitments.
What "Globally Shortest" Actually Means for the TSP
The traveling salesman problem asks for a closed route that visits every input point exactly once and returns to the starting point, with the minimum possible total distance. That minimum, taken across all valid permutations, is the globally shortest tour. For n points there are (n−1)!/2 distinct tours to compare once a fixed start is enforced, and that count grows faster than any polynomial in n. Google OR-Tools describes the same routing objective and warns that practical solvers can return non-optimal results because routing problems are computationally difficult.
Once the input passes roughly fifteen or twenty points, exact algorithms such as branch-and-bound or the Held–Karp dynamic program still finish but at rapidly growing cost. Beyond a few dozen points, even dedicated research solvers require hours or special-purpose hardware to prove global optimality. That is why consumer-facing TSP tools — including the one on this page — deliberately use bounded heuristics and report improvement rather than optimality.
How Nearest Neighbor Builds the First Tour
The Traveling Salesman Solver starts by locking the first input row as the starting location, then walks greedily. From the current point it picks the closest unvisited point using Euclidean distance, computed as sqrt((x₂−x₁)² + (y₂−y₁)²). When two candidates are exactly the same distance, the tie keeps the original input order, which makes repeated runs deterministic. The construction finishes when every point has been visited, and the last leg returns to the starting point so the tour is closed.
The nearest-neighbor rule is fast and intuitive, but it has a well-known weakness: a greedy first step can trap later steps in a long detour. A point chosen early because it is locally close may force the rest of the route to cross itself, which is a strong hint that the closed tour is not globally shortest. The solver reports the nearest-neighbor distance so you can see exactly how much room 2-opt has to improve.
How 2-opt Improves the Tour Locally
Once a complete closed tour exists, the solver scans pairs of route edges and asks a simple question: if the segment between those two edges is reversed, does the total Euclidean distance strictly drop? When the answer is yes, the exchange is applied and scanning restarts from the new tour. When no pair of edges yields a strict improvement — or when a defensive pass limit is reached — the loop stops. The number of 2-opt passes performed is reported alongside the improved distance, so the heuristic work is visible rather than hidden.
This is exactly the local-improvement scheme described by Croes in 1958 for the traveling-salesman problem. The crucial property is what "local" means: the final tour is guaranteed only to have no improving two-edge swap. That condition is necessary for global optimality but not sufficient, because a tour can be 2-opt-locally minimal and still be longer than the true global optimum. A different starting point or a different construction rule can land the heuristic in another local minimum.
How to Use the Traveling Salesman Solver
- Open the Traveling Salesman Solver and enter between 3 and 50 locations, one per line, using the format name, x, y. Names must not contain commas, coordinates must be finite and bounded, and every coordinate pair must be unique.
- Place the desired starting location in the first row so that the constructed tour begins and ends there. The solver treats the first row as fixed, which keeps repeated runs deterministic for the same input order.
- Submit the coordinates to build the approximate tour. The page reports the nearest-neighbor starting distance, the improved distance after 2-opt, and the number of 2-opt passes that were applied.
- Inspect the closed route and read the displayed assumptions — straight-line Euclidean distance, no roads, no traffic, no time windows — and decide whether those assumptions fit the task at hand.
- Copy the result only if straight-line Euclidean distance is the right metric. The copied output contains the full closed name sequence plus the calculated distance.
Why a Different Starting Point Can Change the Answer
Because the solver fixes the first row as the start and uses deterministic nearest-neighbor construction with tie-breaking by input order, permuting the input rows produces different tours. For some inputs those tours agree on the same total distance, but in many practical layouts they do not. If the route quality matters, the standard remedy is to run the same coordinate set several times with different starting points, keep the shortest result, and treat that as the practical best.
Two extra checks are worth doing by hand. First, eyeball the closed route on a sketch and confirm the polyline does not cross itself — a self-intersecting tour is a strong sign that a better ordering exists. Second, repeat the run after reversing the input order; nearest-neighbor tends to behave differently from the back end, and a lower improved distance is a clear signal that the previous run landed in a worse local minimum.
What the Solver Ignores on Purpose
The tool uses straight-line Euclidean distance on a flat plane and calls no external map or routing API, so several real-world complications are deliberately out of scope. Coordinates are treated as abstract planar values such as meters on a local drawing, pixels in a layout, or unitless classroom coordinates — not latitude and longitude. Applying Euclidean distance directly to degrees distorts real Earth distance, especially across large regions or across the antimeridian. For geographic points, convert to an appropriate local projection or hand the problem to a routing service built on geodesic distance; the guide Can You Enter Latitude and Longitude in a TSP Solver? covers the limits in more detail.
| Aspect | Behavior of the Traveling Salesman Solver |
|---|---|
| Coordinate system | Flat plane with the same unit on both axes |
| Distance metric | Straight-line Euclidean, sqrt((x₂−x₁)²+(y₂−y₁)²) |
| Roads, traffic, one-way streets | Ignored; no map or routing API is called |
| Geographic points (lat/lon) | Not supported as a reliable distance source |
| Solution guarantee | Locally optimal under two-edge exchanges, not globally shortest |
| Privacy | Inputs and outputs stay in the browser; no data leaves the device |
When the Heuristic Is Enough — and When It Is Not
The heuristic is the right tool for learning how TSP algorithms work, exploring spatial ordering on a small coordinate sketch, planning an approximate inspection sequence on a local grid, or producing reproducible test fixtures. It also works well as a sanity check on small inputs where exact enumeration is trivial. The same is true for any puzzle, classroom exercise, or layout problem where the metric really is straight-line distance on a flat plane.
The heuristic is the wrong tool when the route drives real decisions: dispatch, navigation, cost commitments, time windows, vehicle capacity, multiple drivers, or any safety-critical routing. For those tasks the proper input is a real distance or time matrix and the proper engine is a validated routing solver such as Google OR-Tools, used with independently verified network data. Treat the local approximation on this page as a learning aid and a quick estimator, not as operational authority.
A Small Worked Example
To make the construction and the distance arithmetic concrete, take three points: A at (0, 0), B at (3, 0), C at (0, 4), with A as the fixed starting row. From A the nearest-neighbor step compares distance to B, sqrt((3−0)²+(0−0)²) = 3, and distance to C, sqrt((0−0)²+(4−0)²) = 4, so it picks B. From B the only unvisited point is C, with distance sqrt((0−3)²+(4−0)²) = sqrt(9+16) = 5. Closing the tour from C back to A adds another 4. The nearest-neighbor total is 3 + 5 + 4 = 12. Because the three edges form a 3-4-5 right triangle with no crossing alternative, 2-opt finds no strictly improving exchange and the improved distance stays at 12 — a reminder that locally optimal and globally optimal can coincide on small geometric inputs even though they diverge on larger ones.
For a deeper look, see 24 Game Solver With Decimals: Fraction Routes to 24.