The travelling salesman problem

In the travelling salesman problem we are given a graph. The task of the salesman is to find the shortest (or cheapest) possible route by visiting each vertex (that represents cities) exactly once and returning to the initial vertex (city). A Hamilton cycle is a cycle in a graph, in which each vertex is visited only once. In the travelling salesman problem we are thus searching for a Hamilton cycle with a minimum price. The problem was posed in 19th century by the Irish mathematician W. R. Hamilton. Today, this is one of the most intensively studied problems in combinatorial optimization. The travelling salesman problem belongs to the class of NP-hard problems. In particular, this means that we (so far) cannot construct a polynomial-time algorithm that would solve this problem. The bachelor's thesis deals with exact and approximation algorithms for solving the traveling salesman problem. We present an exact Concorde algorithm for solving symmetric traveling salesman problems and use it to examine how good two approximation algorithms are: the nearest neighbour algorithm and the double-tree algorithm. We also explore applicability of the travelling salesman problem to various problems encountered in the fields of science and engineering.