The application of machine learning models to optimal TSP tour length estimation

Abstract

The traveling salesman problem (TSP) is a well‐known NP‐hard problem in combinatorial optimization, with numerous applications in logistics and elsewhere. This paper introduces a machine learning‐based approach to estimate the optimal tour length of the TSP, using linear regression, random forests (RF), and neural networks, including Kolmogorov–Arnold networks (KANs).

A key limitation of one of the most accurate published neural‐network estimators for the TSP is that it relies on size‐specific architectures: Each model is bound to a fixed instance size and cannot be applied to larger instances without retraining. We address this through size‐independent features enabling bidirectional scalability: a single model applicable to instances of any size without retraining. Under equivalent conditions, our best model achieves 1.51% mean absolute percentage error, outperforming the state‐of‐the‐art approach (2.02%).

We conduct systematic generalizability analysis on challenging out‐of‐distribution instances, such as instances (a family of instances whose two‐dimensional projections form the edges of a tetrahedron) and on triangular distributed instances, revealing that KAN models generalize remarkably well, while RF requires representative training examples from each distribution. Through KAN's interpretability framework, we extract analytical formulas that recover classical relationships from early theoretical work, bridging machine learning and traditional analytical methods.

Our findings provide practical guidance for model selection and demonstrate that machine learning techniques can achieve high accuracy, robust generalization, and interpretability for TSP tour length estimation.