The anteater analysis: a comparison of traveling salesman tour construction methods and their global frequencies
Date
2022
Authors
Ourada, Shannon A., author
Whitley, Darrell, advisor
Ghosh, Sudipto, committee member
Clegg, Benjamin, committee member
Journal Title
Journal ISSN
Volume Title
Abstract
For the Traveling Salesman Problem (TSP), many algorithms have been developed. These include heuristic solvers, such as nearest neighbors and ant colony optimization algorithms. In this work, the ATT48 and EIL101 instances are examined to better understand the difference between biased and unbiased methods of tour construction algorithms when combined with the 2-opt local search operator. First, a sample of tours are constructed. Then, we examine the frequencies of global edges of different sizes using n-grams. Using 2-opt as the tour improvement algorithm, we analyze randomly initialized local optima compared to nearest neighbors local optima as well as ant colony solutions with and without 2-opt. This comparison serves to better understand the nature of these different methods in their relation to the global optimum. We also provide some ways the algorithms may be adapted to take advantage of the global frequencies, particularly the ant colony optimization algorithm.
Description
Rights Access
Subject
graph algorithms
ant colony optimization (ACO)
traveling salesman problem (TSP)