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

Vikrant Vig, Udatta S. Palekar

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish (US)
Pages (from-to)111-119
Number of pages9
JournalEuropean Journal of Operational Research
Volume186
Issue number1
DOIs
StatePublished - Apr 1 2008

Keywords

  • TSP constant
  • Tour length
  • Travelling Salesman Problem

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'On estimating the distribution of optimal traveling salesman tour lengths using heuristics'. Together they form a unique fingerprint.

Cite this