An Empirical Analysis of Approximation Algorithms for the Euclidean Traveling Salesman Problem
This is an incremental analysis comparing existing algorithms for a classical optimization problem relevant to computer science and engineering.
The paper evaluated greedy, 2-opt, and genetic algorithms for the Euclidean Traveling Salesman Problem, finding that greedy and 2-opt are efficient for small datasets, while genetic algorithms perform best for optimality on medium to large datasets but have longer runtimes.
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.