文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 天文/地理 > 基于GIS的城市道路网最短路径分析
侵权投诉

基于GIS的城市道路网最短路径分析

基于现实城市道路网络的最短路径分析,解决方案

求得的解大于实际最短路经长,所以在每次搜索最短路径顶点时,将当前结点的邻接点按照矢量夹角大于零和小于零分为两组,分

乎

别在两组中选取矢量夹角绝对值的最小值对应的结点。算法采用

双向搜索,从起点S开始进行正向搜索,同时从终点T进行逆向

搜索。两个方向每一步都要搜索与指定直线段左右两侧各一条夹

角最小的边,直到二者会合或直到目标点,最后取两个方向搜索

到的距离最短的路径为所求解。

П Ё Ё

2.2 算法具体步骤

假设需要求解最短路径的两个结点分别为S点和T点,其中 乊 Ё 起点为S、终点为T。定义ds(i)表示源结点S6到结点i的加权距离 ;第六步:搜索结束后,若会合于一点,则取会合点处的标记

值之和ds(An)+ dt(Bn)作为可能最短路径长度;若没有会合,则取终点T(正向搜索)或起点S(逆向搜索)处的标记值ds(T)、dt(S)作为可能最短路径长度。取其中最小值min{ ds(An)+ dt(Bn), ds(T), dt(S)}即为所求最短路径长度。

如果所求最短路径中包含会合点,则最短路径由会合点开始沿与之相关联的两条边依次寻找求解的最短路径的标记结点,加入路径队列,直至S、T。若没有会合点,则从起点S或终点T开始,在二叉树中顺次寻找所求最短路径的相关结点,直至达到T或S,便得到最短路径序列。搜索流程如图1。

7 dt(j)表示目标点 T到结点j的加权距离; ps(m)、pt(m)表示结点m 的状态,分为未标记结点(0)和标记结点(1)两种,其中ps表 偸

示正向搜索(从S出发)过程中的状态,pt表示逆向搜索(从T

出发)过程中的状态。

第一步:初始化:对所有结点6 7 Ё i,若i=S,则6 ds(i)=0, ps(i)=17 Н;GV L ⑤ 若6i=T, 则L dt(i)=0, pt(i)=1GW M ;否则ds(i)7 →∞M, dt(i) →∞,ps(i)=0, SV P

SW P pt(i)=0。并定义一个数变量P Ёk作为循环变量,初始化为SVk=0。

6 Ё SW第二步:判断 7 Ё S与T之间是否邻

接,若邻接,则连 接两端点的边即为

所求最短路径。否Н

则,转第三步。

第三步:令S、

T分别为两棵二叉

树的根节点,分别

从S、T出发,在

直线段ST、TS左 右两侧各寻找一条与 ST

、 TS 夹角最小的边,把搜索到

S的边加入对应的二

叉树。设从S点出

基于GIS的城市道路网最短路径分析

发搜寻到的两条边

的另一端点分别为 A1、A1',计算

SA1、SA

基于GIS的城市道路网最短路径分析

1'的加 权距离,分别记为 ds(A1)、ds(A1');从T点出发搜寻到的两条边的另一端

点分别为B1、B1',

记TB图1 最短路径搜索流程图1、TB1'的

加权距离分别为dt(B1)、dt(B1')。

第四步:将ds(A1)、ds(A1')作为当前点A1、A1'的标记值,d t(B1)、dt(B1') 作为当前点B1、B1'的标记值。也就是将起点或终点至该临时标记点子路径上所有边的权值之和作为当前点的标记值。同时ps(A1)、ps(A1')、 pt(B1)、pt(B1')均变为1。

第五步:用A1、A1'分别代替S,B1、B1'分别代替T,然后变量k自增k=k+1,重复第二、三、四步,但第三步中是从A1(A1')、B1(B1')出发,在直线段A

1T(A1'T)、TB1(TB1')

左右两侧各寻找一条与AT

搜索到的边加入对应的二叉树1 A1

′T 、TB ,对二叉树的当前点分别计算标记

1 TB1′ 夹角绝对值最小的边。把

值并作标记。以此类推,直至An,Bn会合于一点,即正向和逆向搜索都对同一点进行了标记,则点列S,A1,…,An(Bn),…,B1,T组成可能最短路径,路径长度为ds(An)+ dt(Bn)。若二者没有会合,也即双向搜索都未对同一点进行标记,则正向搜索到终点T,逆向搜索到起点S,生成两棵特殊的二叉树。相应方向已标记过的点不在搜索范围之内。

3 结论

本文根据城市交通道路网的特点,建立了道路网数据模型,并在综合考虑人们出行时的时间消耗和能量消耗的情况下,选择可达性作为道路权重,以此为搜索指标进行最短路径分析。本文所用最短路径算法对经典的Dijkstra算法进行了改进,在每次搜索过程中,不必遍历图中所有未标记的结点,只搜索当前结点的邻接结点。对于实际的道路网,每个结点的邻接点个数一般为2—5个,较之Dijkstra算法大大减少了搜索范围。而且求解的只是源点到终点间的最短路径,搜索的速度快,也增加了适用性。

参考文献

[1]白尘.交通路网中最优路径算法的道路权重选择.中国管理信息化,2009,12(15):54-56.

[2]鲍培明.距离寻优中Dijkstra算法的优化.计算机研究与发展,2001,38(3):307-311.

[3]王行风,贾凌.GIS支持下的城市交通网络最短路径研究. 计算机与现代化,2005,115(3):9-12.

[4]刘云翔,陈荦,李军,陈宏盛.基于城市道路网的最短路径分析解决方案.小型微型计算机系统,2003,24(7):1390-1393.

[5]赵春燕,王国华,周军.支持城市多种交通方式的最佳路径分析.测绘信息与工程,2009,34(4):8-10.

93

基于GIS的城市道路网最短路径分析

2010 4(下)

基于GIS的城市道路网最短路径分析

上一页第2页

你可能喜欢

  • 网络分析实验
  • 网络数据
  • 城市地理规划
  • Excel使用技巧大全(超
  • 公交查询系统
  • 最短路径算法
  • GIS实习报告
  • GIS空间分析

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email