An Improved Approximation Algorithm for Symmetric & Asymmetric TSP Problems

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