随着移动互联网的快速发展,导航系统被广泛地应用于日常生活之中。现有的导航应用程序大部分提供的是逐步导航技术,其主要来自基础道路的网络拓扑信息,因此逐步导航被认为是将物理世界中的度量简化为简单口语描述的工具（例如距离、时间、转向等信息）。这种导航描述方式忽略了人们对地理空间的固有认知,对于那些了解城市布局的司机来说,往往是冗长和复杂的。这样不仅使得驾驶员对导航描述更为模糊,还占用了大量的终端资源。而互联网应用拥有大量的用户导航历史数据,并且这些数据包含了大量的地理信息。所以本论文希望利用用户的历史轨迹数据,研究一种全新的基于用户历史轨迹的个性化导航路径描述算法,生成更为简洁、直接且准确的定制化路线描述;这种描述方式使驾驶员更容易理解路线,并且可以使用较少的资源（例如,屏幕空间）以更直观的方式利用高级信息来解释整个路线。基于以上问题,本论文提出了一个名为PerRD（Personalized Route Description）的基于用户历史轨迹的个性化导航路径描述算法,其目标是利用大量用户之前生成的历史轨迹数据,提取用户在道路网络中经常访问的路线,通过提取的信息得出对每一个用户更具个性化并且更容易理解的路线描述。本文将这项任务分解成以下几个问题以分步完成,首先是最大程度地挖掘熟悉度,同时在保证最小化路线分段数量的前提下,找到最优的路径分段;其次找到合适的地理类型及地标去生成一个合适的语句,去描述每一个路线分段。为了进行实证研究,本论文的解决方案被应用于三个轨迹数据集以及用户的真实体验去评估PerRD的性能及有效性。在本论文的研究中,提出了一个名为PerRD的基于用户历史轨迹的个性化导航路径描述算法,其目的是通过利用历史轨迹数据为城市通勤者提供更高质量的个性化路线描述。本论文将路线描述问题形式化,然后提出了有效的算法来最优化地解决它们。本论文提出了一种寻找最合适的位置名词进而描述路线分段的方法。据调研所知,本论文是最早使用个性化位置名词描述路线的文章。本论文在实际数据集的基础上进行了广泛的实验,并实现了具体的Web系统以评估PerRD算法的性能和有效性;并且如结果所示,在适当数量的路线下,PerRD可以减少路线描述语句的数量,同时仍可为用户提供较好的导航服务。