一种基于交通信息更新变权值最快路径算法

　一种基于交通信息更新的变权值的最快路径算法

　【摘要】最短路径分析是 GIS 网络分析的基础。在传统的最短路径算法中，Dijkstra 算法是很经典的算法。由于在最短路径规划中，影响规划的外在因素较多，而且这些因素或者是随时间变化的，或者是随机发生的，为了得到当前最优的规划路径，我们提出了基于交通信息更新的路径规划算法，当交通信息更新时，根据交通信息实时生成 Dijkstra 算法邻接矩阵的权值，规划当前的最优路径。论文关键词：交通信息更新,Dijkstra,邻接矩阵,最短路径 随着计算机技术以及地理信息科学技术的发展，GIS（Geography Information System）因其强大的功能和方便性而得到日益广泛的应用，在电子导航、交通旅游、城市规划以及电力、通讯等各种应用布局中发挥了重要的作用。在 GIS 的应用中，导航路径的规划即最短路径问题是一个最基本最关键的问题。人们做了很多工作，提出了相当多的最短路径算法，其中 Dijkstra 算法是一个相当经典的算法。在 Dijkstra算法中，算法依据一个权值矩阵对这些权值做相应的计算得出最短路径。但是我们知道 GIS 网络是一种时变网络，网络的拓扑结构、各边的权值都可能随着时间的变化而变化的[1]。在现有的已经应用的导航设备中，导航路径规划使用的地图是设备上已经存在的地图[2]，规划时不考虑外界的影响因素，或者即使有的设备在道路的属性中新增加了几个影响规划的属性值，但是这些属性所在的地图是没有及时更新的，这些属性值当然也是不会变化。影响道路规划的因素极可能是突

　然变化的，如果在规划的时候不实时考虑外在的因素影响，显然做出的规划不一定是最好最合理的，由此在规划的过程中实时考虑外在因素的影响是必须的。本文在研究了影响网络拓扑结构、各边权值的因素的前提下，提出了一种基于交通信息更新的 Dijkstra 最快路径规划算法。

　2 影响导航路径规划的外在因素 影响导航路径规划的外在因素有很多，我们必须认真地对这些影响因素逐一进行分析，以确保高效实现最优路径规划。而每个影响因素对路径规划的影响程度也不同，为此要对这些影响因子进行度的量化。

　（1）交通拥挤度[3][4]。交通拥挤度是路径规划的最大影响因素，我们都有这样的感受，特别是在城市里面上下班的高峰期，某些路口的交通拥挤程度是很大的，如果拥挤度足够大，我们几乎可以在导航路径的规划中不选择这条路，也就是认为这个路口不同，最大限度的避开。

　（2）交叉口延误[3][4]。在实际出行中，拥堵和延误常常发生在交叉口[5]，比如等待红绿灯，据研究行驶在城市路网的车辆，在交叉口所耗费的时间大约占整个出行时间的 20%--40%。

　（3）道路等级[3][4]。在城市道路网中，不同级别道路的设计车速是存在差异的，这当然也影响着路径的选择。在相同的交通状态下，选择级别较高的道路应该是最好最节省时间的。

　（4）交通事件[[3][4]。交通事件主要指道路施工维修、临时交通管制、车辆故障、路面损坏等有可能发展成为交通拥挤和交通事故的事件。

　道路施工、车辆故障、路面状况的改变（损坏、积水、积雪）会占用车道，临时交通管制会改变道路通行方式。这些交通事件的发生将会阻碍车辆通行的速度，降低道路的通行能力，增加出行延误时间。在计算路段和节点权值时应该考虑这些影响因素。

　（5）交通组织[3][4]。交通组织主要是指交叉口的转向限制（禁左、禁右）以及路段对车辆的限制（车辆类型、最大速度、路障等等），而现实中某些交通限制往往是与时间相关的，某些时间段可以通行，某些时间段却又禁止通信等。

　（6）气象环境[3][4]。雾、雨、雪、风和雷等气象环境状况，都会严重影响行车安全，特别是行驶在高速公路上的车辆。因此，有必要的在路段和节点的权值上加入天气因素，以体现气象环境对路径选择的权值确定和影响。

　3 基于交通信息更新的最快路径规划算法 分析上述因素我们知道，这些因素几乎都是随着交通状况或者天气状况或者时间变化的，最快路径的规划，都要考虑到这些因素的影响，而这些影响统统都反映在 Dijkstra 算法的邻接矩阵的权值当中，所以如何计算权值，权衡各个因素的影响比重就成了问题的关键。下面给出我们的权值算法主要分两步：

　（1）计算出各因素的固定影响值； （2）根据交通状况实时计算路段此时的权值。

　3.1 计算各个因素的固定权值 下图给出了道路权值指标体系图[3][4]，直观反应了影响道路权值的因素

　 图 1 道路权值指标体系图 确定判定量化的标度，将影响因素两两比较，根据表 1 的原则，构建判定矩阵表 2。

　表 1 判定矩阵标度含义 标度 含义 1 两个因素同等重要 2 两个因素相比，一个比另一个较重要 3 两个因素相比，一个比另一个重要 4 两个因素相比，一个比另一个很重要 5 两个因素相比，一个比另一个非常重要 倒数 因素 Bj 与 Bi 比较时，标度为 aji=1/aij 表 2 判定矩阵 B1 B2

　B3 B4 B5 B6 B1 1 1 4 3 3 5 B2 1 1 4 3 3 5 B3 1/4 1/4 1

　1/2 2 5 B4 1/3 1/3 2 1 2 5 B5 1/3 1/3 1/2 1/2 1 5 B6 1/5 1/5 1/5 1/5

　1/5 1 用 MATLAB 计算出判定矩阵的特征值，最大特征值为 6.3947，最大特征值相应位置的值就是对应因素的相对权重数据如下表：

　表 3 各因素相对权值 w1 w2 w3 w4 w5 w6 0.6363 0.6363 0.2292 0.3055 0.1971 0.0743 若影响道路权值确定的影响因素 B1，B2，……B6 的无量纲化的结果为b1，b2，……b6,则为道路增加六个属性值，将 di=wi*bi 作为对应因素的固定影响值保存其中。