基于GIS的管网爆管分析算法优化与实现＊

王方雄 崔 羽

（辽宁师范大学自然地理与空间信息科学辽宁省重点实验室1） 大连 116029）

（辽宁师范大学海洋经济与可持续发展研究中心2） 大连 116029）

（辽宁师范大学城市与环境学院3） 大连 116029）

城市地下管网是数字城市建设中的重要基础设施．由于管网绝大部分埋设在地下，管网压力的变动、材质的差异、铺设时间的不同等使得爆管事故屡有发生，这就要求爆管后能快速、准确地确定爆管地点、关阀方案以及影响范围，为管网管理部门提供科学合理的抢修方案．目前，许多城市已建立的城市地下管网地理信息系统中都不同程度地实现了爆管分析功能，大多存在以下问题：（1）关阀分析效率低，分析结果不一定最优［1－2］．多数管网系统仅使用单次广度优先遍历（breadth－first search，BFS）算法，简单地搜索最近阀门，未考虑到流向，而并未对某些必要阀门进行分析，结果导致最终关阀方案中数量冗余，生成结果不一定最优，一些无需关闭的阀门也被关闭了；（2）GIS管网分析接口多支持树状管网，而城市管网主管道的布设形式大多为环状（如城市供水管网），需要扩展基本的爆管分析功能，使其能对环状网进行最优爆管分析；（3）管网数据模型不够合理．多数系统是按管线、节点去组织数据，或者是根据水力分析需要建立逻辑网络模型，没有专门针对爆管分析而建立逻辑网络模型［3］，使搜索算法较为繁琐．

1 管网爆管分析算法与数据模型

1.1 广度优先遍历算法

广度优先遍历算法（BFS）［4－5］是目前管网爆管分析普遍采用的搜索算法．BFS是从结点集合V中一个指定结点V［i］开始访问，下一步访问所有与V［i］连接的未被访问的点 w1，w2，w3，w4，…，wt，再依次访问与w1，w2，w3，w4，…，wt相邻接未被访问的结点．依次类推，直到结点集合V中所有的点均被访问，整个图的遍历才算结束．如图1所示，其广度优先遍历顺序就是0，1，2，3，4，5，6．

图1 一个简单的管网实例（无向图）

图是一种非线性数据结构［6］，其内部各结点之间都有可能存在关系，这种复杂关系可以有多种存储方法，常用邻接矩阵来存储．图l中的管网实例数据，可以用一个一维数组V［7］来存储结点（vertex），图内点间的关系用一个二维数组A（i，j）来存储，即邻接矩阵．在邻接矩阵中，i，j表示顶点序号，A（i，j）的值k表示顶点之间的邻接关系．针对图1中顶点之间的关系可以用如下邻接矩阵表示．邻接表取值为：k＝A（i，j）＝0，表示顶点间不邻接；k＝A（i，j）＝1，表示顶点间相邻接．

管网结点的邻接矩阵如下．

现有的管网系统大多数都是根据图论广序优先遍历搜索的原理，通过点击图面拾取或者按照名称查找得到爆裂的管道，判断管道两头的结点．若两头都是阀门（特殊情况），不需要进行搜索，两端阀门直接进入初步关阀结果：若不是，则以非阀门端为图的起点（两端均为普通节点的任取一个），进行图的广序遍历搜索，计算生成初步关阀方案：（1）访问相邻结点，如果该结点未被访问，则标记为已读．且如果是阀门或者水源，则分别加入初步关阀方案的相应数组——水源数组或者阀门数组；（2）待与该起始点相邻的所有结点访问结束后，从队列中取队头元素，开始新的一层搜索．依次类推．直到队列为空时结束搜索，此时水源数组和阀门数组中的各个结点均为需要关闭的水源或者阀门．但是，有一些阀门处于可关可不关的状态．事故发生后，如果对这一类阀门也进行关闭，只是增加了成本，浪费了人力，因此，需要对此算法进行优化，得到正确关闭的阀门．

1.2 管网数据模型

ArcGIS Geodatabase数据库采用几何网络模型（geometric network）和逻辑网络模型（logical network）来表达线性网络系统［7－8］．逻辑网络是由一系列的点和弧段连接组成，与几何网络不同的是逻辑网络不包含坐标值，其主要目的是用特定的属性表存储网络的连通性信息．由于逻辑网络中的边线和交汇点没有几何属性，所以它们不是要素（feature），而被称为元素（elements）．在逻辑网络中点和边的拓扑关系用3个属性表来描述：边元素表、点元素表和连通性表．几何网络的网络要素和逻辑网络的元素间有一对一和一对多的关联关系．一个几何网络总是关联到一个逻辑网络，当编辑几何网络对象时，逻辑网络中的要素将自动更新．Geodatabase网络模型有一个重要特性，它可以描述几何网络中资源（如水、气）的流向．因此，采用Geodatabase网络模型作为管网数据模型，可以实现一体化集成管理管网的空间数据、连通性数据及属性数据等．利用Geodatabase网络模型将管网中的阀门、资源供给点（如水厂、供热站、供气站等）等建模为几何网络的结点（junction）要素，将管线建模为几何网络的边（edge）要素．而结点与边的连通性用逻辑网络的连接表（connectivity table）、节点元素表（junction element table）和边元素表（edge element table）来准确描述，见图2．

图2 Geodatabase网络数据模型

几何网络中，结点要素要设置一个名为AncillaryRole的属性（在建立网络模型时，自动生成），该属性有3个值：None，Source和Sink．其中Source和Sink是指网络中流的源点和流的终止点，从未在网络中生成流向．进行爆管分析时，将管网中资源供给点（如水厂、供热站、供气站等）设置为源点（source），资源使用点（如用户阀门）设置为终止点（sink），然后使用ArcEngine函数接口（IUtilityNetworkGEN）生成流向．在Geodatabase网络模型中可形成3种流向：determinate flow（已知流向），indeterminate flow（未知流向）和uninitialized（未初始化流向）．在一个源点（source）的情况下，树状网络结构将全部生成已知流向；环状结构则部分生成已知流向，部分生成未知流向，而与源点不相连的部分则生成未初始化流向．对于有多个源点的情况下，则大部分主干网络都生成未知流向，见图3．

图3 管网的网络流向

2 爆管分析算法优化

在一个源点的情况下，树状网络结构将全部生成已知流向；环状结构则部分生成已知流向，部分生成未知流向，而与源点不相连的部分则生成未初始化流向．对于有多个源点的情况下，则大部分主干网络都生成未知流向．根据Geodatabase网络模型可以看出，在只有一个源点且网络成树状的情况下才能生成已知流向，才能直接使用ArcEngine所提供的管网分析接口ITraceFlow－SolverGEN去寻找上游最近可关闭的阀门，而城市管网一般为环状且有多个源点，如果只使用该接口将很难对环状网实现最优的爆管分析．目前，支持管网流向分析的GIS平台（如ArcGIS）都只提供了支持树状管网分析的接口（如ArcEngine的ITraceFlowSolverGEN），难以直接有效地解决环状管网的爆管分析功能．

传统广度遍历算法BFS中，只考虑了网络中边和结点的连通性，没有考虑边上的资源流向，所以在搜索时，只能机械地在爆管发生处向两边搜索最近的阀门，致使下游不需要关闭的阀门被关闭，从而不能进行正确的影响区域分析．因此，采用Geodatabase网络模型一方面有效地解决管网数据的集成存储管理，另一方面利用该模型的网络拓扑结构及资源流向优化传统广度优先算法，并利用ArcEngine的网络模型接口实现该优化算法，完成上游最近阀门的搜索．算法优化的结构流程为：（1）建立阀门数组（V＿array）、节点队列 N＿queue和有效边集合E＿set；（2）把所有与爆管点相交的有效边加入到E＿set；（3）从E＿set中取出一条边，判断其流向，将该边的上游节点N1加入到队列N＿queue；并做判断，若N1为有效阀门点则将N1加入阀门数组（V＿array），否则将所有与N1相交的有效边加入到E＿set中；（4）重复第（3）步，直到Edges为空为止．

Geodatabase网络模型中，边元素上的流向是利用边元素两端点的方向性来判断的．如果流向是从边的起点到终点，流向即为esriFDWith－Flow（顺向流），反之则为esriFDAgainstFlow（逆向流）．因此，在搜索流向的上游方向时，首先判断P1点是边的起点还是终点，然后结合边的流向判断P2点是否为该边的上游流向点，如此便可正确搜索到上游最近的阀门．对于流向为未知流向或无流向的边元素则不做以上的判断，直接按BFS算法搜索．

3 爆管分析算法实现

ArcEngine是美国ESRI公司推出的由一套核心ArcObjects组件组成并用于构建制定应用程序的嵌入式GIS组件库．可以利用ArcEngine的ITraceFlow－SolverGEN接口与支持Geodatabase的访问接口INetTopology（实现网络的拓扑功能）、INetAttributes（查看网络元素的有效性）和IUtilityNetworkGEN（在网络中生成流和提取元素的流向）等来实现BFS优化算法的爆管分析功能．

爆管可分为两类：边上爆管和点上爆管，爆管的位置可利用INetFlag接口来设置标记（flag）．对于边上爆管，可直接设置边标记（EdgeFlag），然后判断边上的流向，根据不同的流向决定阀门搜索的方向，具体分3种情形：已知流则用上游点进行阀门搜索；未知流则分别用2个端点进行阀门搜索；未初始化流则不搜索．对于点上爆管，则直接用该点进行阀门搜索，即先判断点是否为阀门类型，若是则应先设置此阀门为无效阀门再进行搜索．搜索到可关闭的阀门后，将这些阀门设置为无效（使用INetworkFeature接口）；再用ITrace－FlowSolver接口中的FindFlowElements函数查找与爆管地点相连通的区域，即为爆管的影响区域；最后还原阀门的有效性，恢复网络模型的初始状态．在进行阀门搜索前，应注意网络模型中的源点和流向的设置问题．首先搜索与爆管地点相连的源点，并生成网络流向（使用IUtilityNetworkGEN函数接口）．

4 应用实例

大连石化矿区管网综合管理系统的管网矢量数据、连通性数据及管网属性数据采用Geodatabase数据库存储管理，DEM及遥感影像数据与三维模型数据分别采用．tif与．skp文件形式存储．软件系统基于ArcEngine／C＃开发，三维场景浏览与管网爆管分析结果显示采用SceneControl控件，图层的控制和管理采用TOCControl控件，三维场景的放大、缩小、漫游等基本浏览功能采用Toolbar－Control控件实现．基于BFS优化算法实现的爆管分析功能主要在二维场景中完成，爆管分析结果的显示实现了二维、三维场景的联动．另外，基于Geodatabase网络模型系统还实现了爆管影响分析、管网剖面分析、管网联通分析等管网分析功能．

5 结束语

本文采用Geodatabase网络模型建模并一体化存储管网数据，在管网数据模型中明确表达网络流向，并利用ArcEngine的Geodatabase网络访问接口扩展优化广度优先遍历算法，实现了支持环状管网的爆管分析功能，很好地解决了爆管分析中上游可关闭阀门的搜索和爆管的影响区域分析等问题，已在大连石化矿区综合管理系统中得到了很好的应用．该算法优化方案目前没有考虑管网的压力传递问题，将会进一步探索管网压强平差计算的爆管分析方案．

［1］刘建川，李永树，蔡国林．基于ArcGIS管网爆管分析的算法优化与实现［J］．测绘科学，2008，33（1）：215－217．

［2］胡新玲，张宏飞．供水管网地理信息系统中爆管分析的算法研究［J］．测绘科学，2008，33（4）：225－226．

［3］Cooper N R，Blakey G，Sherwin C，et al．The use of GIS to develop aprobability－based trunk mains burst risk model［J］．Urban Water，2000（2）：97－103．

［4］王杉杉，骆旭佳，高 飞，等．基于GIS的多水源环状管网爆管分析的算法［J］．水科学与工程技术，2010（4）：43－46．

［5］李元臣，刘维群，徐凯声．一种基于广度优先遍历的网络拓扑发现算法及其自适应研究［J］．武汉理工大学学报：交通科学与工程版，2005，29（3）：481－484．

［6］殷剑宏，吴开亚．图论及其算法［M］．合肥：中国科学技术大学出版社，2003．

［7］Zeiler M．Modeling our world：the ESRI guide to geodatabase design［M］．Kapiolani：ESRI Press，1999．

［8］ESRI．Building a Geodatabase［M］．Kapiolani：ESRI Press，2004．