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

ÇAVDAR B., Sokol J.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.243, sa.2, ss.588-598, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 243 Sayı: 2
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1016/j.ejor.2014.12.020
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.588-598
  • Anahtar Kelimeler: TSP, Tour length estimation, VEHICLE
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.