基于现实城市道路网络的最短路径分析,解决方案
基于GIS的城市道路网最短路径分析
韩俊卿
太原师范学院,山西太原 030012
摘要 运用GIS网络分析功能,针对城市道路网的特点,建立了基于路段连接的道路网络模型,并选择可达性作为道
路权重对道路网进行了最短路径分析。对经典的Dijkstra算法加以改进,提出了求解道路网任意两点间最短路径的算法,该算法搜索速度快,具有较强的适用性。关键词 最短路径;可达性;道路网
中图分类号 TP393 文献标识码 A 文章编号 1674-6708(2010)17-0092-02
0 引言
随着计算机和地理信息科学的发展,地理信息系统因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一,在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用,通用的网络分析功能包括路径分析、资源分配、连通分析、流分析等。网络分析中最基本和最关键的问题是最短路径问题,它作为许多领域中选择最优问题的基础,在交通网络分析系统中占有重要地位。
从道路网络模型的角度看,最短路径分析就是在指定道路网络的两节点间找出一条阻碍强度最小的路径。根据阻碍强度的不同定义,最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。相应地,最短路径问题就成为最快路径问题、最低费用问题等。因此,城市道路网作为一种大型网络设施有其本身的特征。它一方面包含网络本身的拓扑特征;另一方面还包含了大量反应地理位置特征的几何数据。本文根据道路网的特点,运用GIS网络分析功能对道路网络模型、道路的权重选择以及快速寻求路网中两节点间的最短路径算法分别进行了研究。
路径算法是路径选择的搜索工具,决定了如何在庞大的路网数据库中找到最佳的可行路径。道路权重则是路径选择的搜索指标,是最短路径算法的依据。因此,道路权重的选择直接影响到最优路径算法的合理性。
一个城市的道路网络由不同等级的道路组成,不同等级的道路的通行能力和功能要求均不相同。只有整个城市的交通负载根据出行者目的的不同,均衡分布在不同等级的道路上,城市的路网才能得到最有效的利用。因此单纯的选择距离、时间或道路的通行能力作为道路权重都不太客观,需要选择一种比较综合的指标作为道路权重。可达性是Hansen于1959年首次提出的概念,用于定义交通网络中各结点间相互作用机会的大小。其表述的是路网中任意点之间通达的可能性及难易程度,数学上指单位时间内可实现通达的直线距离[1],即
=D CK=D/t CK为可达能力(km/m),是可达性的量度。
可达性同时考虑了时间和距离的因素,把道路交通的固定设施和移动工具有机结合起来,而且避免了以道路通行能力作为权重可能造成的城市路网全局负载问题。因此以可达性为道路权重是一个比较综合的指标,具有更大的合理性。
1 道路网模型及权重设置
1.1 道路网模型建立
城市道路网主要由众多道路相交、相连构成。在纵横交织、
错综复杂的道路网络中,道路间的地理位置关系相当复杂,一条道路可能与若干条道路相交相连,且其相交相连的模式复杂。为了避免过多地考虑道路间的拓扑关系,抽取道路网中道路交叉路口作为分析对象,并对道路以交叉路口为结点进行分割,成为路段。这样,整个网络图将由交叉路口点和路段组成,并定义交叉路口点为网络的结点,路段为网络的弧。从而建立基于路段连接的网络模型,其模型形式表述为:
2 最短路径算法
最短路径问题的算法有很多种,包括基于限制条件的深度优
先搜索算法、Dijkstra算法、Floyd算法、A*算法等,各种算法在空间复杂度、时间复杂度、易实现性等方面各具特色。其中,采用启发式策略的Dijkstra算法是目前公认的求解最短路问题的经典算法。但Dijkstra算法在基于网络的权矩阵求解最短路问题的计算机算法和程序中,运用了关联矩阵、邻接矩阵和距离矩阵的概念。在存储图形数据和运算时,需要定义N×N的数组(其中N为网络的结点数),当网络的结点数较大时,将占有大量的计算机内存。如果不对Dijkstra算法进行优化,该算法很难在实际中得到应用。
在原始的Dijkstra算法中,每次在临时标记点中搜索路径最短的结点时都要遍历所有的临时标记结点。解决办法就是将临时标记结点按照最短路径排序,每个搜索过程不必全部遍历或者较少地遍历临时标记点。或者尽量减少最短路径分析过程中搜索的临时结点数量。基于此思想,提出了以下优化算法。
2.1 算法原理
利用两点之间直线最短的原理,在道路网中,如果两结点间存在一条边,则该边为两结点间的最短路径。若不存在一条边,则连接起、止点的直线段代表了一个路线的趋势,顺着连线方向的某条边是最短路径的可能性最大。依据此思想,可以构造2个矢量,矢量一以当前结点为起点,目标点为终点;矢量二以当前结点为起点,当前结点的邻接点为终点。将矢量二的方向值与矢量一的方向值相减得到两矢量间的夹角。由夹角最小的边组成的路径最接近于最短路径。
由于只依据矢量夹角作为求解最短路径中路段集合的要素,可能造成求得的路径因左右方向的震荡而增加路径的总长度,使
R=(N,R,L)R
w
R=x,yx,y∈N,且L(x,y)
L=lxyx,y∈R R
{
}
}
其元素为有序对x,y且,L(x,y)}表示由结点x到结点y存在一条有向通路;LR代表路段长度集合,其元素lxy表示有向路段x,y的加权长度。其中,路段的加权长度是指根据目标函数要求,综合各种动态实时信息和静态属性信息后所得的路段参数,而并非真实意义下的长度。
1.2 道路网权重选择
式中,RW代表道路网络;N代表结点集;R代表路段集合,
在交通路网中,两点间最优路径算法的优劣主要受到2个因素的影响,即所使用的最短路径算法和所选择的道路权重。最短
韩俊卿,讲师,工作单位:太原师范学院地理信息系统专业,学历:硕士,研究方向:测绘科学与地理信息系统

2010 4(下)92

信息科学 Information Science 基于GIS的城市道路网最短路径分析韩俊卿 太原师范学院 , 山西太原 030012 摘要 运用 GIS 网络分析功能 , 针对城市道路网的特点 , ...
3页 2财富值 GIS城市道路最短路径算法研... 5页 免费 基于GIS的城市道路网最短路... 6页 免费 实验8、Arcgis道路网络分析... 11页 免费...
基于GIS的城市路网拓扑关系的自动建立及最短路径分析_专业资料。采用Arc-Node路网数据模型,建立了基于MapInfo的乌鲁木齐市城市道路路网,利用GIS编程技术完成了路网交点...
复杂性分析,然后结合城市道路网络给出了实际算例,比较分析了最短路径关键边 ,最...本设计研究对基于 WebGIS的城市旅游信息系统开发进行了探索性研究,为城市旅游信息...
基于 的城市道路网最短路径算法探讨 严寒冰摘 要 刘迎春杭州 ...{ 在数学中被认为是 z 引 言 本文在对城市道路网络进行大量分析% 验的实...
基于GIS的最短路径分析_专业资料。GIS是综合处理和分析地理空间数据的一种技术... 基于GIS的城市路网拓扑关... 40人阅读 4页 2.00 基于MapGis的道路网络...
基于GIS的最短路径分析_专业资料。GIS是综合处理和分析地理空间数据的一种技术... 基于GIS的城市路网拓扑关... 40人阅读 4页 2.00 基于MapGis的道路网络...
基于GIS的最短路径分析_天文/地理_自然科学_专业资料。2012 年第 34 卷 第... 并已成为 城市道路交通、作战指挥自动化、网络通信、城市规划等许多 网络优化...
基于GIS的城市路网拓扑关系的自动建立及最短路径分析_天文/地理_自然科学_专业...1 道路图层的建立与拓扑处理乌鲁木齐市道路图层的建立 在建立乌鲁木齐市基础道路...
热门文档