A distribution-free TSP tour length estimation model for random graphs
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol.243, no.2, pp.588-598, 2015 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Volume: 243 Issue: 2
- Publication Date: 2015
- Doi Number: 10.1016/j.ejor.2014.12.020
- Journal Name: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
- Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Page Numbers: pp.588-598
- Keywords: TSP, Tour length estimation, VEHICLE
- Middle East Technical University Affiliated: Yes
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 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. (C) 2014 Elsevier B.V. All rights reserved.