车载导航系统的最优路径规划算法研究

城市的发展和扩建带动了智能交通的发展,现如今城市交通越来越复杂多变,车辆数目增加、道路维修、交通阻塞等问题给城市交通系统带来了极大的负担,仅仅依靠城市交通中心的控制不足以解决日益严重的交通问题。车载导航系统可以有效的缓解城市交通拥挤、优化城市交通流、提高运输效率、减少环境污染等。路径规划是车载导航系统的重要功能之一,有效的路径规划可以缓解城市交通拥挤、优化城市交通流、提高运输效率、减少环境污染等。 路径规划算法是获得最优路径的关键因素。导航系统中的最优路径是依据导航仪内部存储的矢量电子拓扑图,结合驾驶员出行的起始点和终止点利用路径规划算法得到的,算法的准确性和有效性直接影响路径规划的结果,体现了路径规划算法研究的重要性。 (1)首先介绍了导航系统电子地图制作过程的基础,利用MapInfo软件建立了西安市矢量电子地图的拓扑结构并实现了地理编码。 (2)由于路径规划中广泛使用的Dijkstra算法搜索节点范围大导致该算法具有较高的复杂度,基于此提出了基于桶排序的矩形区域限制搜索的改进Dijkstra算法。首先利用桶排序将数据的存储结构转换成按照边的权值大小排列的临接表结构,然后采用矩形区域限制搜索方法,以达到减少遍历节点数量的目的。 (3)针对路径规划的影响因素,选择常用的距离、道路等级以及交叉口等待时间作为路径规划要素,提出了一种加权的路阻函数模型。利用模糊算法经过模糊规则的选择、论域的设置、模糊表的编辑并通过实验确定路阻函数模型在实时动态交通中的加权值。 (4)本文的实验是根据MapInfo中建立的西安市矢量拓扑图,在MATLAB2007平台上编程实现了本文算法,并利用电子地图的拓扑数据进行了算法的验证。实验验证了改进Dijkstra算法和加权路阻函数模型的可行性和有效性,提高了路径规划算法的效率。