Different Methods and Their Comparison in Solving Traveling Salesman Problem
Name
Erich Jagomägis
Abstract
Traveling salesman problem is a NP-hard problem which is commonly used as an abstraction of many real life problems. It is widely used as benchmark to many optimization methods.
In given thesis we analyze various methods, describe their algorithms and benchmark their performance when solving traveling salesman problem. Furthermore we compare results.
Firstly an introduction is made to artificial neural networks. Then Hopfield neural network is introduced and applied to solving traveling salesman problem.
Secondly blind search algorithms are introduced. In given thesis we focus on depth first search and breadth first search. In both cases we introduce some optimizations to algorithms which enable them to work faster.
Thirdly heuristic search algorithms are introduced and some more common algorithms are analyzed. In given thesis nearest neighbour algorithm, best first algoritm, genetic algorithm and simulated anneal are described.
Once the algorithms and theory behind them are described, they are implemented in a java application, which is used to benchmark their performance. Application is made firsthand for students to observe how algorithms work, as well as measure their time consumption and measure the results of each algoritm.
Having done the benchmarks in this thesis, it is concluded that blind search algoritms are not suitable methods for solving traveling salesman problem. Furthermore it is concluded that Hopfield neural networks are also impractical when it comes to solving traveling salesman problem. Nearest neighbour search, genetic algorithm and simulated annealing are found to be most promising methods when solving problem described above. Most suitable method is found to be simulated annealing proving to find good solutions in relatively short time.
In the end of thesis some proposals are made, which could be further investigated by students. These proposals could benefit work done so far by improving described methods.
Mathematical functions to generate distance matrix from coordinates and vice versa are described in extras.
Graduation Thesis language
Estonian
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
Mare Koit
Defence year
2013