On estimating the distribution of optimal traveling salesman tour lengths using heuristics

摘要: The traveling salesman problem is an important combinatorial optimization due to its significance in academic research and real world applications. has been extensively studied much known about polyhedral structure algorithms for exact heuristic solutions. While most work concentrated on solving the deterministic version of problem, there also some stochastic TSP. Research TSP asymptotic properties estimation TSP-constant. Not is, however, probability distribution optimal tour length. In this paper, we present empirical results based Monte Carlo simulations symmetric Euclidean Rectilinear TSPs. We derive regression equations predicting first four moments estimated lengths using heuristics. then show that a Beta gives excellent fits small moderate sized problems. parameters distribution. Finally predict constant two alternative approaches.