Research Of Destination Prediction Algorithm Based On Historical Trajectories

With the rapid development of wireless communication technology, the car is not only a transportation instrument, but also an important node of the Internet. Users can get a lot of information which is needed through the cars. However, the information won’t be obtained unless the users interact with the car. Nowadays, the car can only obtain and display the information passively. But it can’t automatically perceive the needs of users and show the information that the users need. The destination prediction algorithm is an efficient algorithm which can predict the destination and the need of the users then it can provide the needed information for users. Therefore, designing a destination prediction algorithm, which has a good performance, has an important practical significance.This thesis aims at the research of the destination prediction algorithm which is based on the historical trajectory. We construct the prediction model by using the users’ individual historical trajectories, and then predict their current destination of the users. Concrete works are as follows:Firstly, we implement a map matching algorithm, which is used to eliminate the deviation between the trajectory and the road network of the electronic map. Then we do a test on the map matching algorithm that we implement. Results show that the algorithm has a high matching accuracy and efficiency.Secondly, we study and implement two kinds of destination prediction algorithm. The first one is called Sub-Trajectory Synthesis, and the other one is a destination prediction algorithm based on the probability statistic. Aiming at the condition that the Sub-Trajectory Synthesis doesn’t work sometimes, we make some improvement on its prediction algorithm. As a result, we get higher prediction coverage. For the probabilistic algorithm, we make some adjustments enabling that it can be used while employing a grid representation of the map data space. In addition, we propose an improved destination prediction algorithm based on the probability statistic, which can achieve higher prediction accuracy.Thirdly, in order to evaluate the destination prediction algorithm more deeply, We divide the historical trajectories into five categories, according to the trajectory’s repetitions, starting point and end point. And we test the three destination prediction algorithms through Matlab simulation. Results show that the destination prediction algorithm based on the probability statistic that we propose has a good performance in most condition.Lastly, we develop a simple destination prediction android application, and we make some experiments on the application. Results show that the application can realize the basic function that we set.