A hybrid technique for single-source shortest path-based on A* algorithm and ant colony optimization

Sameer Alani, Atheer Baseel, Mustafa Maad Hamdi, Sami Abduljabbar Rashid

Abstract


In the single-source shortest path (SSSP) problem, the shortest paths from a source vertex v to all other vertices in a graph should be executed in the best way. A common algorithm to solve the (SSSP) is the A* and Ant colony optimization (ACO). However, the traditional A* is fast but not accurate because it doesn’t calculate all node's distance of the graph. Moreover, it is slow in path computation. In this paper, we propose a new technique that consists of a hybridizing of A* algorithm and ant colony optimization (ACO). This solution depends on applying the optimization on the best path. For justification, the proposed algorithm has been applied to the parking system as a case study to validate the proposed algorithm performance. First, A*algorithm generates the shortest path in fast time processing. ACO will optimize this path and output the best path. The result showed that the proposed solution provides an average decreasing time performance is 13.5%.

Keywords


A* algorithm, Ant colony optimization, Parking system, Single-source shortest path

Full Text:

PDF


DOI: http://doi.org/10.11591/ijai.v9.i2.pp356-363

Refbacks

  • There are currently no refbacks.


View IJAI Stats

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.