基于图论的动态导航系统最短路径算法研究

近几年来,随着国民经济的发展,城市中机动车辆渐渐增多,交通需求在不断增加,公路交通流量也越来越大,由此导致了交通拥堵的频繁发生,城市交通正面临着越来越大的压力。在这种形势下,基于静态地图的自主导航虽然可为驾驶员规划一条“最短”路径,但却无法避开前方道路可能发生的交通拥挤。而动态导航则不同,系统获知出发点与目的地之间的交通状况,经过规划得到一条满足用户需求的合理路径。这种导航方式不仅可以有效的避开拥堵,节省出行成本,而且对整个路网有着良性影响。 本文研究了车载动态导航系统最优路径规划的系统方法,包括:交通路网的矢量地图表达,图论中的最短路径算法,动态时间权重的最优路径规划等。 首先,简述了有关地理信息系统的一些基本概念,包括地理信息系统概念、地理信息系统数据模型、地理信息系统数据的组织和管理,针对城市交通道路网的特点,着重分析研究了城市交通道路网的矢量地图表达、网络中的交通限制信息的表示等。 其次,本文介绍了图论的相关理论,研究了图的邻接矩阵、邻接表的表达方式,对图的搜索方式进行了分析,基于边带的通用图搜索,基于FIFO队列的广度优先搜索,基于栈的深度优先搜索。同时分析了Dijkstra算法求单源点最短路径问题,即图的最短路径树,以及用在交通网络中的欧几米得试探法。 最后,本文研究了基于交通路网的A*算法,该算法能够有效降低Dijkstra算法的时间复杂性,提高系统的运行效率。提出了从起点到终点所用时间最短的路径的方法,即所谓的时间最短路径算法。确定了算法对路段动态阻抗的获得方法。提出了动态路段阻抗的数据结构即各路段的阻抗序列数组以及时段数组。综合考虑了动态导航系统路径规划子系统的解决方案。