A novel hybrid algorithm for the dynamic shortest path problem

摘要

For the dynamic shortest path problem, a novel hybrid algorithm DSP is designed, which embeds the ant colony algorithm into the A algorithm. Considering both the speed of searching and the quality of solution, in DSP algorithm, the evaluation function and the means of selecting next expanded node in A algorithm as well as searching strategy and related parameters in the ant colony algorithm are improved firstly, then the current saved path, obstruction isolation search and the novel dynamic path planning method are proposed. 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 within a shorter period of time on road networks of any scales, especially more effectively on the large scale.