Traveling salesman problem

The main target of this bachelor's thesis was to analyze and solve this classic\noptimization task. The traveling salesman problem is a very demanding optimization\nproblem for which there is no universal algorithm to solve this problem optimally.\nThe purpose or this thesis was not to find an optimization algorithm but to find and\nto try out the known and usually used algorithms and compare their solution with a\nsolution of the author's own algorithm. The first part focuses on the origin and partly\nexpert description of this problem, the actual state of possibilities of solutions and\nsupposed development in “not so far” future. The second part concentrates on the\nsoftware which was made for solving the traveling salesman problem. This software\nwas made in Java programming language and it is attached to this thesis. The third\npart is focused on the analysis and implementation some of current possible\nsolutions. Four known algorithms are implemented and the fifth is an exact\nalgorithm. This fourth part is focused on developing, testing the author's own\nalgorithm and its evaluation. This algorithm is based on a simple genetic algorithm\nbut radically adjusted. The final chapter is focused on evaluation of algorithms and\ncomparison of their results.\nThis thesis showed that even a simpler algorithm can achieved quite good value of\nthe solution. Probably the best implemented solution was Christofides algorithm\nwhich can be recommended as primary algorithm to solve the traveling salesman\nproblem or to start with the heuristic solution.