The Research On Technologies Of Route Planning Based On GPS Historical Trajectory

With the popularity of GPS enabled equipment,route planning based on trajectory searching gradually become a hot research topic.Given a set of ordered query points,in order to explore the experience in the route selection of the previous users,some traditional algorithms aim to search trajectories which are spatially close to the query points.However,these trajectories have two major problems.First,these trajectories may be only close to partial query points,while far from others;second,these trajectories may pass through other locations beyond the query point set.If users travel along these trajectories,they may not find some query locations due to the Problem Ⅰ,and have to bear the extra cost due to the Problem Ⅱ.In this thesis,we propose a new model called Route Planning for Locations Based on Trajectory Segment(RPBTS).It can solve two main problems of traditional trajectory searching algorithms.Given a set of query points,we first convert these query points to the road segments around them.Next,we retrieve the combinations of trajectory segments which intersect at these road,and use these trajectory segments to assemble a route.In this way,the assembled route is close to each query point.In addition,this thesis proposes a variance-based method to determine whether the trajectory fragment has abnormal behavior between two consecutive query points.By discarding these abnormal trajectory fragments,we can ensure the returned route didn’t go to the other location between any two consecutive query points.Then,we propose the basic solution of RPBTS,and introduce the idea of greedy algorithm.In addition,three optimization methods are utilized to further improve the efficiency of the algorithm.First,optimization method based on the grid index,for each query point,this method can efficiently locate the road segments nearby.Secondly,optimization method based on regional landmark,the method can convert query points to the popular road segments around them.Third,optimization method based on random selection,this method can effectively reduce the overhead of multi-scheme selection.These optimization methods reduce the complexity of the RPBTS algorithm reasonably,and make the planning process more in line with people’s common sense.Finally,we design a reasonable experiment based on the T-drive trajectory data set provided by Microsoft Research and the map data in Beijing provided by the Chinese Academy of Sciences software to verify the effectiveness and efficiency of the RPBTS algorithm.The experimental results demonstrates the RPBTS algorithm can effectively avoid the two major problems in traditional algorithms.Moreover,our algorithm has achieved high efficiency.When the query points is 4,the average operation time of RPBTS is about 156 ms,it can fully meet the users’ requirements of response speed.