Downloads: 127

Research Paper | Mathematics | Ghana | Volume 7 Issue 12, December 2018

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

Douglas Yenwon Kparib | Stephen Boakye Twum | Douglas Kwasi Boah

Abstract: 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.

Keywords: Shortest path, Network, Label-setting, Label-correcting, Ant colony system, Algorithm, Dynamic programming

Edition: Volume 7 Issue 12, December 2018,

Pages: 1123 - 1127

Similar Articles with Keyword 'Shortest path'