现下于人们的日常生活中,基于地理位置信息的服务(LBS,Location-Based Services)是一种经常性被使用的应用服务,绝大多数以LBS为核心的实际应用都依赖于路径规划技术,以提供人们相关交通性质的应用服务。随着移动互联网以及地理信息定位技术的快速发展,人们能够愈发容易地通过智能终端设备使用集成了路径规划技术的应用程序,这些应用程序可以为其用户便捷地规划优质的出行路径。基于以上事实,路径规划算法在提高人们出行的质量与效率上起了很重要的作用。在路径规划研究领域中,几乎所有的研究工作所面临的最大挑战就是:如同著名的旅行商问题(Traveling Salesman Problem)一样,其核心问题都是NP完全问题。换而言之,当空间路网中的节点数目激增时,各种路径规划算法的算法效率就会让人难以接受了,即无法在多项式时间内给出精确解。除此之外,现存的路径规划算法很少考虑到对POI兴趣点的可能限制,比如根据用户的意图活动来限制所规划出的路径需涵盖的兴趣点活动类型。本文主要研究基于活动意图的多准则路径规划问题,其目的是为用户规划一条路径,该路径能够在给定的距离或时间阈值内最大化用户满意度。本课题不同于其他研究工作之处如下所示:(1)不同于传统的路径规划,本文引入了用户满意度这个概念。一个POI兴趣点的用户满意度可以通过计算历史用户对其评分的平均值获得,并在一定程度上反应了该兴趣点一般意义上的评价等级。(2)本文不仅提出了基础的精确算法,同时也提出了空间梗概近似算法(Spatial Sketch-based Trip Planning Algorithm)作为核心技术算法,通过该算法可以以损失一些精度的代价大幅度提高算法运行效率。(3)另外,本文设计了一些诸如查询优化(Query Optimization)以及缓存管理(Buffer Management)等在展示系统中被实际应用的优化技术,以期加速用户查询处理过程。