基于GIS的管網(wǎng)爆管分析算法優(yōu)化與實現(xiàn)＊

王方雄 崔 羽

（遼寧師范大學(xué)自然地理與空間信息科學(xué)遼寧省重點實驗室1） 大連 116029）

（遼寧師范大學(xué)海洋經(jīng)濟與可持續(xù)發(fā)展研究中心2） 大連 116029）

（遼寧師范大學(xué)城市與環(huán)境學(xué)院3） 大連 116029）

城市地下管網(wǎng)是數(shù)字城市建設(shè)中的重要基礎(chǔ)設(shè)施．由于管網(wǎng)絕大部分埋設(shè)在地下，管網(wǎng)壓力的變動、材質(zhì)的差異、鋪設(shè)時間的不同等使得爆管事故屢有發(fā)生，這就要求爆管后能快速、準確地確定爆管地點、關(guān)閥方案以及影響范圍，為管網(wǎng)管理部門提供科學(xué)合理的搶修方案．目前，許多城市已建立的城市地下管網(wǎng)地理信息系統(tǒng)中都不同程度地實現(xiàn)了爆管分析功能，大多存在以下問題：（1）關(guān)閥分析效率低，分析結(jié)果不一定最優(yōu)［1－2］．多數(shù)管網(wǎng)系統(tǒng)僅使用單次廣度優(yōu)先遍歷（breadth－first search，BFS）算法，簡單地搜索最近閥門，未考慮到流向，而并未對某些必要閥門進行分析，結(jié)果導(dǎo)致最終關(guān)閥方案中數(shù)量冗余，生成結(jié)果不一定最優(yōu)，一些無需關(guān)閉的閥門也被關(guān)閉了；（2）GIS管網(wǎng)分析接口多支持樹狀管網(wǎng)，而城市管網(wǎng)主管道的布設(shè)形式大多為環(huán)狀（如城市供水管網(wǎng)），需要擴展基本的爆管分析功能，使其能對環(huán)狀網(wǎng)進行最優(yōu)爆管分析；（3）管網(wǎng)數(shù)據(jù)模型不夠合理．多數(shù)系統(tǒng)是按管線、節(jié)點去組織數(shù)據(jù)，或者是根據(jù)水力分析需要建立邏輯網(wǎng)絡(luò)模型，沒有專門針對爆管分析而建立邏輯網(wǎng)絡(luò)模型［3］，使搜索算法較為繁瑣．

1 管網(wǎng)爆管分析算法與數(shù)據(jù)模型

1.1 廣度優(yōu)先遍歷算法

廣度優(yōu)先遍歷算法（BFS）［4－5］是目前管網(wǎng)爆管分析普遍采用的搜索算法．BFS是從結(jié)點集合V中一個指定結(jié)點V［i］開始訪問，下一步訪問所有與V［i］連接的未被訪問的點 w1，w2，w3，w4，…，wt，再依次訪問與w1，w2，w3，w4，…，wt相鄰接未被訪問的結(jié)點．依次類推，直到結(jié)點集合V中所有的點均被訪問，整個圖的遍歷才算結(jié)束．如圖1所示，其廣度優(yōu)先遍歷順序就是0，1，2，3，4，5，6．

圖1 一個簡單的管網(wǎng)實例（無向圖）

圖是一種非線性數(shù)據(jù)結(jié)構(gòu)［6］，其內(nèi)部各結(jié)點之間都有可能存在關(guān)系，這種復(fù)雜關(guān)系可以有多種存儲方法，常用鄰接矩陣來存儲．圖l中的管網(wǎng)實例數(shù)據(jù)，可以用一個一維數(shù)組V［7］來存儲結(jié)點（vertex），圖內(nèi)點間的關(guān)系用一個二維數(shù)組A（i，j）來存儲，即鄰接矩陣．在鄰接矩陣中，i，j表示頂點序號，A（i，j）的值k表示頂點之間的鄰接關(guān)系．針對圖1中頂點之間的關(guān)系可以用如下鄰接矩陣表示．鄰接表取值為：k＝A（i，j）＝0，表示頂點間不鄰接；k＝A（i，j）＝1，表示頂點間相鄰接．

管網(wǎng)結(jié)點的鄰接矩陣如下．

現(xiàn)有的管網(wǎng)系統(tǒng)大多數(shù)都是根據(jù)圖論廣序優(yōu)先遍歷搜索的原理，通過點擊圖面拾取或者按照名稱查找得到爆裂的管道，判斷管道兩頭的結(jié)點．若兩頭都是閥門（特殊情況），不需要進行搜索，兩端閥門直接進入初步關(guān)閥結(jié)果：若不是，則以非閥門端為圖的起點（兩端均為普通節(jié)點的任取一個），進行圖的廣序遍歷搜索，計算生成初步關(guān)閥方案：（1）訪問相鄰結(jié)點，如果該結(jié)點未被訪問，則標記為已讀．且如果是閥門或者水源，則分別加入初步關(guān)閥方案的相應(yīng)數(shù)組——水源數(shù)組或者閥門數(shù)組；（2）待與該起始點相鄰的所有結(jié)點訪問結(jié)束后，從隊列中取隊頭元素，開始新的一層搜索．依次類推．直到隊列為空時結(jié)束搜索，此時水源數(shù)組和閥門數(shù)組中的各個結(jié)點均為需要關(guān)閉的水源或者閥門．但是，有一些閥門處于可關(guān)可不關(guān)的狀態(tài)．事故發(fā)生后，如果對這一類閥門也進行關(guān)閉，只是增加了成本，浪費了人力，因此，需要對此算法進行優(yōu)化，得到正確關(guān)閉的閥門．

1.2 管網(wǎng)數(shù)據(jù)模型

ArcGIS Geodatabase數(shù)據(jù)庫采用幾何網(wǎng)絡(luò)模型（geometric network）和邏輯網(wǎng)絡(luò)模型（logical network）來表達線性網(wǎng)絡(luò)系統(tǒng)［7－8］．邏輯網(wǎng)絡(luò)是由一系列的點和弧段連接組成，與幾何網(wǎng)絡(luò)不同的是邏輯網(wǎng)絡(luò)不包含坐標值，其主要目的是用特定的屬性表存儲網(wǎng)絡(luò)的連通性信息．由于邏輯網(wǎng)絡(luò)中的邊線和交匯點沒有幾何屬性，所以它們不是要素（feature），而被稱為元素（elements）．在邏輯網(wǎng)絡(luò)中點和邊的拓撲關(guān)系用3個屬性表來描述：邊元素表、點元素表和連通性表．幾何網(wǎng)絡(luò)的網(wǎng)絡(luò)要素和邏輯網(wǎng)絡(luò)的元素間有一對一和一對多的關(guān)聯(lián)關(guān)系．一個幾何網(wǎng)絡(luò)總是關(guān)聯(lián)到一個邏輯網(wǎng)絡(luò)，當編輯幾何網(wǎng)絡(luò)對象時，邏輯網(wǎng)絡(luò)中的要素將自動更新．Geodatabase網(wǎng)絡(luò)模型有一個重要特性，它可以描述幾何網(wǎng)絡(luò)中資源（如水、氣）的流向．因此，采用Geodatabase網(wǎng)絡(luò)模型作為管網(wǎng)數(shù)據(jù)模型，可以實現(xiàn)一體化集成管理管網(wǎng)的空間數(shù)據(jù)、連通性數(shù)據(jù)及屬性數(shù)據(jù)等．利用Geodatabase網(wǎng)絡(luò)模型將管網(wǎng)中的閥門、資源供給點（如水廠、供熱站、供氣站等）等建模為幾何網(wǎng)絡(luò)的結(jié)點（junction）要素，將管線建模為幾何網(wǎng)絡(luò)的邊（edge）要素．而結(jié)點與邊的連通性用邏輯網(wǎng)絡(luò)的連接表（connectivity table）、節(jié)點元素表（junction element table）和邊元素表（edge element table）來準確描述，見圖2．

圖2 Geodatabase網(wǎng)絡(luò)數(shù)據(jù)模型

幾何網(wǎng)絡(luò)中，結(jié)點要素要設(shè)置一個名為AncillaryRole的屬性（在建立網(wǎng)絡(luò)模型時，自動生成），該屬性有3個值：None，Source和Sink．其中Source和Sink是指網(wǎng)絡(luò)中流的源點和流的終止點，從未在網(wǎng)絡(luò)中生成流向．進行爆管分析時，將管網(wǎng)中資源供給點（如水廠、供熱站、供氣站等）設(shè)置為源點（source），資源使用點（如用戶閥門）設(shè)置為終止點（sink），然后使用ArcEngine函數(shù)接口（IUtilityNetworkGEN）生成流向．在Geodatabase網(wǎng)絡(luò)模型中可形成3種流向：determinate flow（已知流向），indeterminate flow（未知流向）和uninitialized（未初始化流向）．在一個源點（source）的情況下，樹狀網(wǎng)絡(luò)結(jié)構(gòu)將全部生成已知流向；環(huán)狀結(jié)構(gòu)則部分生成已知流向，部分生成未知流向，而與源點不相連的部分則生成未初始化流向．對于有多個源點的情況下，則大部分主干網(wǎng)絡(luò)都生成未知流向，見圖3．

圖3 管網(wǎng)的網(wǎng)絡(luò)流向

2 爆管分析算法優(yōu)化

在一個源點的情況下，樹狀網(wǎng)絡(luò)結(jié)構(gòu)將全部生成已知流向；環(huán)狀結(jié)構(gòu)則部分生成已知流向，部分生成未知流向，而與源點不相連的部分則生成未初始化流向．對于有多個源點的情況下，則大部分主干網(wǎng)絡(luò)都生成未知流向．根據(jù)Geodatabase網(wǎng)絡(luò)模型可以看出，在只有一個源點且網(wǎng)絡(luò)成樹狀的情況下才能生成已知流向，才能直接使用ArcEngine所提供的管網(wǎng)分析接口ITraceFlow－SolverGEN去尋找上游最近可關(guān)閉的閥門，而城市管網(wǎng)一般為環(huán)狀且有多個源點，如果只使用該接口將很難對環(huán)狀網(wǎng)實現(xiàn)最優(yōu)的爆管分析．目前，支持管網(wǎng)流向分析的GIS平臺（如ArcGIS）都只提供了支持樹狀管網(wǎng)分析的接口（如ArcEngine的ITraceFlowSolverGEN），難以直接有效地解決環(huán)狀管網(wǎng)的爆管分析功能．

傳統(tǒng)廣度遍歷算法BFS中，只考慮了網(wǎng)絡(luò)中邊和結(jié)點的連通性，沒有考慮邊上的資源流向，所以在搜索時，只能機械地在爆管發(fā)生處向兩邊搜索最近的閥門，致使下游不需要關(guān)閉的閥門被關(guān)閉，從而不能進行正確的影響區(qū)域分析．因此，采用Geodatabase網(wǎng)絡(luò)模型一方面有效地解決管網(wǎng)數(shù)據(jù)的集成存儲管理，另一方面利用該模型的網(wǎng)絡(luò)拓撲結(jié)構(gòu)及資源流向優(yōu)化傳統(tǒng)廣度優(yōu)先算法，并利用ArcEngine的網(wǎng)絡(luò)模型接口實現(xiàn)該優(yōu)化算法，完成上游最近閥門的搜索．算法優(yōu)化的結(jié)構(gòu)流程為：（1）建立閥門數(shù)組（V＿array）、節(jié)點隊列 N＿queue和有效邊集合E＿set；（2）把所有與爆管點相交的有效邊加入到E＿set；（3）從E＿set中取出一條邊，判斷其流向，將該邊的上游節(jié)點N1加入到隊列N＿queue；并做判斷，若N1為有效閥門點則將N1加入閥門數(shù)組（V＿array），否則將所有與N1相交的有效邊加入到E＿set中；（4）重復(fù)第（3）步，直到Edges為空為止．

Geodatabase網(wǎng)絡(luò)模型中，邊元素上的流向是利用邊元素兩端點的方向性來判斷的．如果流向是從邊的起點到終點，流向即為esriFDWith－Flow（順向流），反之則為esriFDAgainstFlow（逆向流）．因此，在搜索流向的上游方向時，首先判斷P1點是邊的起點還是終點，然后結(jié)合邊的流向判斷P2點是否為該邊的上游流向點，如此便可正確搜索到上游最近的閥門．對于流向為未知流向或無流向的邊元素則不做以上的判斷，直接按BFS算法搜索．

3 爆管分析算法實現(xiàn)

ArcEngine是美國ESRI公司推出的由一套核心ArcObjects組件組成并用于構(gòu)建制定應(yīng)用程序的嵌入式GIS組件庫．可以利用ArcEngine的ITraceFlow－SolverGEN接口與支持Geodatabase的訪問接口INetTopology（實現(xiàn)網(wǎng)絡(luò)的拓撲功能）、INetAttributes（查看網(wǎng)絡(luò)元素的有效性）和IUtilityNetworkGEN（在網(wǎng)絡(luò)中生成流和提取元素的流向）等來實現(xiàn)BFS優(yōu)化算法的爆管分析功能．

爆管可分為兩類：邊上爆管和點上爆管，爆管的位置可利用INetFlag接口來設(shè)置標記（flag）．對于邊上爆管，可直接設(shè)置邊標記（EdgeFlag），然后判斷邊上的流向，根據(jù)不同的流向決定閥門搜索的方向，具體分3種情形：已知流則用上游點進行閥門搜索；未知流則分別用2個端點進行閥門搜索；未初始化流則不搜索．對于點上爆管，則直接用該點進行閥門搜索，即先判斷點是否為閥門類型，若是則應(yīng)先設(shè)置此閥門為無效閥門再進行搜索．搜索到可關(guān)閉的閥門后，將這些閥門設(shè)置為無效（使用INetworkFeature接口）；再用ITrace－FlowSolver接口中的FindFlowElements函數(shù)查找與爆管地點相連通的區(qū)域，即為爆管的影響區(qū)域；最后還原閥門的有效性，恢復(fù)網(wǎng)絡(luò)模型的初始狀態(tài)．在進行閥門搜索前，應(yīng)注意網(wǎng)絡(luò)模型中的源點和流向的設(shè)置問題．首先搜索與爆管地點相連的源點，并生成網(wǎng)絡(luò)流向（使用IUtilityNetworkGEN函數(shù)接口）．

4 應(yīng)用實例

大連石化礦區(qū)管網(wǎng)綜合管理系統(tǒng)的管網(wǎng)矢量數(shù)據(jù)、連通性數(shù)據(jù)及管網(wǎng)屬性數(shù)據(jù)采用Geodatabase數(shù)據(jù)庫存儲管理，DEM及遙感影像數(shù)據(jù)與三維模型數(shù)據(jù)分別采用．tif與．skp文件形式存儲．軟件系統(tǒng)基于ArcEngine／C＃開發(fā)，三維場景瀏覽與管網(wǎng)爆管分析結(jié)果顯示采用SceneControl控件，圖層的控制和管理采用TOCControl控件，三維場景的放大、縮小、漫游等基本瀏覽功能采用Toolbar－Control控件實現(xiàn)．基于BFS優(yōu)化算法實現(xiàn)的爆管分析功能主要在二維場景中完成，爆管分析結(jié)果的顯示實現(xiàn)了二維、三維場景的聯(lián)動．另外，基于Geodatabase網(wǎng)絡(luò)模型系統(tǒng)還實現(xiàn)了爆管影響分析、管網(wǎng)剖面分析、管網(wǎng)聯(lián)通分析等管網(wǎng)分析功能．

5 結(jié)束語

本文采用Geodatabase網(wǎng)絡(luò)模型建模并一體化存儲管網(wǎng)數(shù)據(jù)，在管網(wǎng)數(shù)據(jù)模型中明確表達網(wǎng)絡(luò)流向，并利用ArcEngine的Geodatabase網(wǎng)絡(luò)訪問接口擴展優(yōu)化廣度優(yōu)先遍歷算法，實現(xiàn)了支持環(huán)狀管網(wǎng)的爆管分析功能，很好地解決了爆管分析中上游可關(guān)閉閥門的搜索和爆管的影響區(qū)域分析等問題，已在大連石化礦區(qū)綜合管理系統(tǒng)中得到了很好的應(yīng)用．該算法優(yōu)化方案目前沒有考慮管網(wǎng)的壓力傳遞問題，將會進一步探索管網(wǎng)壓強平差計算的爆管分析方案．

［1］劉建川，李永樹，蔡國林．基于ArcGIS管網(wǎng)爆管分析的算法優(yōu)化與實現(xiàn)［J］．測繪科學(xué)，2008，33（1）：215－217．

［2］胡新玲，張宏飛．供水管網(wǎng)地理信息系統(tǒng)中爆管分析的算法研究［J］．測繪科學(xué)，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的多水源環(huán)狀管網(wǎng)爆管分析的算法［J］．水科學(xué)與工程技術(shù)，2010（4）：43－46．

［5］李元臣，劉維群，徐凱聲．一種基于廣度優(yōu)先遍歷的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)算法及其自適應(yīng)研究［J］．武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，2005，29（3）：481－484．

［6］殷劍宏，吳開亞．圖論及其算法［M］．合肥：中國科學(xué)技術(shù)大學(xué)出版社，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．