New Heuristic Function in Ant Colony System for the Travelling Salesman Problem

Ant Colony System (ACS) is one of the best algorithms to solve NP-hard problems. However, ACS suffers from pheromone stagnation problem when all ants converge quickly on one sub-optimal solution. ACS algorithm utilizes the value between nodes as heuristic values to calculate the probability of choosing the next node. However, one part of the algorithm, called heuristic function, is not updated at any time throughout the process to reflect the new information discovered by the ants. This paper proposes an Enhanced Ant Colony System algorithm for solving the Travelling Salesman Problem. The enhanced algorithm is able to generate shorter tours within reasonable times by using accumulated values from pheromones and heuristics. The proposed enhanced ACS algorithm integrates a new heuristic function that can reflect the new information discovered by the ants. Experiments conducted have used eight data sets from TSPLIB with different numbers of cities. The proposed algorithm shows promising results when compared to classical ACS in term of best, average, and standard deviation of the best tour length.