The Performance of Different Algorithms to Solve Traveling Salesman Problem

Traveling salesman problem, with extensive potential applications in industries of all sorts, has been studied for decades. Although there are massive solutions put forward, the most efficient and exact way has never been widely acknowledged since this problem is typically NP-hard. We selected three types of most commonly used algorithms to solve this problem: Greedy Algorithm, Ant Colony Algorithm and Simulated Annealing Algorithm. With data sets given in TSPLIB, we computed and compared these algorithms in both the shortest distance and the time cost. Based on the statistics obtained from experiments, it can be found that Greedy Algorithm runs the fastest with a sacrifice of accuracy, whereas Simulated Annealing Algorithm searches out the shortest path in a relatively small group of cities and Ant Colony Algorithm performs even better when the points increase.