Research On Path Planning Based On The Shortest Time Principle

Intelligent vehicle navigation terminal is an important node in the internet of vehicle(IOV). It can improve the efficiency of the trip when the number of cars is increasing and the traffic conditions become worse and worse. Drivers choose the route through the path planning of intelligent vehicle navigation terminal. Path planning can choose the best route according to some conditions,such as distance and time. Along with the country thinking highly of IOV and the accelerated pace of life, a study on path planning algorithm of the shortest time principle and its functions realization method in the vehicle navigation system can help to meet people's actual travel demand and provide the basis for the specific development of IOV. The thesis focus on the research of the storage structure of network data and path planning algorithm of the shortest time principle based on the research of map data storage technology, and study implementation and verification method of the path planning algorithm in vehicle navigation system. The main contents are as follows:1. Study on the map data storage technology.A binary data storage method is designed to store map data based on analyzing map data model and the actual needs, and the data occupy less memory space. It can separate attribute information from geometric data information in an interactive indexing storage way. Because the calculation of conversing the longitude and latitude coordinates to plane coordinates is complex,this paper establish a linear transformation model to converse rapidly the longitude and latitude coordinates in ECEF to the plane coordinates in local coordinate system. Integer data type is used instead of floating-point data under the conditions of ensuring the accuracy of map. It can further reduce the data storage space, improve the efficiency of conversing map data to the screen coordinate and speed up the map rendering speed.2. Study on the storage method of road network data.The road network based on map data are the basic of path planning, the quality of road network directly affects the efficiency of path planning algorithm. In order to accelerate the expansion speed and reduce storage space,a node forward extension structure is designed to store topological relation data structure of network. Calculation methods of different types weights of the road based on time is analyzed, and the time is also stored as part of network data to get the time weight of road in path planning algorithm.3. Research on path planning algorithm.Dijkstra algorithm and A* algorithm are focused on, and their differences are compared in search space and execution time. Because the beginning and end points in practical application are the specific goal points that are independent from road, start point and end point are matched to the road node. On this basis, according to the project requirement,real-time traffic is simulated by establishing road database. The dynamic travel time of road is calculated by combining road database with the attribute data. An improved A* algorithm is proposed. The node estimation, time prediction algorithm and the implementation process of the improved A* algorithm are built.4. Realization of the path planning algorithm based on the shortest travel time in vehicle navigation system.The vehicle navigation system is completed based on Linux operating system,and ARM is control core. Its main functions include map display, map zoom and roaming,searching target and interest point, real-time positioning, map matching, path planning and path guidance. As the core function of vehicle navigation system, the commonly path planning of the shortest travel time is completed, which the shortest distance instead of the shortest travel time. And the path planning of the shortest travel time based on road database is realized through combining the road database data and the natural data of road and estimating travel time of every road. The shortest travel time path planning based on road database and the commonly shortest travel time path planning are compared, then ascertain the former having less travel time and prove the advantage of the former. Further tests show that the mean time of searching the optimal path in vehicle navigation system via the algorithm is only 2.9 seconds. Finally, the route guidance experiment based on the results of path planning proves that the results of this research are practical.