Abstract:
Travelling salesman problem (TSP) is one of the fundamental and most researched problems in the study of Approximation Algorithms. Generally, the
algorithm is provided with a metric(V, d) and the aim of the algorithm is to
find a closed tour starting from any random vertex and visiting each and every
point in V with the minimal possible cost of d. It is a known NP-Complete
Problem and has key applications in the areas of logistics, planning, and cir cuit design. Although, many successful algorithms have been proposed for
the symmetric TSP problems, but generally those fail to provide adequate
results for the asymmetric problems. We have proposed a new and improved
approximation algorithm for both symmetric and asymmetric TSP problems.
For this purpose 2-opt local search technique has been used with some enhancements to generate better results. We have compared our technique
with seven other different algorithms of different types and the proposed algorithm outperforms others in error margin, time and convergence tests. To
cater complexity and time issues in bigger TSP problems, we have introduced
a graph compression technique to ensure the solution of bigger problems in a
timely manner. So here in this improved approximation algorithm, we have
achieved our major objective of receiving a solution which is quite near to
the optimum with minimal comparative computational complexity. In this
thesis, we have used a well known library TSPLIB, and compared our results with a ruin and recreate algorithm for time, error and convergence. We
have also compared the results of our algorithm with six other well known
algorithms used in this field which include the nearest neighbor, genetic algorithm, simulated annealing, tabu search, ant colony and tree physiology
optimization. The proposed algorithm clearly outperforms other algorithms
for multiple parameters
