A distribution-free TSP tour length estimation model for random graphs

Date

2015-06-01

Author

Çavdar, Bahar
Sokol, Joel

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

1
views

0
downloads

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 et al. (1959); more importantly, when the distribution is unknown or non-integrable so Beardwood et al.'s estimation cannot be used, our model still provides good, fast tour length estimates.

Subject Keywords

TSP, Tour length estimation

URI

https://hdl.handle.net/11511/51665

Collections

Department of Industrial Engineering, Article