关键词: 时间依赖路网, K近邻查询, TD-FTT算法, 预处理, 网络泰森图

Abstract: The existed TD-FTT (Time Dependent Fast Travel Time) algorithm, for answering K Nearest Neighbors (KNN) query in time dependent road network, requires that the issued time and the arrival time of a query must be in the same time interval, which costs a long time in the preprocessing phase. To solve these problems, an Improved TD-FTT (ITD-FTT) algorithm based on dynamically selecting heuristic values was proposed. Firstly, in the preprocessing phase, the road network G_min with the minimum cost for each time interval was created by using time functions of edges. Secondly, a parallel method of utilizing Network Voronoi Diagram (NVD) in road network G_min was used to compute the nearest neighbors of nodes to reduce the time cost. Finally, in the query phase, the heuristic value was dynamically selected to get rid of the time interval limitation by calculating the time interval of the current arrival time of nodes. The experimental results show that in the preprocessing phase, the time cost of ITD-FTT is reduced by 70.12% compared with TD-FTT. In the query phase, the number of traversal nodes of ITD-FTT is 46.52% and 16.63% lower than TD-INE (Time Dependent Incremental Network Expansion) and TD-A (Time Dependent A star) algorithm respectively, and the response time of ITD-FTT is 47.76% and 18.24% lower than TD-INE and TD-A. The experimental results indicate that the ITD-FTT algorithm reduces the number of nodes by query expansion, decreases the time of searching the KNN results and improves the query efficiency.

Key words: time dependent road network, K Nearest Neighbors (KNN) query, Time Dependent Fast Travel Time (TD-FTT) algorithm, preprocessing, Network Voronoi Diagram (NVD)