大规模路网图下关键词覆盖最优路径查询优化

来源：软件学报杂志2020年第8期北京时间：

作者：郝晋瑶，牛保宁，康家兴

单位：郝晋瑶，太原理工大学 信息与计算机学院, 山西 晋中 03060011,牛保宁，太原理工大学 信息与计算机学院, 山西 晋中 03060002,康家兴，太原理工大学 信息与计算机学院, 山西 晋中 03060003

摘要：游客倾向于采用个性化的旅游路线，规划这样的路线需要综合考量路径长度、路径开销和路径覆盖的兴趣点.关键词覆盖最优路径查询（KOR）就是用于规划这样的路线的一类查询，其处理过程通常包括预处理和路径拓展.由于路网图规模的不断扩大，现有算法预处理所需内存开销急剧上升，由于内存不足，导致较大规模的路网不能处理；路径拓展搜索空间快速膨胀，应用场景可扩展性与查询实时性难以保证.针对这些问题，提出一种大规模路网图下关键词覆盖最优路径查询算法KORL.KORL在预处理阶段将路网划分为若干子图，仅保存子图内路径和子图之间路径的信息，以减小预处理所需内存.在路径拓展阶段，综合运用最小代价剪枝、近似支配剪枝、全局优先拓展和关键词顶点拓展等策略对现有算法进行优化，以高效地搜索近似最优解.采用美国各地区的路网图，在16G内存环境下进行实验，突破了现有算法只能处理顶点数不超过25K路网图的限制.实验结果表明，KORL算法具有良好的可扩展性.

关键词：个性化旅游路线;关键词覆盖最优路径;大规模路网图;路网图划分;最小代价剪枝

基金资助：国家自然科学基金（61572345）