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

ÇAVDAR B., Sokol J.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol.243, no.2, pp.588-598, 2015 (SCI-Expanded) identifier identifier

  • 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.