International Journal of Science and Research (IJSR)

International Journal of Science and Research (IJSR)
Since Year 2012 | Open Access | Double Blind Reviewed

ISSN: 2319-7064


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


How to Download this Article?

You Need to Register Your Email Address Before You Can Download the Article PDF


How to Cite this Article?

Douglas Yenwon Kparib, Stephen Boakye Twum, Douglas Kwasi Boah, "An Improved Ant Colony System Algorithm for Solving Shortest Path Network Problems", International Journal of Science and Research (IJSR), Volume 7 Issue 12, December 2018, pp. 1123-1127, https://www.ijsr.net/get_abstract.php?paper_id=ART20193716

Similar Articles with Keyword 'Shortest path'

Downloads: 105

Research Paper, Mathematics, India, Volume 3 Issue 11, November 2014

Pages: 1173 - 1176

Characteristics of Fuzzy Petersen Graph with Fuzzy Rule

Dr. G. Nirmala [5] | P. Sinthamani [2]

Share this Article

Downloads: 117

Research Paper, Mathematics, India, Volume 4 Issue 2, February 2015

Pages: 2074 - 2081

Hybrid Crossover - Mutation Pair for Genetic Algorithm in Solving Fuzzy Shortest Path Problem - Predominant and Subordinate Ants

V. Anusuya | R. Kavitha [15]

Share this Article
Top