第十二讲 网络分析

地理信息系统GeographicalInformationSystem第十二讲网络分析2/8/20202概论什么是网络分析？为什么要进行网络分析网络数据结构网络数据模型网络分析能力2/8/20203什么是网络分析很多人类的社会、经济活动都是以网络形式运作；网络形式、容量和效率与社会生活息息相关网络在自然界常常存在，如河流2/8/20204网络示例铁路、公路电力网、电讯网煤气管网各种服务网络航空网络街道网络2/8/20205为什么要使用网络分析从甲地道乙地的最短路径是什么？如何设定一个服务中心？特定位置的服务中心是的服务范围？从一个位置到另一个位置的通行程度如何？从出发地到目的地，有多少条可行路线？如何在街道图上定位一个发生的事件？2/8/20206网络分析定义数学定义以图论和运筹学为基础，通过研究网络的状态以及模拟和分析资源在网络上的流动和分配情况，对网络结构及资源等的优化问题进行研究GIS定义依据网络拓扑关系，通过考察网络元素的空间与属性数据，以数学理论模型为基础，对网络的性能特征进行多方面的分析计算技术2/8/20207网络类型平面网络除节点外，网络链不相交，如公路网；非平面网络网络链可相交，如航空网络2/8/20208网络层次精细尺度网络，如街道网络中尺度网络，如交通规划粗尺度网络，如高速公路网2/8/20209网络数据结构具有图的结构结点/结点集：图中任意两条线段交点边/边集：图中的任意一条边（弧段）图：有限结点和边的集合网络：有向图具有一般地理数据的内容拓扑关系空间数据属性数据2/8/202010网络数据结构结点网络中分布的中间点、交点等，弧段交点链连接节点并具有运输能力的线段（弧段）2/8/202011地理网络的特殊要素3人10人5人学校8路公共汽车起点站8路公共汽车终点站6人路径站点中心拐点障碍点段2/8/202012地理网络的特殊要素站点网络中物流的装、卸位置，但不一定在网络结点上。如公交路线的汽车站、邮政网络的邮筒等中心网络中具有集中或分散资源的结点如公交系统的汽车总站、水系中的水库、街道网络中的学校、小区等2/8/202013地理网络的特殊要素（续）障碍点网络中限制资源流通的点，如河流的闸门拐点网络中物流方向发生改变的点有方向控制段弧或弧的一部分由起点和终点，可通过百分比形式衡量2/8/202014地理网络的特殊要素（续）路径具有属性的有序弧段的集合，表示一线型特征如公交系统中边家村到黄雁村路段路径系统路径和段的集合，常用来管理具有相同属性的多个线形特征如城市公交系统中的行车路线路径系统要使用统一的度量标准2/8/202015地理网络要素的属性数据阻抗资源在网络中运动的阻力大小，用时间、成本等衡量与链的长度、方向、属性、结点类型有关不同类型的阻抗要具有统一的量纲适用对象链（弧段、段）结点（拐点）2/8/202016地理网络要素的属性数据（续）资源需求量网络链或结点能收集的或可提供给某一中心的资源量弧段、结点如水网中水管的供水量、沿街道学生分布3人10人5人学校2/8/202017地理网络要素的属性数据（续）资源容量中心为满足各弧段要求而能提供的资源总量，或从一中心流向（接收）另一中心的资源总量，如水库容量、学校最大学生数等中心点：最大容量、服务范围、服务延迟数等站点：资源需求量（上、下）2/8/202018地理网络要素的属性数据（续）事件路径系统中某一路径的分段属性属性由用户定义，用路径的度量表示类型点事件：与一个位置对应，一个度量线事件：区段，两个度量连续事件2/8/202019网络分析主要内容路径分析最短路径最佳路径定位与分配定位分配定位与分配地址匹配爆管分析2/8/202020路经分析最佳路径含义类型单源点之间的最佳路经所有点对之间的最佳路经最佳路径数学模型最佳路径求解2/8/202021最佳路径的数学模型数学模型直接求解比较困难，目前主要采用戴克斯徒拉在1959年提出的算法jkpk,jwdddjkjk;,,2,1),min(012/8/202022最佳路径求解的依据最佳矩阵计算最佳含义要求两点之间直接相连，不直接相连着为不通简单路径，即互不相交整体最优则局部最优，即若两点S和T之间有一条最佳路径，则该路径上任何点到S的路径都是最佳的。2/8/202023Dijkstra算法步骤寻找从1点到其他点的最短路径2)3)()}(),(),(min{)(,Y},{},,{2)}1,1,1{,},,({},{}{,）1,},,,,{101111121，转给定值，则结束，反之或若处更改了路径值，则如在中的连接指针，例同时改变值（小于情况下），并有后的最佳路径值替代原入中的值发生变化，用加即在的路径值可能改变，的加入，使得其他已存的最佳路径。由于到经中，则称从加进若将要求为最佳的点中，选择到在设经过若干步骤后，初始化为连接数据集和设为中获取该值从）的最佳路径值集合为到候选点集和为顶点集合为到其余各点的最佳路径设初始化到其余各点的最佳路径现要求搜索从表示最佳路径值网络的连通矩阵为设网络的顶点集合为kkkjjjkjkjkkjjkikiinnnvvvlPlPvDvvvvXvvDvvdvDvDvvYXvYvvXPPMvvdDYvYXvYvXXvvvvvVM2/8/202024Dijkstra算法例解寻找从0点到其他点的最短路径0123450123450∞10∞30100∞05∞∞∞∞∞050∞∞∞∞∞0∞10∞∞∞20060∞∞∞∞∞043015210060203010505102/8/202025Dijkstra算法例解（续）寻找从0点到其他点的最短路径第一步：初始化相关数组X={0}Y={1,2,3,4,5}D={0,∞,10,∞,30,100}P={0,0,0,0,0,0}第二步：在Y中寻找到0的最佳路径X=X+{2}={0,2}Y=Y–{2}={1,3,4,5}D={0,∞,10,60,30,100}P={0,0,0,2,0,0}43015210060203010505102/8/202026Dijkstra算法例解（续）寻找从0点到其他点的最短路径第三步：在Y中寻找从0到其余点的最佳路径X=X+{4}={0,2,4}Y=Y–{4}={1,3,5}D={0,∞,10,50,30,90}P={0,0,4,0,0,4}43015210060203010505102/8/202027Dijkstra算法例解（续）寻找从0点到其他点的最短路径第四步：在Y中寻找从0经由4到其余点的最佳路径X=X+{3}={0,2,4,3}Y=Y–{3}={1,5}D={0,∞,10,50,30,90}P={0,0,0,4,0,4}43015210060203010505102/8/202028Dijkstra算法例解（续）寻找从0点到其他点的最短路径第五步：在Y中寻找从0经由3到其余点的最佳路径X=X+{5}={0,2,4,3,5}Y=Y–{5}={1}D={0,∞,10,50,30,60}P={0,0,0,4,0,3}43015210060203010505102/8/202029Dijkstra算法例解（续）寻找从0点到其他点的最短路径第六步：在Y中寻找从0经由5到其余点的最佳路径由于1中的值为∞，故退出43015210060203010505102/8/202030Dijkstra算法例解（续）寻找从1点到其他点的最短路径开始点到结点最佳路经最佳值01无无020，21003P(3)=4,P(4)=00,4,350040,43005P(5)=3,P(3)=4,P(4)=00,4,3,56043015210060203010505102/8/202031最佳路径计算点对计算对每个点重复Drikstra步骤运算复杂，速度较慢算法复杂度O(n3)Floyd算法邻接矩阵计算继续加强新算法的设计大规模数据的处理能力2/8/202032定位与分配通过网络模拟资源的供需分配问题规划重要的公共设施普通设施医院、教育、养老院等应急设施消防队、急救站等表述为设一定数量的需求点（消费点），求一定数量的供给点（公共设施）以及供给点的需求分配，用来完成某个规划目的2/8/202033定位与分配（续）图书馆设在哪儿合适呢？居民分布点公共设施2/8/202034定位与分配（续）1和2那个去合适呢？12居民分布点服务点2/8/202035定位与分配的常用模型最小距离法（P–中值定位模型）所有需求点到服务点的总距离为最小图书馆、食物配送、健康设施、垃圾站设置等最大覆盖模型指定时间或距离到达需求的覆盖面最大紧急救护、消防服务最大最小距离保证行程最小的情况下确保需求点在指定的最大距离范围内2/8/202036定位与分配的常用模型等分配模型服务点的服务在数量上相等阀值限制模型服务对象尽可能超过指定的量容量限制模型满足最大容量情况下的最大服务范围2/8/202037定位与分配问题的求解多目标数学规划问题目标函数、约束条件P-中值定位模型直接对上述问题进行求解比较麻烦，一般采用最优化发或启发式方式nmppaniadwamjniijmjijnimjijijij)(,,2,11)min(111112/8/202038地址匹配地址：网络上的空间位置，可通过门牌号、街道编码等实现在商业、犯罪控制、供需分析等常常使用2/8/202039爆管分析定义水、油、气等物质网络上管道或点设备（法门、仪表等）发生故障的分析问题。目的对该点断流，即检索出全部与该点直接相连的各种断流设备算法基于矢量数据的爆管算法基于栅格数据的爆管算法2/8/202040动态分段数据模型线性参照系与平面坐标系动态分段模型通过路径、量度和事件把线性参照性和平面系组合在一起查询、显示和空间分析事故发生地点的显示与分析路面损坏分析