The Traveling Salesman Problem is finding the shortest path through all the cities, where each city is visited precisely once, while the first and the last city are the same. This can be formulated as searching for the shortest cycle in a graph which visits each vertex exactly once.
Finding the optimal solution is practically fruitless due to the time complexity of the problem.
Heuristic algorithms are good alternatives to algorithms, which search for the optimal solution, because a solution can be found in a practically achievable time frame; however, the guarantee of the solution being optimal is lost.
The introduction of this work includes a basic description of The Traveling Salesman Problem, which is followed by a list of practical applications, a detailed description of the problem, the classification of heuristic algorithms and the details of the experimental environment.
The main part of this work includes six algorithms, which were implemented and tested.
The selected algorithms are Local Search with the k-opt operation; Lin-Kernighan algorithm; Simulated Annealing; Ant Colony Algorithm; Particle Swarm Optimization and Wolfpack algorithm.
The final part of this work is a comparison of the results from each algorithm and a commentary on the methodology that was used for the comparison of the algorithms.
|
