A metaheuristic ant colony optimization algorithm for symmetric and asymmetric traveling salesman problems

Abstract

This research addresses solving two types of Travelling Salesman Problems (TSP) which are the symmetric TSP (STSP) and the asymmetric TSP (ATSP). The TSP is a problem of finding a minimal length closed tour that visits each city once. If the distances between each pair of cities are the same in both directions, the problem is a STSP, otherwise, it is an ATSP. In this thesis, a new metaheuristic algorithm which is based on Ant Colony Optimization (ACO) is proposed to solve these problems. The key idea is to enhance the ability of exploration and exploitation by incorporating a metaheuristic approach with an exact method. A new strategy for creating ‘Intelligent Ants’ is introduced to construct the solution tours. This strategy aims at reducing the computational time by heuristically fixing part of the solution tour and improving the accuracy of the solutions through the usage of a solver, specifically for large size instances. Moreover, this proposed algorithm employs new ways of depositing and evaporating pheromone. A different approach of global updating of pheromone is proposed in which the pheromone is deposited only on the edges belonging to the colony-best ant and evaporated only on the edges belonging to the colony-worst ant that are not in the colony-best ant. Additionally, the parameters of the proposed algorithm which include the number of colonies, the number of ants in each colony, the relative influence of the pheromone trail 𝛼 and the pheromone evaporation rate 𝜌 are expressed as a function of the problem size. Comparisons with other sets of parameter values suggested in the literature have been investigated which illustrate the advantages of the choice of the proposed parameter settings. Further, in order to evaluate the performance of the proposed algorithm, a set of standard benchmark problems from the TSPLIB with up to 442 cities were solved and the results obtained were compared with other approaches from the literature. The proposed algorithm has proven to be competitive and shows better performance in 63% of the 16 algorithms in terms of solution quality and obtained the optimum solutions in 70% of the 33 instances, proving that it is a good alternative approach to solve these hard combinatorial optimisation problems.