Title: An Empirical Analysis of Approximation Algorithms for the Euclidean Traveling Salesman Problem,
Abstract: With applications to many disciplines, the traveling salesman problem (TSP)
is a classical computer science optimization problem with applications to
industrial engineering, theoretical computer science, bioinformatics, and
several other disciplines. In recent years, there have been a plethora of novel
approaches for approximate solutions ranging from simplistic greedy to
cooperative distributed algorithms derived from artificial intelligence. In
this paper, we perform an evaluation and analysis of cornerstone algorithms for
the Euclidean TSP. We evaluate greedy, 2-opt, and genetic algorithms. We use
several datasets as input for the algorithms including a small dataset, a
mediumsized dataset representing cities in the United States, and a synthetic
dataset consisting of 200 cities to test algorithm scalability. We discover
that the greedy and 2-opt algorithms efficiently calculate solutions for
smaller datasets. Genetic algorithm has the best performance for optimality for
medium to large datasets, but generally have longer runtime. Our
implementations is public available.