基于ArcGIS网络模型的最优路径算法分析与实现.pdf

基于ArcGIS网络模型的最优路径算法分析与实现

刘建川，杨军，甘泉

（四川省基础地理信息中心，成都610041）

摘要:根据ArcGIS网络模型和城市道路交通网络的特点，设计了能够描述城市交通禁则（禁止直行、禁止左转、
禁止调头等）的道路交通网络模型。利用该模型对传统的Dijkstra算法进行了改进，提出了能解决城市交通禁则
问题的最优路径算法。通过城市路网对比试验，结果表明，所提出的算法能够根据城市交通禁则规划出实用的最
优路径。

关键词：Dijkstra算法；ArcGIS；最优路径；网络模型

AlgorithmicAnalysisandImplementationOfOptimalRoute
BasedOnArcGISNetworkModel

LIUJianchuan,YANGJun,GANQuan

(SichuanGeomaticsCenter,Chengdu610041,China)

Abstract:Consideringthecharacteristicsofurbantrafficnetwork,thenewtrafficnetworkmodelwas
designedtodescribeurbantrafficconfinerule(suchasprohibitingrunningstraightly,prohibiting
turningleft,prohibitingturningaroundetc.).Usingthenewmodel,thetraditionalDijkstraalgorithm
wasimprovedandthealgorithmofoptimalrouteguidancewasdesignedontheconditionsofurban
trafficconfinerule.Contrastiveexperimentalresultsbasedonanurbanroadnetworkshowthatthis
algorithmcouldmakeouteffectiverouteaccordingtourbantrafficconfinerule.
Keywords:Dijkstraalgorithm,ArcGIS,optimalroute,networkmodel

在复杂的城市交通网络中，为缓解紧张的交通状况，设置了许多交通禁则，如禁止左转、禁止直行、
单行道等，加之众多城市立交桥、下穿隧道等交通设施，因此，该网络用简单的网络模型是无法描述的，
须建立带交通约束的网络模型。这种模型加大了对最优路径搜索的难度，由于交通禁则的限制，往往需要
对边进行重复搜索。在一般的道路模型中，包含重复边的路径不是最优的，但在城市交通禁则下，只有在
必要的情况下包含重复边（但不是同一行驶方向），才能正确引导出行者到达目的地。基于此，本文在分
析带交通禁则的城市交通模型的基础上，对传统的Dijkstra算法进行改进，设计了一种用于在城市交通禁
则下的最优路径算法，并与传统的算法相比较，验证了其有效性。

作者简介：刘建川，男，硕士，主要从事地理信息系统开发、3S技术及应用研究工作，E-mail：[e-mail]。

1
1在交通禁则下的城市交通模型

[5]
包含交通禁则的道路网络模型使用受限路网模型描述,用有向带权图Rw(N,R,T)表示。其中，N

={c1,c2,⋯,cn}为道路节点集合；R={r1,r2,⋯,rm}为路段集合；ri={<ci1,ci2>,wi，di},ci1、ci2分别是起点

和终点,wi>0为路段权值,di为单行标记;T={tc1,tc2,⋯,tcn}为基于节点的交通约束集合,tck={<rk1,

rk2>,……,<rkw-1,rkw>}，ck是其中所有路段的公共端点，路段二元有序对〈rk1,rk2〉表示ck点存在一个从

rk1到rk2的交通约束。
在实际的最优路径分析中，用户所选择的起点和终点距离道路网络模型有一定的距离，为此，首先应
根据距离最短的原则将用户点投影到路网中，然后利用投影点和用户点构造临时节点和路段并添加到路网
中，最后，在根据用户点的位置和车辆的行驶方向构造道路约束关系。如图1所示，a、b为路网中的两个
节点，在<a,b>线上是禁止掉头，s点为起点，m为s在路网中的投影点，将路段<s,m>和s,m节点分别加入到
N和R中，则
N’=N∪{s,m}，

R’=R∪{<a,m>,<s,m>,<m,b>}.

这样就建立起了s与路网的临时拓扑关系。由于<a,b>线上是禁止掉头的,按照交通规则，由s到m时只能
向a方向行驶，在b方向存在约束{<s,m>,<m,b>}，将此约束加入到T中则构成了新的交通约束模型