The traveling salesperson problem is one of the best-known problems of combinatorial optimization. It has been continuously studied since 1930 and it asks the following question: "If we have a set of cities and a set of distances between each pair of cities, what is the shortest possible route to visit all the cities, each exactly once, and return to the starting place?" The TSP is an NP-hard problem, which means that (for the time being) we do not know the algorithm that would solve this problem in polynomial time. Since we do not always need the optimal solution, there exist approximation algorithms for this problem. For these algorithms, however, there are some key assumptions. Because of these assumptions, we can no longer deal with the general TSP. Instead, we talk about the so-called metric traveling salesperson problem. The thesis presents the TSP problem, the metric traveling salesperson problem, a detailed procedure and implementation of two currently best approximation algorithms for the metric traveling salesperson problem. In the last part, the implemented algorithms are tested, compared and analysed.
|
