路网中的空间路径搜索是地图服务中的一项基本功能,有别于传统的最短路径搜索,基于关键词的最优路径搜索(Keyword-aware Optimal Route Search,KORS)旨在查询返回一条覆盖所有用户指定的查询关键词、满足有限的行程预算(行程公里数),最终有最小花费(行程费用或时间)的路径。KORS是一种面向基于位置的服务(Location Based Service,LBS)的查询技术,能够为用户个性化的出行提供旅游行程的规划。由于KORS具有考察属性多样、拓展组合多变、查询条件受限等特点,实际求解该类问题的真实最优解是一类NP难题,故提出更为有效的查询处理方法颇具研究挑战。为减小处理KORS查询的复杂度,当前最新研究方法采用两类近似算法以及一类贪婪算法,在优化后的解空间下对问题进行近似最优求解。然而,这其中依然存在着不足之处,主要表现在:1.近似算法的执行效率在大图及多关键词查询中存在瓶颈;2.启发式算法无法求得能够满足所有查询约束条件的结果。因此本文针对上述两类问题展开研究,首先对符合KORS查询条件的所有可行结果进行分析,发现KORS的求解本质是采用Skyline路径序列化地构建部分关键顶点间的连接。由于现有算法各自采用了较为极端的路径拓展方式,为权衡查询处理的效率与精度,本文提出一种新的路径拓展构建方法:基于关键词的Skyline路径构建(Keyword-aware Skyline Route Generation,KSRG),以Skyline路径拓展代替旧有算法中极端的路径拓展方式,从而使路径能够在拓展过程中优先满足对查询关键词的覆盖。其次为了有效提升KSRG执行的可扩展性,本文进一步设计适用的完全多项式时间近似策略(Fully Polynomial拟Time Approximation Scheme,FPTAS),将原幂指复杂度级下的KSRG求解过程限定在多项式级。基于上述框架,提出近似算法以实现在大规模路网图及多关键词查询下更为高效通用的KORS查询处理过程。通过真实路网数据集下的实验测试,本文验证了提出方案的有效性:提出算法相对原有算法能够在有限精度损失下有效提升查询执行效率,同时能够在更大规模路网图下具有相对合理的查询开销。