面对日益复杂的路网,尤其是超大规模路网,车辆导航设备的路径规划功能的效率需要进一步提升。此外,对人们选择路径习惯的深入研究发现,路径增加可接受长度时,人们更倾向于选择转弯次数较少的舒适路径。因此路径规划需要在路径长度和路径的转弯次数之间折中。基于以上分析,本论文研究的目的是1)提升路径规划算法的效率,2)降低路径中的转弯次数,平衡路径的长度和路径转弯次数。路链是路网中的一条自然道路,基于路链构建路网拓扑可以有效地降低路网拓扑中的元素数量,因此基于路链的路网拓扑进行路径规划效率更高。此外,基于路链的路网拓扑规划出的路径是由路链或者路链的一部分构成,因此路径的转弯次数少。基于以上分析,本文研究的主要内容包括1)基于路链构建路网拓扑,2)基于路链的路网拓扑设计路径规划算法。论文以静态路网为应用场景完成了以下两部分的研究:第一、提出了一种基于路链构建路网拓扑的算法和一种基于路链的路网拓扑的存储结构;第二、基于路链的路径规划算法,首先提出了一种基于路链的启发式路径规划算法,该路径规划算法效率高于传统A*算法,同时能够降低转弯次数且路径长度的增加在合理范围内。然后提出了两种基于路链的广度优先路径规划算法,两种算法都能够确保路径的转弯次数最少。其中一种算法为基于路链的双向广度优先路径规划算法,该算法可以高效地寻找到转弯次数最少的路径。另一算法为基于转弯次数最优的最短路径规划算法,它可以在转弯次数最少的路径中寻找到距离最短的一条。