Leveraging TSP Solver Complementarity through Machine Learning

TLDR

The Travelling Salesperson Problem (TSP) is a well‑studied NP‑hard problem with many solution approaches and solvers developed over the years. The study compares five state‑of‑the‑art inexact TSP solvers on benchmark instances, demonstrates their complementary performance, and builds an algorithm selector that chooses the best solver per instance, achieving markedly better performance than any single solver. The authors directly compare the solvers, construct the selector, and analyze it to understand the factors driving its improved performance. Complementary performance among solvers was observed, and the selector achieved significantly better results than the single best solver, with analysis revealing the underlying drivers of this improvement.

Abstract

The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers—namely, LKH, EAX, restart variants of those, and MAOS—on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement.