网络分析与分配模

《网络分析与分配模》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、6・网络分析対地理网络（如交通网络）、城市基础设施网络（如各种网线、电力线、电话线、供排水管线等）进行地理分析和模型化，是地理信息系统屮网络分析功能的主要口的。网络分析是运筹学模型中的一个基本模型，它的根本H的是研究、筹划一项网络工程如何女排，并使其运行效果最好，如一定资源的最佳分配，从一地到另-•地的运输费用最低等。其基本思想则在于人类活动总是趋于按一定目标选择达到最佳效果的空间位置。这类问题在补会经济活动中不胜枚举，因此在地理信息系统中此类问题的研究具有重要意义。6.1网络数据结构网络数据结构的基本组成部分和属性如下：1）链（Link）网络中流动的管线，如街道、河

2、流、水管等，其状态属性包括阻力和需求。2）结点（Node）*网络中链的结点，如港口、车站、电站等，其状态属性包插阻力和需求等。结点中乂有下而儿种特殊的类型。•障碍（Barrier）,禁止网络中链上流动的点。•拐点（Turn）,出现在网络链屮的分割结点上，状态属性右阻力，如拐弯的时间和限制（如在8：00到18：00不允许左拐）。•中心（Center）,是接受或分配资源的位置，如水库、商业中心、电站等，其状态属性包折资源容量（如总量），阻力限额（屮心到琏的最人距离或时间限制）。•站点（Stop）,在路径选择中资源增减的结点，如库房、车站等，其状态属性有资源需求，如产品数量

3、。除了基本的组成部分外，有时还要增加一些特殊结构，如邻接点链表用來辅助进行路径分析。6.2主要网络分析功能6.2.1路径分析1）静态求最佳路径：在给定每条链上的属性后，求最佳路径。2）N条瑕佳路径分析：确定起点或终点，求代价最小的N条路径，因为在实践中最佳路径的选择只是理想情况，山于种种因素而要选择近似最优路径。3）最短路径或最低耗费路径：确定起点、终点和要经过的中间点、中间连线，求最短路径或最小耗费路径。4）动态最伴路径分析：实际网络中权值是随权值关系式变化的，可能还会临时出现一些障碍点，需耍动态的计算最佳路径。在图数据结构中称为“弧”。6.2.2计算最短路径的Di

4、jkstra算法为了迓行网络最短路径分析，需要将网络转换成有向图。无论是计算最短路径还是最佳路径，其算法都是一致的，不同之处在于有向图中每条弧的权值设置。如果要计算最短路径,则权至设置为两个节点的实际距离；而要计算最佳路径，则可以将权值设置为从起点到终点的时间或费用°Dijkstni算法nJ以用于计算从有向图中任意一个节点到其它节点的最短路径。下面是该算法的描述。1）用带权的邻接矩阵Co"來表示带权的h个节点的有向图，Cost[i,j]：校示弧5,吁>的权值，如果从叫到吁不连通，则Cost[iJ]=-o图8-14^示了一个带权有向图以及其邻接矩阵。OOOO10OO30

5、100OOOO5OOOOOOOOOOOO50OOOOOOOOOOOOOO10OOOOOO20OO60OOOOOOOOOOOO图8-14：带权的有向图和邻接矩阵然后，引进一个辅助向量30,每个分量〃表示从起始点到每个终点旳的最短路径长度。假定起始点在有向图屮的序号为汐，并设定该向量的初始值为：Dist[i]=Cost[iO,i]vrEV。令s为己经找到的从起点出发的最短路径的终点的集合。2）选择旳,使得Dist[jJ=Min{Distli]VjWV~S}岭EV就是当前求得的一条从咖出发的最短路径的终点，令S=SU/vjl3）修改从咖出发到集合SS中任意一顶点以的最短路

6、径长度。如果Distfj/+Cost!j,k]

7、"算的结果终卢从”到其它各个节点的最短路径V/OOOOOOOOOO无"210(v0,v2)"3OO60(Vo,V2,V3)50(v0,v4,v3)V43030（Vo,V4）（v0,v4）V5100（Vo,v5）100（Vo,V5）90（Vo,V4,V5）60（

8、V（）,V4,V3,V5）9v2V4V?V5在实际应川屮，采川Dijkstra算法计算两点之间的最短路径和求从一点到其它所有点的最短路径所需要的时间是一样的，算法时间复杂度为0（，丿。6.2.3资源分配资源分配网络模型由屮心点（分配屮心或收集屮心）及其属性和网络组成。分配有两种形式，一种是由分配小心向四周分配，另一种是「I讷周向收集中心分配。资源分配的应用包括消防诂点分布和求援区划分、学校选址、垃圾收集站点分布，停水停电对区域的社会、经济影响估计等。1）负荷设计负荷设计可川于估计排水系统在暴雨期间是否溢流，输电系统是否超载等。2）时间和距离估算时间和