李佳佳，刘晓静，刘向宇，夏秀峰，朱 睿

(沈阳航空航天大学 计算机学院，沈阳 110136)(*通信作者电子邮箱lijiajia@sau.edu.cn)

0 引言

目前，关于静态路网K近邻查询研究已经相当成熟[1-3]，代表性算法有基于Voronoi图的VN3(Voronoi-based Network Nearest Neighbor)算法[4]；利用欧氏距离与路网距离结合的IER(Incremental Euclidean Restriction)、INE(Incremental Network Expansion)[5]算法；通过范围扩展的“岛”算法[6]等，但静态路网以行驶距离作为边的权值，在时间依赖路网中，边的权值为行驶时间。如图1所示，汽车1寻找最快到达的加油站，在图1(a)发起查询时刻为早上8:00，加油站1为返回结果，如果在早上6:00发起查询如图1(b)所示，加油站2则是离汽车1最近的加油站。由于发起查询时刻不同，返回的结果集不同，因此静态路网中求解K近邻查询的算法并不适用于时间依赖路网中，需要探索新的方法。

关于时间依赖路网K近邻查询存在一定研究[7-9]但相关研究还很不完善。Demiryurek等[10]提出TE(Time-Expanded)和TD-NE(Time-DependentKnearest neighbor with Network Expansion)算法，Cruz等[11]通过启发函数和剪枝技术提出TD-NE-A*(Time Dependent Network Expansion with A*search)算法。TE算法将边的权值离散化，无法保证权值在所有时刻取得实际值，因此造成误差并不断积累，最终可能导致结果集的错误；TD-NE算法查询中盲目扩展所有节点的邻接点，计算代价大；TD-NE-A*算法剪枝策略的设定，会漏掉查找的兴趣点，或者使到达兴趣点的代价增大，并且由于时间依赖路网中权值在高峰期和低峰期相差较大，TD-NE-A*在高峰期用全天最小值作启发值与实际值相差较大，启发效果差，因此Komai等[12]提出TD-FTT(Time Dependent Fast Travel Time)算法，该算法将总体时间分为n个时段。预处理阶段，取每个时段边的最小值构成静态路网Gmin，在Gmin中计算所有节点的C近邻。……