路网中基于最短路径的最近邻查询算法研究

摘要

已有的城市道路网中的最近邻查询算法只考虑离查询者当前位置最近的对象,不能保证相对于即将行驶的路径也是最近的.提出基于最短路径的最近邻查询,给定当前位置和目的地,返回的是到它们之间的最短路径有最小绕道距离的对象.提出基于三阶段的查询算法SFV(Search-filter-verify),利用双向Dijkstra算法得到最短路径的同时,保留有用的距离信息,再利用最小绕道距离的上下界关系过滤掉不可能成为结果的对象,最后精确计算剩余对象的最小绕道距离,得到结果.基于真实城市路网的实验结果表明,SFV与传统算法相比,有较高的性能和良好的扩展性.