Show/Hide Menu
Hide/Show Apps
anonymousUser
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Açık Bilim Politikası
Açık Bilim Politikası
Frequently Asked Questions
Frequently Asked Questions
Browse
Browse
By Issue Date
By Issue Date
Authors
Authors
Titles
Titles
Subjects
Subjects
Communities & Collections
Communities & Collections
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
Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
DOI
https://doi.org/10.1016/j.ejor.2014.12.020
Collections
Department of Industrial Engineering, Article