SH: A Novel Method for the Dynamic and Shortest Path Problem

Abstract:

For the dynamic and shortest path problem, a novel algorithm SH(simulate human) is designed by simulating the process of our searching path in real life. The algorithm adopts the idea of heuristic search and integrates with the ant colony algorithm, in which the saved current path, the idea of “ask once every junction”, the bypassing barrier search and other some related definitions are proposed, as well as the ant colony algorithm is improved, so as to find the better solution and reduce the searching time. The experimental results show that the algorithm runs better than other existing methods. Moreover, it can find the shortest path or the approximate shortest one in a shorter time on road networks of any scales. Especially, SH algorithm is more effective for the large scale road network.

• Periodical: Advanced Materials Research (Volumes 129-131)
• Pages: 1013-1017
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.129-131.1013
• Online since: August 2010
• Authors: Ya Fei Guo, Zheng Qin, Rong Hua Guo, Lei Ji
• Keywords: Ant Colony Algorithm (ACA), Dynamic Path Problem, Heuristic Search, SH Algorithm, Shortest Path Problem

References

[1] Wei-Hsun Lee, Shian-Shyong Tseng, Sheng-Han Tsai: A knowledge based real-time travel time prediction system for urban network. Expert Systems with Applications: An International Journal, Vol. 36(2009), pp.4239-4247.

DOI: 10.1016/j.eswa.2008.03.018

[2] Liye Zhang, Tao We, Research on Flexible Architecture of Transportation Planning System Based on GIS-T, Proceedings of the 2009 WASE International Conference on Information Engineering, NW Washington: IEEE Computer Society(2009), pp.224-227.

DOI: 10.1109/icie.2009.221

[3] Chabini I, Lan S: Adaptations of the A* algorithm for the Computation of Fastest Paths in Deterministic Discrete-time Dynamic Networks. IEEE Transactions on intelligent transportation system, vol. 3(2002), pp.60-74.

DOI: 10.1109/6979.994796

[4] Anthony Stentz, The Focused D* Algorithm for Real-Time Replanning, Proceedings of the International Joint Conference on Artificial Intelligence. 1652-1659 ( 1995).

[5] Zheng Y. Mobile Robot Dynamic Path-planning Based on Ant Colony Optimization Algorithm. Chengdu: university of electronic science and technology of China(2008).