Traveling salesman problem
Stencek, Jakub (2013)
Stencek, Jakub
Jyväskylän ammattikorkeakoulu
2013
All rights reserved
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-201305189397
https://urn.fi/URN:NBN:fi:amk-201305189397
Tiivistelmä
The main target of this bachelor's thesis was to analyze and solve this classic
optimization task. The traveling salesman problem is a very demanding optimization
problem for which there is no universal algorithm to solve this problem optimally.
The purpose or this thesis was not to find an optimization algorithm but to find and
to try out the known and usually used algorithms and compare their solution with a
solution of the author's own algorithm. The first part focuses on the origin and partly
expert description of this problem, the actual state of possibilities of solutions and
supposed development in “not so far” future. The second part concentrates on the
software which was made for solving the traveling salesman problem. This software
was made in Java programming language and it is attached to this thesis. The third
part is focused on the analysis and implementation some of current possible
solutions. Four known algorithms are implemented and the fifth is an exact
algorithm. This fourth part is focused on developing, testing the author's own
algorithm and its evaluation. This algorithm is based on a simple genetic algorithm
but radically adjusted. The final chapter is focused on evaluation of algorithms and
comparison of their results.
This thesis showed that even a simpler algorithm can achieved quite good value of
the solution. Probably the best implemented solution was Christofides algorithm
which can be recommended as primary algorithm to solve the traveling salesman
problem or to start with the heuristic solution.
optimization task. The traveling salesman problem is a very demanding optimization
problem for which there is no universal algorithm to solve this problem optimally.
The purpose or this thesis was not to find an optimization algorithm but to find and
to try out the known and usually used algorithms and compare their solution with a
solution of the author's own algorithm. The first part focuses on the origin and partly
expert description of this problem, the actual state of possibilities of solutions and
supposed development in “not so far” future. The second part concentrates on the
software which was made for solving the traveling salesman problem. This software
was made in Java programming language and it is attached to this thesis. The third
part is focused on the analysis and implementation some of current possible
solutions. Four known algorithms are implemented and the fifth is an exact
algorithm. This fourth part is focused on developing, testing the author's own
algorithm and its evaluation. This algorithm is based on a simple genetic algorithm
but radically adjusted. The final chapter is focused on evaluation of algorithms and
comparison of their results.
This thesis showed that even a simpler algorithm can achieved quite good value of
the solution. Probably the best implemented solution was Christofides algorithm
which can be recommended as primary algorithm to solve the traveling salesman
problem or to start with the heuristic solution.