Travel Time Estimation Of A Long Path Using Trajectory Data

Navigation system is important for solving urban traffic congestion and alleviating traffic pressure.The estimation of path travel time based on traffic condition is the basis of navigation system.With the accumulation of vehicle trajectory data,It becomes possible to estimate the travel time of any path in dynamic network,that is,given a source and a destination for a given time,to predict the travel time of different paths so that the fastest one can be found.However,the shortest path is not necessarily with the largest cumulative probability distribution,when traveling with a deadline,for example,arriving at the airport or an important meeting on time,then getting the path with the largest cumulative probability can play a big role.In order to find the path with the largest cumulative probability in the dynamic network,it is necessary to estimate the probability of the travel time,rather than only a single value.In the study of the existing paradigm,the researchers divided the path to the sequence of road segments,and using the trajectory data collected by the sensor to estimate the travel time of road segments,then combining the estimated results to compute the full path.However,this way ignores the part of the time such as waiting time of traffic lights and the turning time,and leads to an inaccurate result especially when the estimated path is a long path.In this paper,we proposes a path estimation scheme based on sub-paths,which is different from the scheme based on road segments.To improve the efficiency of the estimate,we build a suffix index tree by using history data to mining the sub-path sequence of an query path,and the travel time of the sub-trajectories are stored in each node in suffix tree,in this way we can also compute the travel time of the query path efficiently.For the sub-paths that data is sparse,historical data is used to provide trajectories’ travel time.To improve the accuracy of the estimate,we use linear interpolation algorithm and spatial-temporal algorithm to estimate the travel time probability distribution of the path,the experiments verify the accuracy and efficiency of the algorithm.