Research Of Map-Matching And Route Planning Algorithms In Vehicle Location And Navigation System

Map-Matching and Route Planning Algorithms are core contents which are studied in GPS Vehicle Location & Navigation System(VLNS). Their results decide directly the development of VLNS and then influence the improvement of Intelligent Transportation System(ITS). Then the going convenience of customer is provided, thus the problems of transportation stop, environment pollution and traffic accident are effectively alleviated.On the basis of describing VLNS related knowledge in detail, Map-Matching and Route Planning Algorithms are researched emphatically. For Map-Matching Algorithm, a new method that History Track Deduction Matching Method which has fast matching velocity and low matching precise is adopted when angle is small and Curve Imitated Method which has slow matching velocity and high matching precise is used when angle is large. Consequently, higher matching precise and more fast matching velocity are obtained. For Route Planning Algorithm, on the basis of understanding deeply classic shortest path algorithms, forward-pointed arcs method and A* algorithm are adopted which both save memory space and shorten running time and raise searching efficiency, and then the limited(such as necessary node, avoided node, and so on) Optimum Planning Algorithm is realized. The two algorithms are programmed and realized in Visual Basic 6.0. Consequently, the applied software development is fulfilled in VLNS.