4.5 Article

Optimal TSP tour length estimation using standard deviation as a predictor

Journal

COMPUTERS & OPERATIONS RESEARCH
Volume 148, Issue -, Pages -

Publisher

PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2022.105993

Keywords

Traveling salesman problem; Estimator; Prediction

Ask authors/readers for more resources

This article investigates the effectiveness of using the standard deviation predictor for predicting optimal tour lengths in the traveling salesman problem. They update and extend previous computational experiments and empirically reveal the relationship between the standard deviation predictor and the predictor for Euclidean instances, validating its effectiveness in different types of instances.
For a given set of traveling salesman problem (TSP) instances, the optimal tour lengths of these instances can be predicted reasonably well using the standard deviation of random tour lengths. This surprising result was first demonstrated in a paper by Basel and Willemain (2001). In our paper, we first update and extend these earlier authors' computational experiments. Next, we seek to answer the question: Why does such a simple predictor work? In response, we reveal the relationship between the standard deviation predictor and root the well-known predictor for Euclidean instances. We also empirically show that the standard deviation predictor is valid for both Euclidean and non-Euclidean instances by applying it to the TSPLIB, randomly generated instances, and real-world instances.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available