An Improved A* Algorithm for the Intelligent Transportation System
Yan Li, Yang Gao · 2009
In an intelligent transportation system (ITS), route planning is very important for vehicle navigation. It is necessary to optimize the algorithm of route planning to meet the real time requirement of the system. Based on the analysis of the temporal complicacy and spatial complicacy of the A* algorithm, this paper proposes a modified A* algorithm which can run much more efficiently compared to the original A* algorithm. First, this paper adopts the data structure of a binary heap, not a linear array, to implement the operation of its priority queue and to successfully improve the efficiency of searching the minimum cost node. Secondly, according to the special spatial distribution feature of the road network, a search mechanism to restrict the search district is introduced here, which can greatly reduce the search data volume of the algorithm. Finally, this paper makes tests in a real road network in Xi'an. The tests also prove that the modified algorithm is workable and time-saving.