Comparative Analysis of Optimization Algorithms on the Travelling Salesman Problem: Insights from TSPLIB Benchmarking

Abstract

This study submits a comprehensive comparative analysis of three advanced optimization algorithms applied to the classic Traveling Salesman Problem (TSP), a cornerstone of combinatorial optimization. The chosen algorithms are the Ant Colony Optimization, Particle Swarm Optimization, and Gray Wolf Optimization, were evaluated on nine standard cases from the TSPLIB95 library: att48, berlin52, st70, eil76, brg180, pa561, gr666, pr1002, and pr2392, reflecting varying problem sizes and complexities. Results, such as random variance, best path length, relative error, and mean ± standard deviation, were obtained after each algorithm was executed in 30 independent runs. The findings provide empirical insights into the strengths, limitations, and scalability of each algorithm across different problem sizes. It is worth noting that the ACO and PSO algorithms demonstrate a superior balance between solution accuracy and robustness, making them promising candidates for solving large-scale combinatorial problems. They also highlight the importance of statistical validation and analysis of variance in comparative optimization studies, and provide valuable insights into the suitability of algorithms across various TSP metrics.