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

摘要：

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.

关键词： dynamic and shortest path problem ant colony algorithm heuristic search SH algorithm

作者: Yafei Guo Zheng Qin Ronghua Guo Lei Ji

作者单位: School of Software,Tsinghua University,Beijing 100084,China Department of Computer Science,Tsinghua University,Beijing 100084,China

会议类型: 国际会议

会议名称: 2010 International Conference on Material and Manufacturing Technology(2010材料与制造技术国际会议 ICMMT2010)

会议地点: 重庆

会议语种:英文

页码: 1013-1017

在线出版日期: 2010-09-17（万方平台首次上网日期，不代表论文的发表时间）