The traveling salesman problem asks for the shortest closed route that visits every input point exactly once and returns to the start, and the best solution it admits in practice is a deterministic, locally improved heuristic rather than a globally optimal answer. The Traveling Salesman Solver builds that kind of answer by accepting 3 to 50 named (x, y) coordinates, running a nearest-neighbor pass to produce an initial route, and then repeatedly applying 2-opt edge swaps until no further improvement is possible. The output panel shows the initial nearest-neighbor distance next to the improved distance and counts the number of 2-opt passes, so the gain from local search is visible rather than hidden. Because routing problems are NP-hard, no polynomial-time algorithm is known that returns the guaranteed shortest route for arbitrary inputs, and any tool that promises that is overstating what it can do. This page deliberately keeps the heuristic bounded and inspectable, fixing the first input row as the starting point so repeated runs with the same data produce the same answer.
What "Best Solution" Means for the Traveling Salesman Problem
The traveling salesman problem is the classic question: given a set of points and the distances between them, find the shortest closed tour that visits each point exactly once and returns to the starting point. For very small inputs you can enumerate every permutation and pick the minimum, but for practical inputs that brute-force approach collapses because the number of possible tours grows factorially with the number of points. The TSP is also NP-hard, which means no known algorithm is guaranteed to solve every instance to optimality in polynomial time. Google OR-Tools describes the same routing objective in its routing documentation and notes that practical solvers can return non-optimal results on hard inputs. Production routing systems therefore use specialized solvers, branch-and-bound, integer programming, or constraint methods tuned to specific problem shapes. A web tool aimed at teaching and inspection does something different: it gives you a clear, deterministic heuristic, not a black-box claim of optimality. Knowing that distinction lets you pick the right tool for the right task.
Inputs the Solver Accepts and What It Rejects
The Traveling Salesman Solver takes a list of 3 to 50 named coordinate pairs, one per line, in the form name, x, y. The first row is treated as the fixed starting location and the tour always returns to it at the end. Names may not contain commas because the comma is the field separator, and coordinates must be finite values within the solver's accepted range. Duplicate coordinates are rejected: two distinct names placed at exactly the same position would make the route ambiguous, since the tool cannot tell which ordering you intended. The point limit of 50 is a practical guardrail that keeps the local search responsive, because 2-opt is quadratic in the number of points per pass. Anything outside these rules is rejected before the solver runs, so you get a clear validation message instead of a misleading tour.
| Input element | Requirement |
|---|---|
| Number of points | 3 to 50 inclusive |
| Per-line fields | name, x, y (comma-separated) |
| Name characters | No commas allowed |
| Coordinates | Finite, bounded planar values |
| Starting point | Always the first row |
| Duplicate coordinates | Rejected |
| Latitude and longitude | Not supported as-is |
Run a Closed Tour in Three Steps
- Type each location on its own line as name, x, y. Put the location you want the route to start and end at in the first row. Use a coordinate system that uses the same units on both axes: meters on a local drawing, pixels in a layout, or unitless classroom values are all fine.
- Run the solver to build the tour. The result panel lists the closed sequence of names that visits every point once and returns to the start, the initial nearest-neighbor distance, the improved distance after 2-opt, and the number of 2-opt passes that were applied.
- Compare the two distances to see how much the local search shortened the route, inspect the order of names, and copy the closed sequence if straight-line Euclidean distance fits your task.
How Nearest Neighbor and 2-Opt Produce the Number
The solver is built around two well-understood TSP heuristics that are standard in textbooks and in Croes's 1958 paper on 2-opt. Construction begins at the first input point. At each step, nearest neighbor picks the unvisited point that minimizes Euclidean distance to the current end of the tour, where distance is the straight-line sqrt((x2 − x1)² + (y2 − y1)²). If two candidates are exactly equidistant, the earlier one in your input order wins, which keeps the result deterministic. Once a complete tour exists, 2-opt scans pairs of edges. For each pair, it considers reconnecting them by reversing the segment of the tour between them. If the reversal strictly shortens the total distance, the swap is applied and scanning restarts from the first edge. Passes continue until a full scan finds no improving swap, or until a defensive iteration cap is reached. The returned tour is locally optimal under two-edge exchanges, which is a meaningful improvement on raw nearest neighbor but not a guarantee of global optimality.
Take four points as a worked example: A (0, 0), B (4, 0), C (4, 3), D (0, 3), with A as the start. Starting at A, the nearest unvisited point is D at sqrt((0 − 0)² + (3 − 0)²) = sqrt(9) = 3. From D the nearest unvisited point is C at sqrt((4 − 0)² + (3 − 3)²) = sqrt(16) = 4. From C the nearest unvisited point is B at sqrt((4 − 4)² + (0 − 3)²) = sqrt(9) = 3. From B back to A the distance is sqrt((0 − 4)² + (0 − 0)²) = sqrt(16) = 4. The total nearest-neighbor distance is 3 + 4 + 3 + 4 = 14. For this particular rectangle, nearest neighbor happened to recover the true perimeter (2 × (4 + 3) = 14), so the improved distance after 2-opt will equal the initial distance with no useful swap. On more complex geometries with crossings, 2-opt typically shortens the route further.
| Geometry | Typical 2-opt behavior |
|---|---|
| Triangle (3 points) | No swap can shorten the perimeter; improved equals initial. |
| Square or rectangle | Often no swap is needed if nearest neighbor already walks the perimeter. |
| Collinear points | Removes crossings to recover a clean linear sweep with detours removed. |
| Center point plus ring | Reverses out-and-back legs, often saving a substantial fraction of the initial distance. |
Reading Initial vs Improved Distance and 2-Opt Passes
The output panel is structured so the heuristic is auditable rather than opaque. Three numbers carry most of the meaning. The initial distance is what nearest neighbor produced on its own, before any local search touched it. The improved distance is what 2-opt reached at the end, and by construction it is always less than or equal to the initial distance because every accepted swap is required to strictly shorten the total. The pass count tells you how many full scans the loop needed before it ran a complete scan with no improving swap. A high pass count on a small input usually means the input had crossings that took several sweeps to untangle; a low pass count often means the nearest-neighbor tour was already close to a local minimum. If the two distances are equal, 2-opt made no useful swap on your data, which is common for very small instances or for inputs that nearest neighbor already orders well. Running the same input a second time produces the identical result because the first row is fixed as the start and exact ties keep their original order.
Why You Should Not Paste Latitude and Longitude Here
The solver treats coordinates as flat planar values, not as degrees on a sphere. That matters because Euclidean distance between two points given as decimal degrees is only a rough approximation of real Earth distance, and the approximation gets worse the closer you get to the poles or the larger the region you cover. Across continental or oceanic spans the distortion is severe, and across the antimeridian it can flip direction entirely. If you need a real-world traveling salesman route on the surface of the Earth, project your points to a local coordinate system first (a UTM zone, for example) or use a routing service that works with geodesic distance and the actual road or transit network. Treating pixels, millimeters, or unitless classroom values as if they were meters will also be wrong, but at least the error is uniform and you can pick a consistent scale on both axes. The fundamental limitation is the same in either case: this tool assumes a flat two-dimensional plane with the same units on x and y, so straight-line segments between points are geometric segments, not claims about roads or travel time.
Tasks This Tool Fits and Tasks It Does Not
The Traveling Salesman Solver is a good fit when you want to learn how nearest neighbor and 2-opt behave on a small input you can draw, sketch a candidate inspection sequence on a local drawing, generate reproducible test fixtures for a routing algorithm you are writing, or experiment with how the choice of starting point changes a locally optimal tour. For related combinatorial work on named points, the minimum spanning tree guide covers the connection-cost version of the same input style. The solver is not a fit when you need guaranteed optimal routing for cost commitments or dispatch, when you need to honor real-world constraints like one-way streets, time windows, vehicle capacity, multiple drivers, traffic, or obstacles, or when the underlying distance should be travel time on a road network rather than straight-line Euclidean distance. The solver does not call any external map API, so there is no paid request and no location data leaves your browser, but that also means it cannot know about the road between two coordinates. For those jobs, use a validated solver with a real network distance or time matrix and verify the route independently rather than treating a local approximation as operational authority.