The traveling salesman problem (TSP) has three characteristics common to most problems, which have attracted and intrigued mathematicians: the simplicity of its definition, the wealth of its applications, and the inability to find its optimal solution in polynomial-time.In this paper, we provide point and interval estimates for the optimal cost of several instances of the TSP, by using the solutions obtained by running four approximate algorithms—the 2-optimal and 3-optimal algorithms and their greedy versions—and considering the three-parameter Weibull model, whose location parameter represents the (unknown) optimal cost of the TSP.

CEMAT - Center for Computational and Stochastic Mathematics