随着经济的发展,最优路径应用领域渐广,如路网导航、游戏行业、物流行业等。其中,路网导航备受广大学者的关注。随着路网数据的日益庞大,常规寻路算法的寻路性能稍显不足,不能快速地解决在庞大的路网中寻找任意两点间路径的问题。当前使用较广的寻路算法为分层算法。分层的思想是将详细路网中权重较高的节点和路径段抽象成一个新的交通路网,通过合理地切换详细路网和新路网使得寻路算法获得较好的时空性能。虽然分层算法优化了在庞大的地图数据中寻路的性能,但是其寻路的质量较A*算法相比有所下降。针对这个问题,本文借鉴了分层的思想、小世界网络模型和路由理论等理论,给出了一种在保证路径质量的前提下提升寻路效率的寻路策略：基于小世界模型的启发式寻路算法(Heuristic path finding algorithm based on small world model,简称 HPAS算法)。第一,路网分区。借鉴于分层算法中分层的思想和小世界网络模型,通过对交通路网进行聚类分析,将聚类结果中的各个簇划分成不同区。第二,设置边界路由节点和内部路由节点,并将相邻路由节点之间的最优路径预存到缓存中。借鉴路由理论中的外部网关协议中路由器的功能,将各区中符合条件的节点设置成边界路由节点或内部路由节点,相邻路由节点之间的路径可通过预处理阶段求解出来并进行缓存。第三,寻路阶段。利用A*算法在各个分区中的边界路由节点和内部路由节点之间寻找最优路径。实验由路径计算模块、缓存模块、地图数据库存取模块和用户请求处理模块等组成。通过对美国东西部路网数据的测试表明,不同粒度的聚类在不同程度上提高了HPAS算法的寻路效率。但是较大粒度的聚类也会在一定程度上加大了所求解的路径长度与最短路径长度之间的偏差。仿真实验结果表明在不同的一级划分中平均路径长度与最优路径长度的偏差仅为0.03%。通过HPAS算法与A*算法、双向A*算法和基于层次结构的A*算法在寻路效率和路径质量上的实验数据的对比,可以看出改进型A*算法在地图规模较大的情况下表现出来较好的性能。