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)

摘要： 针对时间依赖路网中的K近邻（KNN）查询TD-FTT算法查询点发起时间与到达时间在同一时段的限制和预处理阶段计算时间代价大的问题，提出基于动态选择启发值改进的TD-FTT （ITD-FTT）算法。首先，在预处理阶段，根据各时段各边时间函数的最小值构建最小路网G_min；然后，在路网G_min中利用网络泰森图（NVD）并行计算节点最近邻来减少预处理阶段的计算时间；最后，在查找阶段通过计算节点到达时间所在时段，动态选择启发值来解除时间段的限制。实验结果显示，在预处理阶段ITD-FTT算法比TD-FTT算法计算时间减少了70.12%；在查询阶段ITD-FTT比TD-INE算法和TD-A算法在遍历节点个数上分别减少了46.52%和16.63%，响应时间比TD-INE算法和TD-A算法分别降低47.46%和18.24%。实验结果表明，ITD-FTT算法减少了查询扩展的节点数，降低了查找K近邻的时间，提高了查找效率。

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