【摘要】最短路径分析是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 作为对应因素的固定影响值保存其中。 3.2 根据交通信息实时计算出当前的道路权值
为了体现各个因素的影响的实时性,对各个因素进行分级[6],各个级别对道路权值的贡献度是不一样的,比如对道路的拥挤度我们可以分为表4级别并规定其各个级别的贡献率:
表4 交通拥挤因素的拥挤度划分以及各个拥挤度的贡献率
拥挤度
畅通
正常
轻微拥挤
拥挤
严重拥挤
贡献率
0
0.25
0.50
0.75
1
设贡献率为参数m,贡献值为n,固定影响值为d,则贡献值为:
一种基于交通信息更新的变权值的最快路径算法
根据当前的交通信息,计算出各因素的贡献值,再加上道路长度对时间的影响就是此时这段道路的权值:
Dijkstra(ni为因素i的贡献值,L0为道路长度,V0为路段速度)
计算出每条道路的权值以后,就可以依据Dijkstra算法,规划出当前最优路径,当交通信息再度发生变化时就触发重新计算各个道路的贡献值(其中只有贡献率是可能变化的,固定权值是不会发生变化的),重新规划当前最优的路径。当然,上述算法还可以做些优化,比如对某一导航设备,离该设备很远的交通信息的更新对设备导航几乎是没有影响的,设备也就无需进行路径更新;路径规划过程中,与规划相关的道路毕竟是离现在的源地址和目的地址较近的道路,所以没有必要开始就更新所有道路的当前权值。
4 实际应用
在基于移动GIS的旅游导航设备的开发中,用超图公司的eSuperMap2008V5·3·0作为地图操作组件。eSupermap是允许对地图进行编辑的、增加属性的,我们给每条道路增加六个非系统属性来对应存放六个因素的影响值,并且缓存当前的交通信息状况。同时eSupermap允许继承它的路径分析类CSePathAnalyst,重载它的函数GetDistance。这样在用函数CreateMatrix生成邻接举证的时候我们就把这六个影响因素考虑进去,生成算法对应的邻接矩阵,进行最快路径分分析,一旦有交通信息的更新,就根据当前的交通状况生成新的邻接矩阵,得出当前的最快路径。
为了更为直观的展示算法,可以用图2的道路交通网为一个实例进行验证。
Dijkstra
图2 一个简单的道路交通网
假定现在汽车行驶到了A点,目的地是B,道路AC、AB、CB的速度限制、转向规则等都一样,并且假设路段长度AB为10,AC为7,CB为8,限速为5,交通拥挤的影响值为3,事故影响值为3。在没有任何交通拥堵和交通事故即交通拥挤和交通事故的贡献率为0的情况下,走AB路段是最快的,因为AC+CB>AB。假设汽车行驶到A点时收到交通信息更新消息,路段AB中发生严重的交通事故,在以往不考虑影响因素的情况下,肯定还是走AB路段的,但是本算法考虑这些并且重新生成邻接矩阵,生成当前的最快路径,在此时,对于AB路段,显然交通拥挤的贡献率为1,交通事故的贡献率也为1,此时AB的权值就为(1*3+1*3+10/5=8),而走AC的权值是(7/5=1.4)。CB段的权值是(8/5=1.6)。很明显此时走AC、CB路段比走AB路段更快。
5 结束语
传统的导航路径规划中,影响道路最快路径规划的外在因素是没有在考虑其中的,这样规划出来的道路不一定是最优的,或者说可能是错误的。影响道路最快路径规划的外在因素是与时间有关的,也可能瞬时变化的,为了规划出当前最优的路径,就必须把这些因素考虑在内,当影响因素发生变化时候,重新进行路径的规划。本文就实时规划的权值做了研究,将影响因素综合起来考虑,实时计算道路的当前权值,规划出当前的最快路径,当然这其中很多的参数是可能发生变化的,比如相对权重是可能发生变化的,或者这个参数不是最优的,这还需要我们继续做深入的研究。
参考文献
[1] 胡腾波,叶建栲。 GIS时变权值玩过最短路径算法研究[J]. 计算机与现代化,2008,2:22-24.
[2] 胡钱钱,李莉。导航电子地图的更新机制与技术方法[J].地理信息世界,2008,1:77-82.
[3] 温惠英,沈毅贤。基于层次分析法的物流配送车辆导航路径规划求权方法[J]. 公路交通科技,2008,25(8):114-118.
[4] 温惠英,沈毅贤。适于物流配送车辆导航路径规划的路网阻抗确定方法研究[J]. 交通科技,2008,226:94-97.
[5] 瞿嵘,翁敏,杜清远。 最简单路径寻找方法研究。 测绘科学,2008,33(6):130-132.
[6] 靳引利,王军。高速公路网中的Dijkstra最短路径优化算法[J]. 现代电子技术,2008,21:188-191 |