Design And Practice Of Route Planning Algorithm In Vehicle Navigation System Based On STL

Transportation is playing an important role in national economic progress. And problems resulted from heavy traffic are more and more serious and has been become a bottleneck related urbanization progress for a long time. Therefore, Intelligent Transportation System (ITS) comes into being. GIS-T, as a typical application of ITS, has been a significant study branch of GIS. Vehicle Navigation System (VNS) is an essential part of GIS-T. And route-planning module is an indispensable function in VNS. Route-planning algorithm, which runs in embedded devices compared with personal computer, should be improved in time consuming and memory storage.Based on Microsoft Visual C++ 6.0 Environment, using C++ standard template library, the paper designs and practices a bidirectional heuristic A* algorithm.Main contents are summarized as followings:Firstly, based on graph theory, the paper utilizes STL to implement data organization of road network effectively.Secondly, the paper computes road segment weight by considering distance and turning angle simultaneously according to high-level road priority to lower.Thirdly, Dijkstra and heuristic algorithms are explained and compared. Then according to characteristics of route planning in VNS, bidirectional heuristic A* algorithm is proposed and implemented. And practice results are given and analyzed.Finally, the paper implements map displaying and view operation of zooming in, zooming out, resuming origin map, pan and etc.