关键词: 城市交通, 动态路径诱导, 时间最短路径, LPA*, D* Lite, A*

Abstract: A new dynamic time-dependent shortest route planning easily implemented for urban vehicle guidance system is proposed in this paper, based on which computing time of Dijkstra, A*, D* Lite algorithms are compared and analyzed in a large experiment square graph. To meet the real-time needs of the in-vehicle dynamic navigation equipment, a hopping dynamic path planning strategy based on network changes is proposed to reduce the computing time, which picks more effective searching way in light of specific change situation. E-map and history traffic volume data of Dongguan city is used to tests the strategy and the result shows that the strategy is effective and feasible, and the time cost if dynamic route planning can be significantly reduced.

Key words: urban traffic, dynamic route guidance, time-dependent shortest path, LPA*, D* Lite, A*