时间依赖路网中限制到达时间的k近邻查询  

k-Nearest neighbor query with limited arrival time in timedependent road networks

作　　者：安云哲 倪灿灿 李佳佳 张安珍 夏秀峰 AN Yunzhe;NI Cancan;LI Jiajia;ZHANG Anzhen;XIA Xiufeng(School of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学计算机学院,辽宁沈阳110136

出　　处：《河南科技学院学报（自然科学版）》2022年第5期58-68,共11页Journal of Henan Institute of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金青年基金(62102271)。

摘　　要：针对网约车平台中用户希望车辆能够在指定时间内到达的问题,提出了时间依赖路网中限制到达时间的k近邻(Time-dependent k-Nearest Neighbor Query with Limited Arrival Time,TD-Lk NN)查询,目标是返回能够在给定时间段内到达查询点,且车辆的空车时间最少的k个移动对象.首先提出了一种基于网格索引的TIGR(Time-aware Incremental Grid-based restrict)算法,用来获取移动对象的位置,以及限制查询范围.为进一步缩小查询范围以及减小候选集的大小,又提出了三种剪枝策略以及基于剪枝策略的TIGR_P(TIGR with Pruning Strategies)算法.基于对四组纽约真实地图数据进行的实验,验证了所提方法的正确性,以及三种剪枝策略的有效性.结果表明,在六组不同的实验参数下,使用不同的最快路径查询算法来支持TD-Lk NN查询时,TIGR_P算法的查询效率均可以比TIGR算法提升一个数量级左右.In response to the problem that users in the online car-hailing platform want the vehicle to arrive within a specified time,a Time-dependent k-Nearest Neighbor Query with Limited Arrival Time(TD-Lk NN)query in timedependent road network is proposed.The goal of the TD-Lk NN is to return k moving objects that can reach the query point within a given time period and have the least empty time for the vehicle.First,a TIGR(Time-aware Incremental Grid-based Restrict)algorithm based on grid index is proposed.The grid index is used to obtain the position of moving objects and limit the query range.To further narrow the query range and reduce the size of the candidate set,three pruning strategies and TIGR_P(TIGR with Pruning Strategies)algorithm based on these pruning strategies are proposed.Based on the experiments on four sets of real-world road network of New York,the correctness of the proposed method and the effectiveness of the three pruning strategies are verified.The results show that when using differentfastest path query algorithms to support TD-Lk NN queryunder six different sets of experimental parameters,the query efficiency of the TIGR_P algorithm can be improved by about an order of magnitude compared with the TIGR algorithm.

关 键 词：时间依赖路网 限制到达时间 空车时间 K近邻查询 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]