The Research Of Optimal Path Planning Algorithms In Vehicle Navigation System

Urban development and expansion brings the development of intelligent transportation. Today, urban traffic becomes more and more complicated. The increase of vehicle number, road maintenance, traffic congestion brings a great burden to urban traffic system. We can’t solve the increasingly serious traffic problems just depend on the control of urban transportation center. But Vehicle navigation system can effectively relieve the problems. Vehicle navigation system can effectively relieve urban traffic congestion, optimization of urban traffic flow, improve transport efficiency, reduce environmental pollution, etc Path planning is one of the important functions of Vehicle navigation system. It gives travelers advices to travel.Path planning algorithm is one of key factors to obtain optimal path. To obtain optimal path, generally use the vector electronic topology and the path planning algorithm. After inputting driver’s travel start and end points, then output the shortest path. Accuracy and effectiveness of algorithm directly influence the outcome of the route planning.(1) At first, we describe the production process of electronic map, establish a vector electronic map of Xian city with Maplnfo software and complete the geographic coding.(2) Dijkstra algorithm is a widely used method in path planning, but has high operation complexity because of wide search node. To solve this problem, we propose an improved Dijkstra algorithm with bucket sorting and rectangular limit search method. Firstly, using bucket sorting method converts data storage structure to adjacent table structure according to the distance size of edge. Secondly, rectangular limit search method is adopted to reduce the traverse nodes of algorithm.(3) In view of the influence factors of path planning, choose the commonly used distance, road grades and intersection waiting time as basic elements, propose a weighted road resistance function model. Fuzzy algorithm is used to determine the weighted values of road resistance function model in the real-time dynamic traffic. The process of fuzzy algorithm includes selecting fuzzy rules, setting domain, editing fuzzy table.(4) In this paper, experimental data correspond to the vector diagram of Xian city with Maplnfo. The simulation is run on MATLAB2007platform. Experiment verified the accuracy and effectiveness of improved Dijkstra algorithm and the road resistance function model, improve the efficiency of path planning algorithm.