Adapting Optimal Solutions to Travelling Salesman Problem
Devika Madhusoodanan, R. Vismaya, Hridyalakshmi, Apurvanand Sahay · 2024
A comparative analysis of algorithms for the Traveling Salesman Problem (TSP) is proposed that evaluates four distinct approaches: Nearest neighbor (NN), 2-opt algorithm, Genetic Algorithm (GA), Simulated Annealing (SA) and a hybrid method of NN and 2-opt to determine its minimum distance achieved with minimum execution time. These algorithms are evaluated by their capability to find the shortest route and the total distance travelled in the given dataset. The evaluation process consists of execution time and route rendering. The results claim that the hybrid approach outsmarts all the other methods in terms of their execution time as it takes as low as 0.308 seconds as compared to other methods on the given dataset. This hybrid approach has the potential to improve the shortest distance in an iterative manner which balances the time versus distance objective criteria in a scalable manner.