第三章第四节-网络分析

第三章第四节_网络分析第一页，共80页。一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？245563344494邮路问题：管梅谷（1962年）提出Postoffice第二页，共80页。我们在实际生活、生产和科研活动中经常看到许多的网络，如互联网、通信网、公路网、管道网、销售网等。对网络进行研究是希望解决其中的一些优化问题，网络最优化能为人们管理和控制这些网络系统提供一套有效的方法ACBD3.4网络分析第三页，共80页。特点网络是用于实现资源运输和信息交流的一系列相互连接的线性特征组合网络数据模型是真实世界中网络系统（如交通网、通讯网、自来水管网、煤气管网等）的抽象表示网络分析的基础：线—点拓扑关系依据网络拓扑关系，根据网络的空间数据、属性数据，对网络的特征、性能进行分析矢量数据特有的空间分析方法第四页，共80页。ArcGIS：查找距离事故最近的医院ArcGIS：确定最短投递线路网络分析例子第五页，共80页。网络数据模型网络模型是对现实世界网络的抽象。在模型中，网络由链（Link）、结点（Node）、站点（Stop）、中心（Center）和转向点（Turn）组成3.4.1网络数据模型第六页，共80页。结点（Nodes）：网络中链的结点，如港口、车站等链（Links）：连接两个结点的弧段，即网络中流动的管线如街道、河流、水管等，为供物体运营的通道，链间的连接关系由弧段-结点拓扑数据结构来表达，属性如资源流动的时间、速度等。中心（Centers）：网络中位于结点处，具有沿着链收集或发放资源能力的设施，是接受或分配资源的位置，如邮局、电站、水库等网络组成要素与属性第七页，共80页。网络组成要素与属性站点（Stops）：资源沿着网络路径流动时被分配或收集的位置，如邮件投放点、车站等，其状态属性有资源需求，如产品数量障碍（Barriers）：禁止网络中链上流动的节点，即资源不能通过的节点，不带状态属性。拐角点（Turns）：链路相交处，资源流向发生改变的点，状态属性有阻力（角度、拐弯时间和方向限制等，如在8点到18点不允许左拐）第八页，共80页。上述要素除障碍和结点之外，都用图层要素形式表示，并用一系列相关属性来描述。这些属性是网络中的重要部分。例如，在城市交通网络中，每一段道路（链）都有名字、速度上限、宽度等；停靠点处有大量的物资等待装载或下卸等属性在这些属性中，有三个重要的概念：阻强（阻力）、资源需求量、资源容量网络组成要素与属性第九页，共80页。1、阻强阻强是指资源在网络中运移阻力的大小。它是描述链与拐弯所具有的属性链弧的阻强是指从链的一个端点至另一个端点所需克服的阻力，如链弧段的长度可作为阻强的描述参数阻强的大小应根据多种因素来确定，如弧段的特性，网络中运移资源的种类、运移的方向，弧段中的特殊情况等

网络组成要素与属性第十页，共80页。转弯的阻强描述了从一条链弧经结点到另一条链弧的阻力大小，它随着两相连链弧的条件状况而变化运用阻强概念的目的在于模拟真实网络中各路线及转弯的变化条件。对不构成通道的弧段或转弯往往赋以负的阻强。这样，在分析应用中,如选取最佳路线时,可自动跳过这些弧段或转弯网络组成要素与属性第十一页，共80页。2、资源需求量

指网络中与弧段和停靠点相联系资源的数量。如在停靠点装卸物的件数等3、资源容量

指网络中心为满足各弧段的需求，能够容纳或提供的资源总数量。如学校的容量指学校能注册的学生总数；停车场能停放机动车辆的空间；水库的总容量等网络组成要素与属性第十二页，共80页。1、链链号起结点终结点长度(km)正方向阻强(km/h)反方向阻强(km/h)资源需求量202445.33555（-1:表示不通，单行道）…425535网络要素的表示第十三页，共80页。2、拐弯

结点号从弧段至弧段角度时间阻强(s)34L2L1906034L1L11803034L2L3-90-1（不允许拐弯）34L1L300（无阻强）网络要素的表示第十四页，共80页。停靠点：直接在相应的结点上附上需求量属性，负为下卸，正值为装载中心：资源最大容量和服务范围等结点号需求量453546-20结点号资源最大容量服务范围241000200………学校3、站点（停靠点）、中心的属性网络要素的表示第十五页，共80页。定向网络A.特征：流向由源（Source）至汇（Sink）、网络中流动的资源自身不能决定流向。如水流的路径是预先设定好的，它只能按照预先设定好的路径进行流通B.其对应数据结构中的有向图非定向网络（交通网络模型）A.特征：流向不确定、流动的资源可以决定流向。如交通系统中流通介质可以自行决定方向、速度和目的地B.其对应数据结构中的无向图网络类型第十六页，共80页。路径分析资源分配选址与服务范围3.4.2网络分析功能第十七页，共80页。路径分析是用于模拟两个或两个以上地点之间资源流动的路径寻找过程。当选择了起点、终点和路径必须通过的若干中间点后，就可以通过路径分析功能按照指定的条件寻找最优路径距离时间费用等（1）路径分析第十八页，共80页。（1）路径分析1）最短路径或最低耗费路径确定起点、终点和要经过的中间点、链，求最短或耗费最小路径2）动态最佳路径分析实际中权数可能是变化的，可能会临时产生一些障碍点，要动态计算最佳路径第十九页，共80页。第二十页，共80页。花费的时间、路线长度第二十一页，共80页。P102-104核心算法用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最佳路径求解有多种不同的方法，最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法第二十二页，共80页。Dijkstra算法基本思想——按最短路径长度递增的顺序，逐个产生各个最短路径E.W.Dijkstra第二十三页，共80页。Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了）。第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度主要特点：以起始点为中心向外层层扩展，直到扩展到终点为止Dijkstra算法第二十四页，共80页。基本过程（1）初始时，S只包含源点，即S＝源点，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（2）从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权（4）重复步骤（2）和（3）直到所有顶点都包含在S中第二十五页，共80页。例子V5V0V4V1V3V21006030101020505带权有向图第二十六页，共80页。例子（思路）CiBi如图所示，A为所求最短距离的起点，其他Bi，Ci为终点我们要求的是一系列最短距离。假定这些最短距离互不相等,那么我们可以把这些最短距离按升序（从小到大）排列我们把所有顶点分为两类B和C。令A到Bi这些顶点的最短距离不为无穷大。A到Ci这些顶点的最短距离为无穷大这就说明A到Ci中的点要么不通，要么通过Bi中的点与之连接A第二十七页，共80页。这样，对于A到Ci中任何一个点的最小距离，我们总可以在Bi中找到一点，使得A到这一点的最小距离小于前一个距离。（因为：A到Ci中的点要么不通，要么通过Bi中的点与之连通）因此，我们可以先不考虑Ci中的点例子（思路）CiBiA第二十八页，共80页。于是，对于右图，我们第一步只考虑下图：V5V0V4V1V3V210060301010505V5V0V4V21003010Bi={v2,v4,v5}例子（思路）20第二十九页，共80页。例子(思路)我们用mindist[]这个数组来保存由V0到其它顶点的最小距离，这些距离按升序排列考虑右图：第一步，通过比较，我们知道mindistance[V0][V2]=mindist[0]=10，（V0-V2）这是我们求出的第一个最小距离,标记V2

一旦我们得到V2，我们就可以知道：V5V0V4V21003010例子（思路）V350第三十页，共80页。V0跟V2直接连通到的点V3之间的最小距离不再是无穷大，它应当是mindistance[V0][V2]+dis[V2][V3]，这样我们应当把V3放入前面的集合Bi中（注意：有多少V2直接连通到的点都应当考虑进来）Bi={v2,v4,v5,v3}V5V0V4V21003010V350例子（思路）第三十一页，共80页。第二步，我们把与V2直接连通的点V3考虑进来dis[0][5]=100；dis[0][4]=30；dis[0][2]=10；dis[0][3]=60；除10以外，30是最小的我们可以证明30是V0到其它顶点除10以外最小的V5V0V4V21003010V350例子（思路）第三十二页，共80页。这样我们得到我们的第二个最小距离：Mindistance[V0][V4]=mindist[1]=30，(V0-V4)接下来，我们把V4与之直接连通的点考虑进来……V5V0V4V21003010V350V5V0V4V1V31006030101050520V2例子（思路）第三十三页，共80页。以v0为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量D的变化见D0—D4V5V0V4V1V31006030101050520V2例子第三十四页，共80页。例子结果终点

从v0到其它各结点的最短路径v1∞∞∞∞∞v210(v0,v2)v3∞60(v0,v2,v3)50(v0,v4,v3)v430(v0,v4)30(v0,v4)v5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)第三十五页，共80页。63567106879129第三十六页，共80页。“供（Supply）”代表一定数量的资源或货物，它们位于被称之为“CENTER”的设施中“需（Demand）”指对资源的利用。Allocation分析就是在空间中的一个或多个点之间分配资源的过程（2）资源分配（Allocation）第三十七页，共80页。中心往四周输出四周往中心集中电站学校分配方式（2）资源分配（Allocation）第三十八页，共80页。资源分配的应用包括消防站点分布和求援区划分、学校选址、垃圾收集站点分布，停水停电对区域的社会、经济影响估计等

1）负荷设计用于估计排水系统在暴雨期间是否溢流，输电系统是否超载等

2）时间和距离估算除用于交通时间和交通距离分析外，还可模拟水、电等资源或能量在网络上的距离损耗（2）资源分配（Allocation）第三十九页，共80页。资源分配网络模型由中心点及其状态属性和网络组成（2）资源分配（Allocation）解决资源的有效流动和合理分配第四十页，共80页。资源分配的核心是：资源的定位和分配资源定位：中心点（供应点）的选择资源分配：需求源接受那个供应点服务的问题（2）资源分配（Allocation）第四十一页，共80页。怎么确定中心点的位置？（2）资源分配（Allocation）第四十二页，共80页。中心选址问题的实例某县要在其所辖的8个乡镇之一修建一个消防站，为8个乡镇服务，要求消防站至最远乡镇的距离达到最小。假设该8个乡镇之间的交通网络被抽象为下图所示的无向赋权连通图，权值为乡镇之间的距离。下面求解消防站应设在哪个乡镇，即哪个顶点？v6v8v1v7v5v4v2v389363253757第四十三页，共80页。中心点选择：中心点选址问题中，最佳选址位置的判定标准：使其所在的顶点与图中其它顶点之间的最短距离的最大值达到最小求网络图的中心点问题。这类选址问题适宜于医院、消防站等服务设施的布局问题第四十四页，共80页。1.用Dijkstra算法计算出每一个顶点vi至其它各顶点vj的最短路径长度dij(i,j=1,2,…,6)，写出距离矩阵：步骤第四十五页，共80页。2.求距离矩阵中每行的最大值，即各个顶点的最大服务距离，得e(v1)=14,e(v2)=15,e(v3)=20,e(v4)=12,e(v5)=15,e(v6)=17,e(v7)=12,e(v8)=20最后计算最大服务距离的最小值。显然，e(v4)=e(v7)=min{e(vi)}。所以，消防站应建在v4或v7点所在的乡镇即可第四十六页，共80页。基于网络的服务区基于缓冲区的服务区两者比较生成的原理不同：前者靠网络中的路径产生服务区边界，后者按直线距离产生服务区边界一般情况下，后者比前者的范围要小适用的范围不同服务范围（ServiceArea）第四十七页，共80页。选址是确定机构设施的最佳地理位置，需要考虑需求和供给在空间上的相互作用，以获得最大的经济效益或最小的运输费用位置-分配问题可描述为：在网络中给定一定数量的需求点，求一定数量的的供给点，以及供给点的需求分配有各种的求解方法（3）选址第四十八页，共80页。应用计算中心地的等时区，等交通距离区，等费用距离区等进行城镇中心，商业中心或者港口等地的吸引范围，寻找最近的商业中心第四十九页，共80页。ArcGIS的网络分析ArcGIS的网络分析分为传输网络（NetworkAnalyst）和效用网络（UtilityNetworkAnalyst），前者是分析非定向网络的，比如道路网等，后者是用来分析定向网络的，比如水、电网络等。传输网络（NetworkAnalyst）基于NetworkDataset（网络数据集），效用网络（UtilityNetworkAnalyst）基于GeometricNetwork（几何网络）第五十页，共80页。使用UtilityNetworkAnalyst分析应用基本概念建立GeometricNetwork路径分析第五十一页，共80页。GeometricNetwork由一套相互连接的边edge、节点Junction组成，并且包含ConnectivityRules（连接规则）Edge与节点相连，是资源流动的纽带；Junction连接边Edge，引导从一条边到另一条边的移动；转弯记录在两个或多边之间运动的信息。其中Edge和Junction是网络的基本结构。网络中的连通性处理边、节点和其他元素间的连接利用街道要素类来创建Edge元素，街道交叉要素类创建Junction元素，另外铁路线和公交线也可以用来构建网络Edge元素，火车站和公交车站也可用来构建网络节点Junction素1基本概念第五十二页，共80页。成本（Cost）限制（Restriction）可通行性（Enable）网络属性包括第五十三页，共80页。成本（Cost）如行车时间、路线距离等通过字段设置成本常用METERS、MINUTES、FT_MINUTES（上行耗时）、TF_MINUTES（下行耗时)，默认单位是：分钟，表示COST成本字段ESRI网络分析工具自动解析这些字段作为成本分析字段第五十四页，共80页。通常设置ONEWAYONE_WAY字段表示，ESRI系统自动识别该字段，该属性值为空或除FT、TF、N三字段外，表示道路没有限制；FT表示从西向东、从北向南可以行驶；TF表示从东向西、从南到北可以行驶；N表示道路禁止通行限制（Restrictions）第五十五页，共80页。网络的Enabled或者Disabled状态是由要素属性字段Enabled设置的，可以选择的属性为True，False，在创建GeometricNetwork时，该字段自动添加为输入要素中，并且缺省状态下属性值为True可通行性（Enable）第五十六页，共80页。2建立GeometricNetwork准备在线图层必须做拓扑检查：“不能相交或者重叠”

使用planarizeline处理第五十七页，共80页。GeometricNetwork的建立必须基于FeatureDataset，数据应该有线图层2建立GeometricNetwork第五十八页，共80页。设置参与网络图层是否添加Enabled字段2建立GeometricNetwork第五十九页，共80页。打开自动捕捉功能：让输入在建立过程中自动调整并捕捉打开设置联系要素类型对话框：设置源（Source）或汇（Sink）2建立GeometricNetwork第六十页，共80页。3最短路径分析在ArcMap中加载数据打开UtilityNetworkAnalyst工具条

第六十一页，共80页。3最短路径分析1）添加旗帜flags的类型，使用toolsaddJunctionflag：添加端点addEdgeflags：添加边addJunctionbarrier：添加故障端点addEdgebarrier：添加故障边第六十二页，共80页。2）分析内容设置不参与分析图层清除设置Flags清除设置故障清除结果。设置权重等有关参数3最短路径分析第六十三页，共80页。障碍物

3最短路径分析选择Tracetask中FindPath使用Slove按钮获得结果第六十四页，共80页。使用NetworkAnalyst分析应用建立NetworkDataSet最短路径分析其他分析第六十五页，共80页。1建立NetworkDataSet准备在线图层必须做拓扑检查：“不能相交或者重叠”

使用planarizeline处理第六十六页，共80页。在ArcCatalog中使用两种方法1）选择shp文件，右键