Adaptive Ant Colony Optimization Using Node Clustering with Simulated Annealing

Multiple fields, including transport, and engineering, require finding the shortest route. This problem is known as the traveling salesman problems (TSP), which is an \(\mathcal{N}\mathcal{P}\) -hard combinatorial optimization problems. As the number of cities increases, finding the shortest path in TSP, considering all combinations, becomes challenging. The ant colony optimization (ACO) has been proposed as a solution to TSP. However, the performance of the ACO heavily depends on its parameters. In addition, finding appropriate settings of parameters for each problem is time-consuming. To address this, an adaptive ant colony optimization with node clustering (AACO-NC) has been proposed. AACO-NC uses both node clustering and effective pheromone evaporation to find the shorter route. Despite its strength, our preliminary experiments suggest that the pheromone updates restrict the solution search range. Consequently, finding a good solution becomes increasingly difficult as the search progresses. Therefore, we implement the simulated annealing (SA) method to expand the solution search space and to escape from the local optimum solution. Numerical experiments demonstrate that the proposed method outperforms the conventional method on a variety of benchmark problems, yielding a smaller error rate between the optimal solution and the mean value.