Algorithm Of Dijkstra And A～* Apply To Route Planning In Vehicle Navigation System

This thesis is about the Vehicle Navigation System. It is animportant part of the intelligent transportation system. Except showingthe electronic map and Vehicle position, the system could also queryinformation and plan an optimum route for guiding the driver to thedestination, thereby enhance the efficiency of the transportation. TheVehicle Navigation System is one of effective ways to resolve the trafficproblems.The system is very important to our daily life. Today more andmore families have their cars, Therefore the transportation of our citywill become increasingly complex. The Vehicle Navigation technologycould convenience people's daily life. It holds a very nice future ofapplications.The primary function of a Vehicle Navigation System shows asfollows: orientating, mapping, route planning, querying, real-timeguiding. The internal configuration of the system is comprised by:Platform layer, DataServer layer, technique layer and UserInterfacelayer. According to its function, every layer has been divided intodifferent modules. The modules which contact with each other supportthe whole system.This article mainly discusses the module of route planning. In theVehicle Navigation System, route planning means: with knowing ofvehicles position and destination, the system could find one or morelow-cost route from vehicle to destination, according to the conditionset by customs. (Here the cost means time, distance, etc. set bycustoms). Route planning is the most basic function in a VehicleNavigation System. Without this function, all magnificent interfaces willbe a hollow shell. So it is especially important to know this module.The main function of this module is: Normal Planning, Reroute,Detour, Pre-Searching, Recovery, Smooth Making, Time BandThinking and so on. The process of realization flow as follows: acceptthe request, make parameters, make term, confirm join level, shapesearch and up search, connect search and edit route.In this article, the route planning function is based on the algorithmof Dijkstra and A*. Dijkstra is an effective algorithm for calculating thesmallest cost between two points. A* is almost same as Dijkstra. Theonly difference is that A* which using evaluating function, can guide thealgorithm firstly to search the node that nearer to the goal node. So it isfaster than Dijkstra, and it is an optimization to Dijkstra. The algorithmof Dijkstra and A* is the key algorithm of this function, it is also the keywhether or not the function could success in application. In order to getan optimum route form Vehicle to destination, the system needs toread huge information data of a map. As we know, Vehicle NavigationSystem belongs to embedded software. The requirement of thememory in this system is much higher than in PC. So in the realization,It is very important that how to use reasonably both of algorithms.In this article, by comparing and analyzing several groups data,we can get such conclusion that the method described in this articlegenerally use less memory than the method which only use thealgorithm of Dijkstra, it is obvious optimization to Dijkstra algorithm.In embedded Vehicle Navigation Systems, memory is veryvaluable resources. So we should reduce memory use not only inalgorithm itself, but also in other aspects. At the same time, as aproduct, software must be assured that the program is strong enoughin all aspects to prevent from being damaged which may caused byusers' illegal operations.In addition, in order to be easy for reader to understand, also formy expatiation, the paper introduced the electronic map in the fifthchapter, which is one of footstone in supporting the system. The mapdata is the foundation of a Vehicle Navigation System. The map datawas stored by levels and blocks, because of the wide and hugegeography information, so we can use it comfortably.