Harnessing Meta-Heuristic Algorithms to Optimize Travelling Salesman Problem
Aryan Kothari, V. R. N. S. Nikhil, Namana Rohit, Apurvanand Sahay · 2024
The Traveling Salesman Problem (TSP) is a challenging combinatorial optimization problem classified as NP-hard. This paper investigates the performance of various meta-heuristic algorithms, including Brute Force, Greedy, Dynamic Programming, Divide and Conquer, Simulated Annealing, Christofides, Lin-Kernighan-Helsgaun (LKH), Optimized LKH, Ant Colony Optimization, and Particle Swarm Optimization. The goal is to determine their effectiveness in solving large-scale TSP instances by focusing on solution quality and computational efficiency. Using a dataset of 256 cities, each algorithm was evaluated based on execution time and the cost of the final path. The Christofides algorithm proved the most balanced, with a time of 0.5027 seconds and a cost of 1321, making it the best in terms of cost efficiency. Simulated Annealing emerged as the fastest, completing in 0.095 seconds, while the Brute Force method, despite guaranteeing optimal solutions, was impractical for large datasets due to its exponential time complexity. The Greedy algorithm, although faster than some, often resulted in suboptimal solutions. This study underscores the importance of selecting the appropriate algorithm based on specific problem parameters and highlights the potential for future research in hybrid algorithms and parallel computing to further enhance performance.