💻 computer science

A Statistically Rigorous, Held–Karp- and LKH-Validated Empirical Evaluation of a Classical 2-opt + Or-opt Local Search Pipeline for the Euclidean Traveling Salesman Problem

This paper provides a statistically rigorous, Held–Karp and LKH-validated empirical evaluation of a classical nearest-neighbor, 2-opt, and Or-opt pipeline for the Euclidean TSP, demonstrating its significant improvement over 2-opt alone and its consistent proximity to certified optimality bounds across synthetic and real-world instances.

Original authors: Mohamad Fatahi, Hamzeh Barati²

Published 2026-10-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Mohamad Fatahi, Hamzeh Barati²

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Finding the shortest possible route that visits a set of locations exactly once and returns to the start is a problem that has puzzled mathematicians and logisticians for decades. Known as the Traveling Salesman Problem, it is not merely an abstract puzzle; it underpins real-world challenges like delivering packages, drilling holes in circuit boards, and sequencing DNA. Because the number of possible routes grows explosively as more cities are added, finding the single perfect path is often impossible to calculate in a reasonable time. Instead, experts rely on "local search" methods. These are practical strategies that start with a rough route and make small, incremental improvements, swapping connections or moving segments of the path to see if the total distance shrinks. While these methods are standard tools, they are often treated as black boxes: we know they work, but we rarely measure exactly how close they get to the theoretical best, or how much better one method is than another, with strict statistical proof.

A recent study by Mohamad Fatahi and Hamzeh Barati brings this level of precision to a classic combination of these local search techniques. The researchers did not invent a new way to solve the problem. Instead, they took a well-known pipeline—starting with a simple "nearest neighbor" approach to build a first draft, then refining it with two specific improvement steps called "2-opt" and "Or-opt"—and subjected it to a rigorous, statistical audit. Their goal was to measure exactly how much better the combined method performed compared to using just the first improvement step, and to determine how close the final routes came to the absolute mathematical limit of perfection. To do this, they generated thousands of random city maps and also tested the method on four famous, real-world city maps where the perfect answer is already known.

The researchers ran their experiments on city sets ranging from 50 to 500 locations. For each size, they ran the process thirty times to ensure the results were not just luck. They compared a standard method, which only uses the first improvement step, against their hybrid pipeline that adds the second step. The results were clear and consistent: the hybrid pipeline, which adds the extra layer of refinement, produced shorter routes in every single case. On average, this extra step improved the route length by between 2.09% and 3.48% depending on the size of the problem. The statistical analysis confirmed that these improvements were not random fluctuations; the difference was significant enough to be considered a genuine gain. Furthermore, the researchers calculated a "lower bound," a mathematical floor that represents the shortest possible distance any route could theoretically achieve for that specific map. They found that their hybrid method produced routes that were only about 4.9% to 5.6% longer than this theoretical floor for the smaller maps, a gap that aligns with what experts have long expected from these types of algorithms.

To ensure their findings held up in the real world, the team tested their method on four specific, historical maps of cities like Berlin and others with known optimal solutions. In these tests, they cross-referenced their results with a highly sophisticated solver known as LKH, which is widely considered the gold standard for finding near-perfect routes. The LKH solver successfully found the exact known best routes for all four maps. The hybrid pipeline used by the researchers did not match that perfection, but it came remarkably close, with final routes ranging from 0.94% to 5.78% longer than the known best. This confirmed that the improvements seen in the random, synthetic maps translated directly to real-world scenarios. The study also tested a more complex idea: using mathematical data from the theoretical lower bound to guide the order in which the improvements were made. This attempt failed to produce any better results, a finding the authors reported transparently to save other researchers from wasting time on the same dead end.

The significance of this work lies not in a new algorithm, but in the clarity of its measurement. By combining a self-calculated mathematical floor with a gold-standard solver and rigorous statistical testing, the authors provided a definitive picture of what a classical, non-learning method can achieve. They showed that while these older techniques are not perfect, they are remarkably robust, consistently staying within a narrow margin of the best possible answer. The study serves as a solid, verified baseline, proving that even without the complexity of modern machine learning, classical methods remain powerful, predictable, and highly effective tools for solving some of the world's most complex routing challenges.

Technical Summary: A Statistically Rigorous, Held–Karp- and LKH-Validated Empirical Evaluation of a Classical 2-opt + Or-opt Local Search Pipeline

Problem Statement
The Traveling Salesman Problem (TSP) remains a foundational challenge in combinatorial optimization, with applications ranging from vehicle routing to DNA sequencing. While exact algorithms (e.g., Concorde) and advanced heuristics (e.g., Lin–Kernighan–Helsgaun, or LKH) are well-established, there is a reported gap in the literature regarding rigorous, statistically grounded empirical evaluations of classical local search heuristics (specifically 2-opt and Or-opt) against a certified optimality reference. Many existing studies compare algorithms against each other or against best-known solutions rather than against a proven lower bound, and few apply strict statistical testing protocols to classical pipelines in isolation.

Methodology
The authors evaluate a classical pipeline consisting of a Nearest-Neighbor (NN) construction phase followed by a hybrid local search of 2-opt and Or-opt. The study employs a methodological framework designed for statistical rigor:

Algorithms Evaluated:
1. NN construction alone.
2. NN + 2-opt local search.
3. NN + 2-opt + Or-opt (segment relocation with path lengths 1–3) + a final 2-opt iteration.
Optimality Reference: Instead of relying on asymptotic approximations (e.g., Beardwood-Halton-Hammersley constant) or best-known solutions, the authors compute a self-generated, guaranteed lower bound for each instance using the Held–Karp Lagrangian 1-tree relaxation via subgradient optimization.
Experimental Design:
- Synthetic Instances: 30 independent trials for Euclidean instances with $n \in \{50, 100, 200, 500\}$ points generated uniformly in a $1000 \times 1000$ square.
- Real Instances: Four TSPLIB benchmarks (eil51, berlin52, st70, kroA100) with known optimal tour lengths.
- Constraints: All algorithms operated under identical wall-clock time budgets (1.0s for $n \le 200$ , 3.0s for $n=500$ ).
Statistical Analysis: The study utilizes Bonferroni-corrected Wilcoxon signed-rank tests ( $\alpha = 0.0125$ ), bootstrap confidence intervals (2000 samples) for percentage improvements, and matched-pairs rank-biserial effect sizes ( $r$ ).
Validation: Results are cross-validated against the LKH solver, which serves as a near-exact benchmark.

Key Contributions
The paper explicitly states that its contribution is methodological and empirical, not algorithmic. The authors do not propose new local search operators; the 2-opt + Or-opt combination is a classical technique. The specific contributions are:

Statistical Rigor: Applying Bonferroni-corrected statistical testing and effect size analysis to classical local search performance, a practice noted as underreported in isolation.
Certified Benchmarking: Comparing heuristic performance against a computed Held–Karp lower bound per-instance rather than against asymptotic estimates or unverified best-known solutions.
Negative Result Reporting: Transparently reporting a "negative result" for a tested extension that attempted to order Or-opt moves using Held–Karp Lagrangian dual information (degree violations), which yielded no statistically significant benefit.
Positioning: Situating classical local search results relative to the rapidly growing field of learned/hybrid TSP solvers (e.g., Zheng et al., Zong et al.), arguing that the rigorous characterization provided here can serve as a baseline for future learning-based algorithms.

Experimental Results

Synthetic Instances: The hybrid pipeline (NN + 2-opt + Or-opt) consistently outperformed 2-opt alone by 2.09% to 3.48% across all problem sizes. These improvements were statistically significant after Bonferroni correction ( $p < 0.001$ ) with an effect size of $r = -1.00$ (indicating the hybrid solution was always better or equal in all 120 paired comparisons).
Optimality Gaps: The hybrid solutions remained within 4.9% to 5.6% of the computed Held–Karp lower bound for $n \le 200$ .
Real Instances (TSPLIB): On real-world data, the hybrid pipeline achieved gaps of 0.94% to 5.78% relative to the known optimal tour lengths. These results were consistent with synthetic findings.
LKH Validation: The LKH solver recovered the exact published optimum (0% gap) for all four TSPLIB instances, validating the experimental setup and coordinate transcription.
Extension Failure: The attempt to guide Or-opt ordering using Held–Karp degree violations resulted in no improvement (0.00% to 0.05% change, $p > 0.35$ ), suggesting that this specific LP-based heuristic ordering does not enhance the classical pipeline under the tested conditions.

Significance and Claims
The authors modestly claim that this work provides a methodologically rigorous characterization of a classical local search pipeline. They do not claim algorithmic novelty in the search mechanism itself. Instead, the significance lies in:

Establishing a statistically sound baseline for classical heuristics that can be used to evaluate future algorithms, particularly the emerging class of learned and hybrid learned/exact solvers.
Demonstrating that even classical, non-learned pipelines can be evaluated with high statistical confidence against certified bounds.
Highlighting that while learning-based approaches (e.g., RL-guided LKH) are advancing, their baselines are often measured against best-known solutions rather than certified bounds; the protocol presented here offers a complementary, rigorous standard for such comparisons.

The paper concludes by identifying future work, including scaling to larger instances with candidate-list optimizations, incorporating the Righini [20] optimized 1-tree selection for tighter bounds, and performing direct, budget-matched comparisons against the new generation of learning-based solvers (including those from 2026 literature).

Technical Summary: A Statistically Rigorous, Held–Karp- and LKH-Validated Empirical Evaluation of a Classical 2-opt + Or-opt Local Search Pipeline

More like this