基于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．