TSPLIB Heuristic TSP Solver

What this research found

A two-stage heuristic for the travelling salesperson problem — a nearest-neighbour construction followed by a first-improvement 2-opt local search — was implemented from first principles, using no external solver or metaheuristic library, and benchmarked on five Euclidean TSPLIB instances spanning 51 to 1,002 cities. The raw greedy tours landed 19% to 31% above the published optima, and a single 2-opt descent cut that to between 2.82% and 7.17%. Fitted power laws put construction runtime at N to the power 1.09 and the local search at N to the power 3.10, so refinement dominates the total cost entirely.

• One first-improvement 2-opt descent shrank the optimality gap by a factor of three to seven: from 19.95% to 2.82% on eil51, from 30.66% to 5.43% on kroA100, and from 27.82% to 7.17% on the 1,002-city pr1002.
• The residual gap drifts gently upward with instance size, from 2.82% at 51 cities to 7.17% at 1,002. A larger instance offers a combinatorially richer landscape of local optima, and one descent from a single greedy starting tour explores only a narrow basin of it.
• Runtime scaling splits sharply between the two stages. Construction fits a near-linear power law with exponent 1.09 (R² = 0.988), while the local search fits a slightly super-cubic law with exponent 3.10 (R² = 0.999); both fits are tight enough that runtime is highly predictable from size alone on these geometric instances.
• The quality–runtime trade-off is stark in absolute terms. On pr1002 the construction takes about 7.5 milliseconds to reach 27.82% above optimum, and 2-opt then spends 91.531 seconds — four orders of magnitude longer — to bring the gap to 7.17%.
• The constant-time move evaluation that makes 2-opt affordable depends on the distance matrix being symmetric, because reversing a subsegment flips every internal edge and only symmetry leaves their combined contribution unchanged. All five matrices were verified symmetric with a zero diagonal, and every returned tour was validated as a genuine Hamiltonian cycle with its length independently recomputed.

How it was done

Five symmetric instances from the TSPLIB library — eil51, berlin52, kroA100, ch150 and pr1002 — were parsed and their edge weights computed under the exact rounded-Euclidean convention the library specifies, since the published optima are defined against those integer weights and any other rounding rule would render the gaps meaningless. The metric was checked against a known reference value, and full integer distance matrices were precomputed to give constant-time lookups in the search inner loop. Construction started from a fixed city and repeatedly appended the closest unvisited one; the 2-opt search then scanned position pairs in a fixed order, applied the first move with a negative length delta, and restarted the scan, continuing until no improving move remained. Runtimes for the two stages were measured separately on a monotonic high-resolution clock and fitted to a power law by ordinary least squares in log–log space.

Data sources

• TSPLIB symmetric travelling-salesman library — eil51 (51 cities), berlin52 (52), kroA100 (100), ch150 (150) and pr1002 (1,002), all rounded-Euclidean with published optimal tour lengths
• Reinelt, ORSA Journal on Computing 3:376 (1991) — the TSPLIB benchmark library
• Rosenkrantz, Stearns & Lewis, SIAM Journal on Computing 6:563 (1977) — worst-case analysis of nearest-neighbour construction
• Johnson & McGeoch, Local Search in Combinatorial Optimization (1997) — reference empirical study of 2-opt quality
• Croes, Operations Research 6:791 (1958) and Lin & Kernighan, Operations Research 21:498 (1973) — the 2-opt move and its variable-depth successor