Solving traveling salesman problems with ant colony optimization algorithms in sequential and parallel computing environments: A normalized comparison

In recent years some comparative studies have explored the use of parallel ant colony optimization (ACO) algorithms over the traditionally sequential ACOs to solve the traveling salesman problem (TSP). However, these studies did not take a systematical approach to assess the performance of both algorithms on a comparable ground. In this paper, we aim to make a comparison of both the quality of the solutions and the running time as a result of the application of a sequential ACO and a parallel ACO to Eil51, Eil76 and KroA100 on a normalized and thus, comparable ground. Our study reaffirmed that the parallel algorithm is superior in computing efficiency over the sequential algorithm, particularly for larger TSPs. We also found that such a comparison could be meaningless if the size of the TSPs keeps increasing. We revealed that the worst solution among 10 repeated runs obtained from the parallel ACO was still better than the best solution among 10 repeated runs obtained from the sequential ACO, though both did not reach the global optimal solution within 300 iterations. The proposed parallel ACO has a very high consistency because at least one best solution was found within an error of 0.5% to the global optimal solution in every three repeats for all three cases. © 2018, International Association of Computer Science and Information Technology