王方雄 崔 羽

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

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

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

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

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

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

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

圖1 一個(gè)簡(jiǎn)單的管網(wǎng)實(shí)例（無向圖）

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

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

現(xiàn)有的管網(wǎng)系統(tǒng)大多數(shù)都是根據(jù)圖論廣序優(yōu)先遍歷搜索的原理，通過點(diǎn)擊圖面拾取或者按照名稱查找得到爆裂的管道，判斷管道兩頭的結(jié)點(diǎn)．若兩頭都是閥門（特殊情況），不需要進(jìn)行搜索，兩端閥門直接進(jìn)入初步關(guān)閥結(jié)果：若不是，則以非閥門端為圖的起點(diǎn)（兩端均為普通節(jié)點(diǎn)的任取一個(gè)），進(jìn)行圖的廣序遍歷搜索，計(jì)算生成初步關(guān)閥方案：（1）訪問相鄰結(jié)點(diǎn)，如果該結(jié)點(diǎn)未被訪問，則標(biāo)記為已讀．且如果是閥門或者水源，則分別加入初步關(guān)閥方案的相應(yīng)數(shù)組——水源數(shù)組或者閥門數(shù)組；（2）待與該起始點(diǎn)相鄰的所有結(jié)點(diǎn)訪問結(jié)束后，從隊(duì)列中取隊(duì)頭元素，開始新的一層搜索．依次類推．直到隊(duì)列為空時(shí)結(jié)束搜索，此時(shí)水源數(shù)組和閥門數(shù)組中的各個(gè)結(jié)點(diǎn)均為需要關(guān)閉的水源或者閥門．但是，有一些閥門處于可關(guān)可不關(guān)的狀態(tài)．事故發(fā)生后，如果對(duì)這一類閥門也進(jìn)行關(guān)閉，只是增加了成本，浪費(fèi)了人力，因此，需要對(duì)此算法進(jì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）來表達(dá)線性網(wǎng)絡(luò)系統(tǒng)［7－8］．邏輯網(wǎng)絡(luò)是由一系列的點(diǎn)和弧段連接組成，與幾何網(wǎng)絡(luò)不同的是邏輯網(wǎng)絡(luò)不包含坐標(biāo)值，其主要目的是用特定的屬性表存儲(chǔ)網(wǎng)絡(luò)的連通性信息．由于邏輯網(wǎng)絡(luò)中的邊線和交匯點(diǎn)沒有幾何屬性，所以它們不是要素（feature），而被稱為元素（elements）．在邏輯網(wǎng)絡(luò)中點(diǎn)和邊的拓?fù)潢P(guān)系用3個(gè)屬性表來描述：邊元素表、點(diǎn)元素表和連通性表．幾何網(wǎng)絡(luò)的網(wǎng)絡(luò)要素和邏輯網(wǎng)絡(luò)的元素間有一對(duì)一和一對(duì)多的關(guān)聯(lián)關(guān)系．一個(gè)幾何網(wǎng)絡(luò)總是關(guān)聯(lián)到一個(gè)邏輯網(wǎng)絡(luò)，當(dāng)編輯幾何網(wǎng)絡(luò)對(duì)象時(shí)，邏輯網(wǎng)絡(luò)中的要素將自動(dòng)更新．Geodatabase網(wǎng)絡(luò)模型有一個(gè)重要特性，它可以描述幾何網(wǎng)絡(luò)中資源（如水、氣）的流向．因此，采用Geodatabase網(wǎng)絡(luò)模型作為管網(wǎng)數(shù)據(jù)模型，可以實(shí)現(xiàn)一體化集成管理管網(wǎng)的空間數(shù)據(jù)、連通性數(shù)據(jù)及屬性數(shù)據(jù)等．利用Geodatabase網(wǎng)絡(luò)模型將管網(wǎng)中的閥門、資源供給點(diǎn)（如水廠、供熱站、供氣站等）等建模為幾何網(wǎng)絡(luò)的結(jié)點(diǎn)（junction）要素，將管線建模為幾何網(wǎng)絡(luò)的邊（edge）要素．而結(jié)點(diǎn)與邊的連通性用邏輯網(wǎng)絡(luò)的連接表（connectivity table）、節(jié)點(diǎn)元素表（junction element table）和邊元素表（edge element table）來準(zhǔn)確描述，見圖2．

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

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

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

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

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

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

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

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

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

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

4 應(yīng)用實(shí)例

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

5 結(jié)束語

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

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

［2］胡新玲，張宏飛．供水管網(wǎng)地理信息系統(tǒng)中爆管分析的算法研究［J］．測(cè)繪科學(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ù)浒l(fā)現(xiàn)算法及其自適應(yīng)研究［J］．武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2005，29（3）：481－484．

［6］殷劍宏，吳開亞．圖論及其算法［M］．合肥：中國(guó)科學(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．