An Improved Ant Colony System Algorithm for Solving Shortest Path Network Problems

Shortest Path Problems (SPP) are concerned with finding a path with minimum distance from one or more sources to one or more destinations through a network. With the increasing application of shortest path algorithms to network problems in real life, researchers and practitioners have begun to look outside the traditional algorithms, such as label setting and label correcting, which have some deficits compared with an algorithm such as Ant Colony. In this paper, an improved ant colony system meta-heuristic algorithm for solving SSP has been presented with modifications made in the following areas: the introduction of dynamic programming into the heuristic information, and the application of a ratio approach to the local pheromone update process. A hypothetical network problem of ten nodes with twenty edges was used as a test case. The results show that the improved ant colony algorithm outperforms the existing one in terms of the number of iterations required to converge to optimality.