Study Of Hierarchical Path Guidance Algorithm And Strategies

Optimal path-finding is one of the primary functions of path guidance sub-system in intelligent transportation system (ITS). Many researchers have extensively studied in this field whether from theory or practice. Two kinds of algorithm, which are flat algorithm and hierarchical algorithm have been proposed for optimal path finding in a road network. A flat algorithm is a kind of nonhierarchical graph-search algorithm such as Dijkstra algorithm, A search algorithm, A* search algorithm and so on. A hierarchical algorithm consists of a nonhierarchical algorithm and a set of rules for reasoning on a hierarchical data structure, in other words, a nonhierarchical algorithm provides a solution for a single level of the hierarchy and the rules state how to use the hierarchical data structure. Generally speaking, a hierarchical algorithm has better performance than a nonhierarchical algorithm when to search a satisfying path in a road network, because hierarchical data structure can reduce the number of nodes involved in a search process and allows performing the search process efficiently in a sub-network, while performance of nonhierarchical algorithm tends to deteriorate as the network size increases. Considering the existent nearest entrance method is not precisely to promoting the nodes of a lower layer road network to a higher layer, and another existent optimal entrance method can not promote them efficiently, a novel yet simple heuristic directional search technique is proposed for search a reliable entrance in this paper, and the hierarchical A* path finding algorithm, which incorporates A* search technique and heuristic directional search technique, is tested on the road network of xi'an city with a two-layer road network. The experimental results show that taking the Dijkstra algorithm as a benchmark the hierarchical A* path finding algorithm has been found to about 75.48 times faster than the Dijkstra algorithm in average. The difference between the average path distance gained by hierarchical A* path finding algorithm and average shortest path is only 0.865 kilometers and the proportion of the highest layer road is up to 69.7%. The performance comparison and analysis among three algorithms (Dijkstra algorithm, hierarchical A* path finding algorithm and hierarchical nearest-entrance path finding algorithm) indicate that hierarchical A* path finding algorithm is more practical than Dijkstra algorithm or hierarchical nearest-entrance path finding algorithm.Besides, traffic center needs send some indispensable map data to vehicles in a centrally determined route guidance system. To narrow down the communication time, propose a data prepare model named transportation meshes set circum-rectangle in this paper. This modal states that traffic center should send a special data set to vehicles that consists of the low level road segments in O-grid and D-grid and all high level road segments involved in the meshes set circum-rectangle which contains O-node and D-node. Experiments indicate that the implementation process is much efficiently in a personal computer. The model will greatly contribute to time savings in the communication between traffic center and vehicles so that provide a better service to vehicles when compared with traditional method.Finally, a path finding system is designed and implemented based on the MapXtreme2005 6.6 and Visual Studio.net 2005, which is composed of three parts: spatial database, layer of core algorithms, and user interface. This system depends on a DLL module to search the path that users need, and the DLL module is implemented by the programming language c++ via creating a VC++ library project. MapXtreme2005 6.6 only supports the programming language Visual Basic and Visual C#, so the method that Visual Basic application program calls the C++ DLL module is adopted to implement the system.