8.6. 网络分析

网络是地理信息系统(GIS)中一类独特的数据实体,它由若干线性实体通过结点连结而成。网络分析是空间分析的一个重要方面,是依据网络拓扑关系(线性实体之间,线性实体与结点之间,结点与结点之间的连结、连通关系),并通过考察网络元素的空间、属性数据,对网络的性能特征进行多方面的分析计算。

与GIS的其它分析功能相比,关于网络分析的研究一直比较少,但是近年来由于普遍使用GIS管理大型网状设施(如城市中的各类地下管线、交通线、通讯线路等),使得对网络分析功能的需求迅速发展,GIS平台软件纷纷推出自己的网络分析子系统。

8.6.1. 网络数据模型――几个基本概念

网络是由若干线性实体互连而成的一个系统,资源经由网络来传输,实体间的联络也经由网络来达成。网络数据模型是真实世界中网络系统(如交通网、通迅网、自来水管网、煤气管网等)的抽象表示。构成网络的最基本元素是上述线性实体以及这些实体的连接交汇点。前者常被称为网线或链(link),后者一般称为结点(node)。

网线构成网络的骨架,是资源传输或通讯联络的通道,可以代表公路、铁路、航线、水管、煤气管、河流等等;结点是网线的端点,又是网线汇合点,可以表示交叉路口、中转站、河流汇合点等。

除了上述基本网络元素之外,由于分析任务的不同,网络还可能有若干附属元素,如在路径分析中用来表示途经地点的可以进行资源装卸的站点(stop);在资源分配中用来表示资源发散地点或资源汇聚地点的中心(center),对资源传输或通讯联络起阻断作用的障碍(barrier)等等。

由于通用性的不同以及网络分析功能的侧重点不同,各个地理信息系统的网络模型也不尽相同,差异主要体现在对网络附属元素的分类和设定上。

针对网络分析的需要,作为网络基本元素的网线或结点除自身的常规属性外,还要具有一些特殊的属性数据。比如,为了实施路径分析和资源分配,网线数据应包含正反两个方向上的阻碍强度(如流动时间、耗费等)以及资源需求量(如学生人数、水流量、顾客量等),而结点数据也应包括资源需求量。特别应该指出的是,在有些GIS平台(如ARC/INFO、MAPGIS)中,结点还可以具有转角数据,从而可以更加细致地模拟资源流动时的转向特性。具体地说,每个结点可以拥有一个转向表(turntable),其中的每一项说明了资源从某一网线经该结点到另一网线时所受的阻碍强度。

对于附属的网络元素,与其相关的数据则主要用来满足网络分析的需要。与中心相联系的数据包括该中心的资源容量、阻碍限度(资源流出或流向该中心所能克服的最大累积阻碍),有些GIS系统还允许赋予中心一定的延迟量,以表达该中心相对于其它中心进行资源分配的优先程度。与站点相关的数据一般有传输量(即资源装卸量)、阻碍强度。障碍一般无需任何相关数据。

以上所讨论的,是在GIS特别是通用GIS平台中较为广泛采用的网络模型及相关概念,正如前面所说,不同的GIS系统的网络模型往往会在网络附属元素的设定和运用方面体现出自身的特色。对于网络分析系统的设计研制者而言,重要的问题在于建立一个抽象的、具有相当适应面的,并且也是便于实现分析任务的网络模型;而对于这一系统的使用者而言,关键之处在于:深入理解现实网络系统中各个组成部分的特点及其相互关系,明确自身的管理分析任务,在此基础上,用网络模型中的不同元素合理地表示这些组成成分。

8.6.2. 常规的网络分析功能

 虽然各个GIS系统的网络分析功能有所不同,但有些分析功能是用户经常需要的,以下是常见的网络分析功能。

1.路径分析

路径分析是GIS中最为普遍的也是基本的功能,其核心是对最佳路径和最短路径的求解。救护车需要了解从医院到病人家里走哪条路最快;旅客往往要在众多航线中找到费用最小的中转方案,这些都是最佳路径求解的例子。从网络模型的角度看,最佳路径求解就是在指定网络中两结点间找一条阻碍强度最小的路径。最佳路径的产生基于网线和结点转角(如果模型中结点具有转角数据的话)的阻碍强度。例如,如果要找最快的路径,阻碍强度要预先设定为通过网线或在结点处转弯所花费的时间;如果要找费用最小的路径,阻碍强度就应该是费用。当网线在顺逆两个方向上的阻碍强度都是该网线的长度,而结点无转角数据或转角数据都是零时,最佳路径就成为最短路径。

最短路径分析需要计算网络中从起点到终点所有可能的路径,从中选择一条到起点距离最短的一条。用于最短路径分析的算法很多,其中最著名的是Dijkstra算法(Dijkstra, 1959),该算法可描述如下:

设一个网络由可k个结点组成,以N ={ni=1,2,…,k}表示结点集,其中一个结点为起始结点,设其为ns。Dijkstra算法将N划分成两个子集,一个子集包含那些到起始结点的最短距离已确定的结点,称这些结点为已确定结点,以s表示这一子集;另一个子集包含未确定结点,即它们到起始结点的最短距离尚未确定,以Q表示这一子集。又设d为一个距离矩阵(array),存放每个结点到ns的最短距离,d(i)表示结点ni到ns的最短距离;p为一前置结点矩阵,存放由ns到其他结点的最短路径上每个结点的前一个结点,p(i)表示结点ni在最短路径上的前一个结点。已知每两个相连结点之间的距离(或它们之间路径的长度),Dijkstra算法按如下几个步骤运行:

(1)将d和p初始化,使d的每个元素值为无穷大,p的每个元素值为空值,并设S和Q为空集;

(2)将ns加入Q,令d(s)=0;

(3)从Q中找出到ns最短距离为最小的结点,设该结点为nu

(4)将nu加入S,并将它从Q中删除;

(5)找出与nu相连的所有结点,从这些结点中取出一个,令其为nv

 ① 如nv已存在于s中,则执行下面第②步,否则,作如下判断:

 如果d(v) < d(u) + n-u和nv之间的距离,执行第②步;

 否则{令d(v) = d(u) + nu和nv之间的距离;

      p(v)=nu

      将nv加进Q;

 ② 如果与nu相连的所有结点都已作过上述判断,继续执行第(6)步;否则,取下一个未判断结点,令其为nv,执行上面的第①步;

(6)判断Q是否为空集,若不是,回到第(3)步;否则,停止运算。

在某些情况下,用户可能要求系统能一次求出所有结点之间的最佳路径,或者要了解两结点间的第二、第三乃至第K条最佳路径。这种需求的提出往往是由于现有网络模型不能包容所有特殊或突发的情况。

另一种路径分析功能是最佳游历方案(包括网线游历和结点游历)的求解。警察需要了解巡查完他担任巡逻的各个街道的最有效线路,铁路巡道员也需要知道巡查完他的路轨的最佳路线,这些都是网线最佳游历方案求解的例子,也就是给定一个网线集合和一个结点,求解最佳路径,使之由指定结点出发至少经过每条网线一次而回到起始结点。结点最佳游历方案求解,则是给定一个起始结点、一个终止结点和若干中间结点,求解最佳路径,使之由起点出发遍历全部中间结点而达终点。推销员可以利用求解结果以尽可能最少的旅程遍访其所分配的每一座城市;商场送货车每天送大量的商品到各个居民点,司机也想知道怎么安排行程最快。

2.资源分配

 资源分配就是为网络中的网线和结点寻找最近(这里的远近是按阻碍强度的大小来确定的)的中心(资源发散或汇集地)。例如,资源分配能为城市中的每一条街道上的学生确定最近的学校,为水库提供其供水区,等等。资源分配模拟资源是如何在中心(学校,消防站,水库等)和它周围的网线(街道,水路等)、结点(交叉路口,汽车中转站等)间的流动的。

资源分配根据中心容量以及网线和结点的需求将网线和结点分配给中心,分配是沿最佳路径进行的。当网络元素被分配给某个中心,该中心拥有的资源量就依据网络元素的需求而缩减,当中心的资源耗尽,分配就停止。

考虑这样一个问题:一所学校要依据就近入学的原则来决定应该接收附近那些街道上的学生。这时,可以将街道作为网线构成一个网络,将学校作为一个结点并将其指定为中心,以学校拥有的座位数作为此中心的资源容量,每条街道上的适龄儿童作为相应网线的需求,走过每条街道的时间作为网线的阻碍强度,如此资源分配功能就将从中心出发,依据阻碍强度由近及远地寻找周围的网线并把资源分配给它(也就是把学校的座位分配给相应街道上的儿童),直至被分配网线的需求总和达到学校的座位总数。

用户还可以通过赋给中心的阻碍限度来控制分配的范围。例如,如果限定儿童从学校走回家所需时间不能超过30分钟,就可以将这一时间作为学校对应的中心的阻碍限度,这样,当从中心延伸出去的路径的阻碍值到达这一限度时分配就将停止,即使中心资源尚有剩余。

确切地说,资源分配问题是要在m个候选点中选择P个供应点为n个需求点服务,使得为这几个需求点服务的总距离(或时间或费用)为最少。假设wi记为需求点i的需求量。Dij记为从候选点j到需求点i的距离,则P中心问题可叙为公式(8-19)。

         image0                                 (公式8-19)

并满足公式(8-20)

             image1 ,             i = 1, 2, …,n                  (公式8-20)

和公式(8-21)。

             image2 ,        P < m ≤ n        (公式8-21)

其中,aij是分配的指数。如果需求点i受供应点j的服务,则其值为1,否则为0。

image3                 image4                      (公式8-22)

上述两个约束条件是为了保证每个需求点仅受一个供应点服务,并且只有p个供应点。

3.连通分析

人们常常需要知道从某一结点或网线出发能够到达的全部结点或网线。例如,当地震发生时,救灾指挥部需要知道,把所有被破坏的公路和桥梁考虑在内,救灾物资能否从集散地出发送到每个居民点,如果有若干居民点与物资集散地不在一个连通分量之内,指挥部就不得不采用特殊的救援方式(如派遣直升机)。这一类问题称为连通分量求解。

另一连通分析问题是最少费用连通方案的求解问题,例如,公路部门拟修建足够数量的公路,使某个县的五个镇直接或间接地相互连结,如何使费用最少呢?如果把每一条可能修建的公路作为网线,把相应的预算费用作为网线的耗费,上述问题就转化为求一个网线集合,使全部结点连通且总耗费最少。

在实际应用中,常有类似在n个城市间建立通信线路这样的问题。这可用图来表示,图的顶点表示城市,边表示两城市间的线路,边上所赋的权值表示代价。对n个顶点的图可以建立许多生成树,每一棵树可以是一个通信网。若要使通信网的造价最低,就需要构造图的最小生成树(图8-29)。

生成树是图的极小连通子图。一个连通的赋权图G可能有很多的生成树。设T为图G的一个生成树,若把T中各边的权数相加,则这个和数称为生成树T的权数。在G的所有生成树中,权数最小的生成树称为G的最小生成树。

../_images/image0062.jpg

图8-29 最小生成树

构造最小生成树的依据有两条:

① 在网中选择n-1条边连接网的n个顶点o;

② 尽可能选取权值为最小的边。

下面介绍构造最小生成树的克罗斯克尔(Kruskal)算法。该算法是1956年提出的,俗称“避圈”法。设图G是由m个节点构成的连通赋权图,则构造最小生成树的步骤如下:

① 先把图G中的各边按权数从小到大重新排列,并取权数最小的一条边为T中的边。

② 在剩下的边中,按顺序取下一条边。若该边与T中已有的边构成回路,则舍去该边,

否则选进T中。

③ 重复②,直到有m-1条边被选进T中,这m-1条边就是G的最小生成树。

例:设有如图8―29(1)所示的图,图的每条边上标有权数。为了使权数的总和为最小,应该从权数最小的边选起。在此,选边(2,3);去掉该边后,在图中取权数最小的边,此时,可选(2,4)或(3,4),设取(2,4);去掉(2,4)边,下一条权数最小的边为(3,4),但使用边(3,4)后会出现回路,故不可取,应去掉边(3,4);下一条权数最小的边为(2,6);依上述方法重复,可形成图8-29(2)所示的最小生成树。如果前面不取(2,4),而取(3,4),则形成图8-29(3)所示的最小生成树。

4.流分析

所谓流,就是将资源由一个地点运送到另一个地点。流分析的问题主要是按照某种最优化标准(时间最少、费用最低、路程最短或运送量最大等)设计运送方案。

为了实施流分析,就要根据最优化标准的不同扩充网络模型。要把中心分为收货中心和发货中心,分别代表资源运送的起始点和目标点。这时发货中心的容量就代表待运送资源量,收货中心的容量代表它所需要的资源量。网线的相关数据也要扩充,如果最优化标准是运送量最大,就要设定网线的传输能力;如果目标是使费用最低,则要为网线设定传输费用(在该网线上运送一个单位的资源所需的费用)。

5.选址

选址功能涉及在某一指定区域内选择服务性设施的位置,例如市郊商店区、消防站、工厂、飞机场、仓库等的最佳位置的确定。在网络分析中的选址问题一般限定设施必须位于某个结点或位于某条网线上,或者限定在若干候选地点中选择位置。存在种类繁多的选址问题,实现方法和技巧也多种多样,不同GIS系统在这方面各有特色。造成这种多样性的原因主要在于:对“最佳位置”的解释(即用什么标准来衡量一个位置的优劣)以及要定位的是一个设施还是多个设施。

由于存在大量的各种各样的选址问题,所以有关文献中也有各种各样的选址问题的数学模型及求解方法。(边馥苓,2006)这里讨论的仅限于选址的范围是一个网络图,而且选址位置必须位于网络图的某一个或几个顶点上,亦可位于一条边的某一个位置上。选址问题又可以分为求网络图的中心点与中位点两类问题。

(1)中心点选址问题

中心点选址问题是使最佳选址位置所在的顶点与图中其他顶点之间的最大距离达到最 小。这类选址问题适宜于学校、医院、消防站点等一类服务设施的布局问题。例如,某镇要在其所辖的几个村之一修建一个初中,为这几个村服务,要求学校至最远村的距离达到最小。这类选址问题,实际上就是求网络图的中心点问题。其数学描述为:

设G=(V,E)(其中V={v1,v2,…,vn},E={e1,e2,….En})是一个无向简单连通赋权图,连接两个顶点的边的权值代表该两顶点之间的距离,对于每一个顶点vi,它与各顶点之间的最短路径长度为di1,di2,…,dim。这几个距离中的最大数称为顶点vi的最大服务距离,记为e(vi)。那么,中心点选址问题,就是求图G的中心点v-io使得

              e (vio) = min{e (vi)}

(2)中位点选址问题

中位点选址问题是使最佳选址位置所在的顶点到网络图中其他顶点的距离(亦可以是加权距离)总和达到最小。这类选址问题的数学描述为:

设G =(V,E)(其中V={v1,v2,…,vn},E={e1,e2,…,en})是一个简单连通赋权无向图,连接两个端点的边的权值为该两点之间的距离,对于每一个顶点vi(i=l,2,… n)。有一个正的负荷a(vi),而且它与其他各顶点之间的最短路径长度为di1,di2,…,dim,那么,中位点选址问题就是求图G中的中位点vio使得

              image5

例如某超市要确定一个配送中心,要使该中心到超市各分店的距离最短,这就是一个典型的中位点选址问题。

除以上所述之外,还有诸如关阀搜索、上下游追踪、空间排序、可访问性分析等网络分析功能,不一一赘述。