Προσεγγιστικοί αλγόριθμοι του προβλήματος του περιοδεύοντος πωλητή

Λαμπάτος, Παναγιώτης Γ.

Approximation algorithms for the travelling salesman problem

Master Thesis

Author

Λαμπάτος, Παναγιώτης Γ.

Date

2014-06-26

Abstract

This paper presents the Traveling Salesman Problem (TSP) and the approximation algorithms solving it. The problem consists in trying to find the most economical - optimal tour, to be followed by a traveling salesman in order to visit each city from a set of cities, exactly once, starting and ending at the same city. Solving the problem has proven to be very difficult and the problem is classified as NP-hard due to the fact that for a large number of cities the time required for all calculations are virtually inconceivable. The paper begins with the historical presentation of the problem and its applications. It is followed by a presentation of the complexity of the problem and its variants. Further on, we present the exact algorithms for TSP, which find the optimal tour for the problem and for this reason they perform well only in few cities problems. Then we present the heuristics algorithms, which provide solutions that are proven close to optimal in a much shorter time. Depending on the technique they use they are categorized as construction and improvement heuristics. Next we present constant ratio approximation algorithms and finally the Polynomial Time Approximation Schemes, PTAS, for the Euclidean-TSP problem.