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

摘要

针对网约车平台中用户希望车辆能够在指定时间内到达的问题,提出了时间依赖路网中限制到达时间的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算法提升一个数量级左右.