A distribution-free TSP tour length estimation model for random graphs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Traveling Salesman Problem (TSP) tour length estimations can be used when it is not necessary to know an exact tour, e.g., when using certain heuristics to solve location-routing problems. The best estimation models in the TSP literature focus on random instances where the node dispersion is known; those that do not require knowledge of node dispersion are either less accurate or slower. In this paper, we develop a new regression-based tour length estimation model that is distribution-free, accurate, and fast, with a small standard deviation of the estimation errors. When the distribution of the node coordinates is known, it provides a close estimate of the well-known asymptotic tour length estimation formula of Beardwood etal. (1959); more importantly, when the distribution is unknown or non-integrable so Beardwood etal.s estimation cannot be used, our model still provides good, fast tour length estimates.