地理信息系统课程GIS网络分析

网络分析模型§1网络分析基础§2最短路径分析§3最佳路径分析§4资源分配①将一批货物从甲地运到乙地，可以经过多条路线，如何求取运输费用最低的路线——最佳路径②当地下煤气管道改装时，若关闭某个阀门，需要确定受影响的用户——连通问题③某城市拟建立一消防站，如何确定10分钟之内能达到的所有街道——资源分配④常乐村15号在那个地方——地址匹配问题引入：什么是网络分析?在GIS中，网络分析是指依据网络拓扑关系（结点与弧段拓扑、弧段的连通性），通过考察网络元素的空间及属性数据，以数学理论模型为基础，对网络的性能特征进行多方面研究的一种分析计算。问题引入：§1网络分析基础网络：是由点、线构成的系统，通常用来描述某种资源或物质在空间中的运动。可表示为由网络结点集V、网络边集E和事件点集P组成的集合，即有D={V，E，P}网络分析：是对地理网络和城市基础设施网络等网状事物以及它们的相互关系和内在联系进行地理分析和模型化。网络分析的基本研究对象：线状目标和点状目标。网络分析的主要研究内容：最短路径分析、资源分配、连通分析等。由一系列相互连通的点和线组成，用来描述地理要素（资源）的流动情况。§1网络分析基础网络基本元素包括网络中心、边、结点、站、拐角和障碍等，如下图。§1网络分析基础1、资源：是网络中传输的物质、能量、信息等。资源通过在网络中的流动实现传输和分配。资源属性与网络通行规则联合作用影响资源在网络中的流动情况。2、链：图或网络中的线状要素，表现的是网络中的地理实体和现象，通常用中心线代表地理实体和现象本身。链有图形信息和属性信息。属性信息包括阻碍强度、资源需求量、资源流动的约束条件。2)道路是一双行道，且正向阻强为40km/s，负向阻强为35km/s，具体表达为链弧号起结点终结点正方向阻强（km/s）反方向阻强（km/s）p1p71740353）道路是一单行道，且阻强为20km/s，具体表达为：链弧号起结点终结点正方向阻强（km/s）反方向阻强（km/s）P6p86820-1(表不通)3、结点：网络链的两个端点4、站点：网络中装载或卸下资源的结点位置。站的属性主要有两种：资源需求量和阻碍强度。5、中心：网络中具有一定的容量，能够从链上获取资源的结点所在地。中心的属性有两种：一是中心的资源容量，一是中心的阻碍强度。6、障碍：对资源传输起阻断作用的结点或链，它阻碍了资源在与其相连的链间的流动，代表了网络中元素的不可通行状态。（障碍持续）7、拐角：网络结点处，所有资源流动的可能的转向。其属性主要是拐角的阻碍强度。8、权值：用于存储通过一条链或结点时所需要的成本。§2最短路径分析路径分析：是在指定网络的结点间找出最佳路径。最短路径：在网络两节点之间找到一条抗阻最小的路径。路径分析的关键：对路径的求解，即如何求出满足条件的最优路径。Dijkstra算法Dijkstra算法是最经典的按路径长度递增的次序产生最短路径的方法。Dijkstra算法的基本思想：标记源点到已得到点的最短路径，再寻找到下一个点的最短路径（由近及远寻找起点到其他节点的最佳路径，直至到达目标节点）。适用于所有弧的权为非负的最短路径算法。Dijkstra算法的具体步骤：（1）初始化：设置源s点：ds=0,ps=空集;其他点：ds=∞,ps=?;将起源点s标号，记k=s，其他点尚未处理；（2）距离计算。计算从所有标记的点k到其他直接连接的未标记的点j的距离lij，并令dj=min{dj，dk+lkj}（3）选取下一点。从上述结点集中，选取dj最小所对应的点为最短路径中的下一连接点i，并作标记。（4）找到点i的前一点。从已标记的点中找到连接到点i的前一点j*,并令i=j*作为前一点。（5）标记点i。如果所有点已标记，则算法完全退出，否则，记k=i，转到（2）再继续，直到所有点都已标记。如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）§3资源分配一、基本概念：资源分配：在网络中根据应用需求将资源分配到所需的地点。资源分配的研究问题包括：（1）需求点和供应点都确定的情况下，现在资源的分配，如物资配送；（2）新增供应点，如新的变电所选址；（3）新增需求点，如新建居民地。资源分配的核心：资源的定位及分配。资源的定位：指已知需求，确定在哪里布设最合适的供应点，即寻找最佳的供应点。资源的分配：就是确定需求源分别受哪个供应点服务。§3资源分配资源分配的数学模型：设有n个需求点Pi（xi,yi），bi是每个需求点的需求量（i=1,2,…,n）,m个供应点Qj（uj,vj）（j=1,2,…,m）。tij和dij分别是供应点Qj对需求点Pi提供的供应量和两点间的距离。若所有的需求点都受到供应点的服务，则若每个需求点都分配给与之最近的一个供应点，则需求点Pi的需求是否由供应点Qj供给可用矩阵（Xij）表示，且mjiijnibt1,,2,1,其他情况当,0;,,2,1,jkmkddbtikijiij其他情况供给受,0,1jiijQPX§3资源分配二、资源分配目标方程若资源分配要求供应点与需求点之间总的加权距离为最小，则相应的目标方程是若要求距离最小时，目标方程是若要求所有的需求点在一给定的服务半径s内，则目标方程是其中nimjijid11minsdsddcijijijiij,,nimjijd11minnimjijc11min4、连通性分析----最小生成树（1）概念连通图：在一个图中，任意两个节点之间都存在一条路。树：若一个连通图中不存在任何回路，则称为树。生成树的权数：生成树中各边的权数之和。最小生成树：图的极小连通子图。（2）应用：通信线路、快递56①树中的边数比节点数少1②树中两节点之间最多有一条边③树中任意去掉一条边，就变成不连通的图④树中添加一条边就会构成回路一般来说，一个图生成的树可能不止一个树的性质(4)算法（Kruskal，克罗斯克尔算法，也叫“避圈”法）1）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。2）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树。3）重复2），直到有M-1条边被选进生成树中，这M-1条边就构成最小生成树3.1.2连通性分析----最小生成树具体步骤克罗斯克尔算法(4)算法（Kruskal，克罗斯克尔算法，也叫“避圈”法）1）先把图中的各边按权数从小到大重新排列，并取权数最小的一条边为最小生成树中的边。2）在剩下的边中，按顺序取下一条边。若该边与最小生成树中已有的边，构成回路，则舍去该边，否则选中生成树。3）重复2），直到有M-1条边被选进生成树中，这M-1条边就构成最小生成树N个城市用高压线建立电网，若能设计把n个城市建立起来构成一个电网，使所用的电缆总长度最小，这就是一个最小生成树的问题