Different approaches to solve Traveling Salesman Problem
Revant Kumar, Xin Wei, Aashu Singh · HAL (Le Centre pour la Communication Scientifique Directe) · 2014
In this paper, we have provided the details and implementation of different approaches to solve Traveling Salesman Problem (TSP). We have implemented five algorithms Greedy Heuristic (Farthest Insertion), MST-2 Approximation, Branch and Bound, Local Search - Hill Climbing and Local Search - Simulated Annealing. We have reported exhaustive evaluations for all the five algorithms. We have obtained our best results for the Local Search – Hill Climbing Algorithm with the solution gap within a value of 3%. It runs within 60s and achieved optimal solution for burma14.tsp and ulysses16.tsp (solution gap of 0%). The performance of our greedy algorithm (Farthest Insertion) is good with solution gap within 11%. The greedy solution is quite fast and runs within 0.1s. For branch and bound, we have achieved optimal solution for burma14.tsp and ulysses16.tsp (solution gap of 0%).