随着无线通信技术的高速发展和智能移动终端的不断普及，基于位置的服务已经融入了人们生活的各个方面。用户的查询请求也越来越多样。例如在路网环境下，从指定的路段中查找最优的位置，要求这一位置到多种公共设施距离和最小;或者从用户感兴趣的对象集中查找到多种公共设施最大距离最小的对象点。上述两种情况都属于生活中常见的位置规划问题。又如，从用户当前位置到目标位置之间查找一条最优旅游路线，满足行程预算且人气值最高。这是外出的用户常常面临的路线规划问题。不同场景下的查询需求导致查询语义的表达复杂而多样，而上述位置相关的查询需求是现有技术没有考虑的。因此，需要有针对性地结合问题的应用场景和约束条件设计新的查询算法。
　　本文在对已有的位置规划和路径规划技术分析总结基础上，针对路网环境下三种不同类型的查询问题，即支持关键字的最优位置查询、支持关键字的兴趣点查询和约束条件下的最优路径规划，进行了深入研究，提出了相应的优化算法。本文贡献点主要包括以下几个方面:
　　(1)针对用户位置规划需求，提出了支持关键字匹配的最优位置查询方法，帮助用户从指定的路段中，查找到多种类型对象集距离和最小的位置。结合路段上存在的对象点，将路段划分为若干的子区间。根据子区间的端点位置到多种类型最近邻对象集的距离和是子区间内距离和下界这一性质，将在路段上查找最优位置的问题转为从路段上子区间的端点中查找最优位置，并基于边剪枝和关键字过滤策略，提出了高效的查询算法。
　　(2)进一步研究位置规划问题，提出了基于关键字匹配的兴趣点搜索技术。从用户感兴趣的目标对象集合中，查找到其他多种类型对象集最大距离最小的兴趣点。本文结合每类对象点将整个路网空间划分为若干个Voronoi单元，采用R-tree结构索引每类对象点对应的单元。基于Voronoi单元包含的关键字类型提出以距离下限为条件的无效兴趣点剪枝策略，改善了搜索效率。
　　(3)针对约束条件下的最优路径规划问题，提出了有效的解决方法，提高了路径规划性能。帮助用户从起始位置到目标位置之间规划一条最优路径，使得这条路径满足行程预算且获益总和最高。这一问题属于NP难问题。基于代价下限和获益上限两种剪枝策略，提出了适用较小规模路网的精确最优路径规划算法。针对较大规模的路网，提出了两种近似算法:一种是基于最短路径扩展的启发式算法;另一种基于完全多项式时间近似模式，主要根据子路径的支配关系，对局部劣势的子路径剪枝。
　　(4)设计并实现了最优路径规划系统
　　将本文所提出的近似路径规划算法推广到实际应用，设计并实现了最优路径规划系统，为用户规划满足行程预算且人气值最高的旅游路线。
　　总之，本文在研究路网环境下已有的位置规划和路径规划技术基础上，针对三种不同类型的支持位置服务的查询问题，提出了相应的解决方法，并通过大量实验验证了提出的方法的有效性和实用性。