International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Call for Papers | Fully Refereed | Open Access | Double Blind Peer Reviewed

ISSN: 2319-7064

Downloads: 127 | Views: 187

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

How to Download this Article?

Type Your Valid Email Address below to Receive the Article PDF Link

Verification Code will appear in 2 Seconds ... Wait