Optimal TSP tour length estimation using standard deviation as a predictor

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.

Automated summary

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.