譜聚類在給水管網(wǎng)分區(qū)優(yōu)化中的應(yīng)用

劉俊　周鵬

摘要：

利用圖劃分技術(shù)和圖論算法實現(xiàn)給水管網(wǎng)分區(qū)。根據(jù)給水管網(wǎng)分析，確定分區(qū)數(shù)量，建立權(quán)重鄰接矩陣并計算圖拉普拉斯矩陣及其特征向量，通過多路圖劃分對隱藏在特征向量中的聚類信息進(jìn)行數(shù)據(jù)挖掘，采用遺傳算法和K均值方法實現(xiàn)最佳節(jié)點(diǎn)聚類。利用PageRank和最短路徑算法確定水表和閥門位置，最終實現(xiàn)給水管網(wǎng)優(yōu)化分區(qū)。實際給水管網(wǎng)模型分區(qū)實例表明所提方法在給水管網(wǎng)分區(qū)的有效性。

關(guān)鍵詞：

給水管網(wǎng)；分區(qū)；聚類；優(yōu)化

中圖分類號：TU991

文獻(xiàn)標(biāo)志碼：A文章編號：16744764（2016）06014206

Abstract：

Design of district metered areas（DMAs） in water distribution system was performed based on complex network spectral clustering and graph theory. First the number of DMAs was determined， and graph weighted adjacency matrix and Laplacian matrix were established. Then kway spectral clustering algorithm was used to discover the optimal clusters hidden behind eigenvectors of Laplacian matrix， leading to the best layout of DMAs using genetic algorithm and Kmeans. PageRank and shortest path algorithm were adopted to ascertain the location of meters in DMAs and valves between DMAs to achieve the optimal design of DMAs eventually. And a real water distribution system was tested and the results showed that the proposed method was effective in DMAs design.

Keywords：

water distribution systems；district metered area； clustering； optimization

給水管網(wǎng)分區(qū)是在系統(tǒng)性能影響最小的情況下通過安裝閥門、水表形成獨(dú)立供水區(qū)域，便于優(yōu)化調(diào)度、漏損控制等各方面的管理，以適應(yīng)信息化、智能化、精細(xì)化的要求[15]。管網(wǎng)分區(qū)目的是獲得規(guī)模均等，壓力、水質(zhì)均衡的分區(qū)。由于管網(wǎng)的高度復(fù)雜性以及眾多技術(shù)要求和制約因素，使得分區(qū)這一問題面臨較大挑戰(zhàn)。

目前，管網(wǎng)分區(qū)優(yōu)化方法主要有圖論算法和復(fù)雜網(wǎng)絡(luò)聚類算法。圖論分區(qū)算法主要使用搜索算法獲得管網(wǎng)拓?fù)浣Y(jié)構(gòu)。其中，廣度優(yōu)先搜索算法在DMA規(guī)模約束下，搜索與某一節(jié)點(diǎn)路徑最短的節(jié)點(diǎn)集，當(dāng)滿足設(shè)定規(guī)模時，搜索終止，則可得到滿足要求的分區(qū)。這類方法可獲得各種分區(qū)方案供決策者選定[6]，或者通過模型分析獲得水力最優(yōu)方案[7]。相比于廣度優(yōu)先搜索算法的局部搜索，深度優(yōu)先搜索算法可從整體上獲得給水管網(wǎng)樹狀結(jié)構(gòu)，并通過優(yōu)化算法獲得減壓閥最佳位置，進(jìn)而實現(xiàn)分區(qū)[8]，或者確定各水源供水范圍[9]。另外，也可以最短路徑算法為基礎(chǔ)，通過壓力均衡性確定分區(qū)[10]，或者通過管道介數(shù)中心性選定閥門、水表位置，以實現(xiàn)分區(qū)[11]。

在復(fù)雜網(wǎng)絡(luò)聚類中，同一聚類內(nèi)節(jié)點(diǎn)連接緊密，而不同聚類間節(jié)點(diǎn)連接相對稀疏，這與管網(wǎng)分區(qū)的內(nèi)在要求一致。相應(yīng)聚類算法包括計算機(jī)科學(xué)中的圖劃分和社會學(xué)中的社團(tuán)發(fā)現(xiàn)。圖劃分將復(fù)雜網(wǎng)絡(luò)聚類轉(zhuǎn)換為優(yōu)化問題，如Nardo等[12]人使用多層次遞歸二分法自動獲得規(guī)模均等的分區(qū)布局。社團(tuán)發(fā)現(xiàn)則將分區(qū)問題轉(zhuǎn)換為模塊度等啟發(fā)式規(guī)則的設(shè)計問題，其中刁克功等[13]在管網(wǎng)分區(qū)中首次引入社區(qū)發(fā)現(xiàn)貪心算法進(jìn)行給水管網(wǎng)分區(qū)。Giustolisi等[14]引入管道權(quán)重提出了給水管網(wǎng)設(shè)施模塊度，可以發(fā)現(xiàn)更小規(guī)模的結(jié)構(gòu)。另外，也有其他相似度的度量方式用于給水管網(wǎng)分區(qū)，如按照節(jié)點(diǎn)位置信息采用K均值聚類，以此為基礎(chǔ)形成供水管網(wǎng)規(guī)劃方案[15]，或者按照節(jié)點(diǎn)水壓波動相似性分區(qū)，確定最優(yōu)壓力監(jiān)測點(diǎn)[16]。

筆者提出一種基于復(fù)雜網(wǎng)絡(luò)譜聚類和圖論算法的給水管網(wǎng)分區(qū)方法。目的是在盡量降低分區(qū)不利影響的前提下，根據(jù)給水管網(wǎng)拓?fù)浣Y(jié)構(gòu)，利用數(shù)據(jù)挖掘發(fā)現(xiàn)隱含在其中的結(jié)構(gòu)聚類信息，確定節(jié)點(diǎn)聚類，繼而實現(xiàn)滿足要求的分區(qū)。

1給水管網(wǎng)分區(qū)方法

所提出的分區(qū)流程主要包含3個部分：

1）數(shù)據(jù)輸入：管網(wǎng)分析與模擬，確定分區(qū)數(shù)量，建立權(quán)重矩陣。

2）實現(xiàn)分區(qū)：圖拉普拉斯矩陣求解，根據(jù)第二特征向量，采用多路圖劃分確定各分區(qū)內(nèi)節(jié)點(diǎn)聚類，即確定分區(qū)范圍。

3）確定閥門、水表位置：PageRank算法確定每個分區(qū)中心節(jié)點(diǎn)，水源到該節(jié)點(diǎn)的最短路徑中確定水表位置，其他分區(qū)間連接管道則為閥門位置。

1.1給水管網(wǎng)分區(qū)數(shù)量的確定

給水管網(wǎng)分區(qū)數(shù)量需要根據(jù)分區(qū)目的、系統(tǒng)規(guī)模、分區(qū)大小、成本等綜合確定。本方法旨在通過發(fā)現(xiàn)給水管網(wǎng)內(nèi)在聚類結(jié)構(gòu)，實現(xiàn)分區(qū)設(shè)計，因此，在獲得指定數(shù)量的分區(qū)時，每個分區(qū)的規(guī)模不是嚴(yán)格相同。

1.2規(guī)范化拉普拉斯矩陣

給水管網(wǎng)可抽象為一個由點(diǎn)集V和邊集E組成的管網(wǎng)圖G =（V，E），節(jié)點(diǎn)數(shù)記為n=V，邊數(shù)記為m=E。給水管網(wǎng)節(jié)點(diǎn)間連接管道的屬性，如管道的流量、管徑等含有重要信息，使用管道權(quán)重能更好地反映節(jié)點(diǎn)間連接關(guān)系。因此，給水管網(wǎng)圖的權(quán)重鄰接矩陣A可表示為endprint

Aij=wij，節(jié)點(diǎn)i與j有邊0，其他 （1）

復(fù)雜網(wǎng)絡(luò)分析中將與節(jié)點(diǎn)i直接相連的邊權(quán)重之和稱為度，表示為ki，可用鄰接矩陣表示為ki=nj=1wij，則對角矩陣D為

D=k100…0k20…00k3…（2）

圖的拉普拉斯矩陣為L=D-A，其元素Lij表示為

Lij=ki，如果i=j-wij，如果i≠j且有一條邊0，其他 （3）

矩陣L的所有特征值稱為圖G的拉普拉斯譜，最小特征值λ1對應(yīng)的特征向量稱為第一特征向量，不包含任何聚類信息，所需要的聚類信息存在于其他的特征向量，稱為第二特征向量。

傳統(tǒng)圖劃分最小割算法以最小化割邊為目標(biāo)，這可能導(dǎo)致分區(qū)時規(guī)模的不均衡。為此采用規(guī)范化割集準(zhǔn)則，規(guī)范化拉普拉斯矩陣為

Lsym=D-12LD-12=I-D-12AD-12=I-E（4）

譜平分法利用第二小特征值對應(yīng)的特征向量實現(xiàn)兩個分區(qū)的優(yōu)化劃分。如果需要得到多個分區(qū)，則需要對子分區(qū)重復(fù)該方法。為了提高分區(qū)效率，采用NJW多路譜算法[17]，即根據(jù)多個第二最小特征向量，通過聚類算法直接獲得指定數(shù)量的分區(qū)。矩陣E的最大特征值為1，其他特征值均小于1。對于社團(tuán)結(jié)構(gòu)比較明顯的管網(wǎng)，有些特征值接近于1，其對應(yīng)的第二特征向量中，同一社團(tuán)內(nèi)部節(jié)點(diǎn)的值接近。對于社團(tuán)結(jié)構(gòu)不明顯的一般給水管網(wǎng)，少量第二特征向量也可獲得良好分區(qū)[18]。第二特征向量確定方法如下：

1）確定管道權(quán)重。管徑、流量大的管道承擔(dān)的輸配水功能越重要，兩節(jié)點(diǎn)連接越緊密，選擇管道權(quán)重為wij=DijQij，Dij、Qij分別為管道ij的管徑與流量。

2）計算矩陣E前k1個最大的第二特征值所對應(yīng)的特征向量，x1，…，xk-1，構(gòu)造矩陣X=[x1，…，xk-1]∈Rn×（k-1）。

3）將矩陣的行向量轉(zhuǎn)換為單位向量，得到矩陣Y，即Yij=XijjX2ij。

4）將Y的每一行看做Rk-1空間中的一個點(diǎn)。

1.3基于遺傳算法的譜聚類

給水管網(wǎng)分區(qū)信息可通過特征向量數(shù)據(jù)挖掘方法獲得。本文采用遺傳算法與K均值算法實現(xiàn)數(shù)據(jù)挖掘。K均值算法將屬性相同的點(diǎn)劃分到一個聚類，并用聚類中心代表該聚類。聚類質(zhì)量由誤差平方和度量，見式（5）。

SSE=mi=1yCidist（y，ci）2（5）

式中：SSE為誤差平方和；Ci為某個聚類i；ci為聚類中心，代表某個聚類；y為空間點(diǎn)；dist為空間點(diǎn)的歐幾里得距離；m為聚類個數(shù)。

K均值算法取決于初始化聚類中心，是一種局部優(yōu)化算法。為了實現(xiàn)最優(yōu)化分區(qū)，采用遺傳算法優(yōu)化聚類中心。種群中每個個體對應(yīng)于各個聚類中心，以SSE最小化為目標(biāo)函數(shù)，通過線性排序確定個體適應(yīng)度，交叉、變異逐漸產(chǎn)生新的子代。為了提高搜索速度，在每次得到聚類劃分后，用校正后的聚類中心代替?zhèn)€體中原來的聚類中心。

1.4確定閥門、水表位置

在確定分區(qū)范圍后，接下來要確定水表和閥門的位置。在每個分區(qū)中均存在中心節(jié)點(diǎn)，一般是拓?fù)溥B接緊密的節(jié)點(diǎn)，即度較高的節(jié)點(diǎn)，這意味著該節(jié)點(diǎn)是流量的樞紐節(jié)點(diǎn)，則水源到該樞紐節(jié)點(diǎn)的最短供水路徑應(yīng)該是該分區(qū)的主要供水路徑，主要供水路徑必經(jīng)過分區(qū)間連接管道，則這個管道即為進(jìn)水點(diǎn)，也就是水表位置，其他連接管道則為閥門位置。本文中將給水管網(wǎng)視為權(quán)重?zé)o向圖，利用PageRank算法確定各節(jié)點(diǎn)的中心性。設(shè)每個節(jié)點(diǎn)的中心性為xi，節(jié)點(diǎn)i的中心性與它的鄰居節(jié)點(diǎn)中心性呈正比。

xi=jA～ijxj

（6）

PageRank算法的節(jié)點(diǎn)中心性向量x對應(yīng)于轉(zhuǎn)移矩陣A～的最大特征值對應(yīng)的特征向量，可以通過冪法迭代求得。

在中心性向量x中找出每個分區(qū)中心性最大的節(jié)點(diǎn)，通過Dijkstra算確定水源到該節(jié)點(diǎn)的最短路徑，進(jìn)而確定水表位置，其他連接管道則為閥門位置。主要供水路徑應(yīng)當(dāng)是水頭損失小，流量較大的管道，則此時最短路徑算法選用的管道權(quán)重為wij=ΔHijQij。

1.5分區(qū)均衡性

每個分區(qū)規(guī)模應(yīng)相當(dāng)，分區(qū)內(nèi)壓力應(yīng)均衡。為此提出兩個分區(qū)評價指標(biāo)。

1）分區(qū)規(guī)模均衡性SU

SU=ni=1Si-1MNi=1Si1MNi=1Si×100%（7）

式中：Si為節(jié)點(diǎn)用水量；M為分區(qū)數(shù)量；N為管網(wǎng)用水節(jié)點(diǎn)數(shù)；n為每個分區(qū)內(nèi)用水節(jié)點(diǎn)數(shù)。

各分區(qū)SU越接近，分區(qū)規(guī)模越均衡。

2）壓力均衡性PU

PU=1nni=1Pi-P2（8）

式中：Pi為節(jié)點(diǎn)壓力；P為分區(qū)平均壓力；PU越小，壓力越均衡。

1.6分區(qū)間運(yùn)行關(guān)系

DMA按進(jìn)水點(diǎn)數(shù)量和流量關(guān)系可分為單進(jìn)口、多進(jìn)口和串聯(lián)DMA，如圖1所示，其中，DMA2和DMA3為單進(jìn)口類型，DMA4為多進(jìn)口，上述3個分區(qū)共同特征是均只有流量流入而無流出。而DMA1除滿足本區(qū)用水外，還需向DMA2供水，因此，DMA1為串聯(lián)類型，有流量的流入和流出。目前的分區(qū)方法為了方便管理并減少計量誤差，一般DMA設(shè)計優(yōu)先選擇單進(jìn)口、無流出類型[19]。但DMA設(shè)計影響因素多、情況復(fù)雜，有時難以滿足上述原則，同時單進(jìn)口DMA也存在系統(tǒng)彈性能力降低、難以滿足消防流量要求和末端水質(zhì)下降等問題，因此，根據(jù)具體情況也可選擇多進(jìn)口DMA，但進(jìn)水口數(shù)量不宜太多，否則進(jìn)水點(diǎn)處減壓閥會引起壓力波動[20]?？刹捎弥鳌⒏边M(jìn)水口設(shè)計，即在正常供水時只開啟主進(jìn)水口，而當(dāng)高峰用水或消防時，可開啟副進(jìn)水口。當(dāng)遠(yuǎn)離干管的DMA其供水路徑需要經(jīng)過其他分區(qū)時，或者管理、技術(shù)等多因素綜合比較后串聯(lián)DMA具有優(yōu)勢時，也可選擇串聯(lián)類型DMA。

4個分區(qū)的方案如圖2所示。每個分區(qū)的規(guī)?？梢姳?，從表中可知每個分區(qū)的規(guī)模與平均規(guī)模有一定偏差。如前所述，如果分區(qū)時強(qiáng)調(diào)每個分區(qū)應(yīng)含有相同的規(guī)模（用水量），則必將破壞給水管網(wǎng)內(nèi)部的聚類結(jié)構(gòu)。而依據(jù)聚類算法，屬性相似的節(jié)點(diǎn)組成一個分區(qū)，這可從整體上降低分區(qū)對給水管網(wǎng)結(jié)構(gòu)的影響。分區(qū)后的壓力分析見表2。由表2可知，每個分區(qū)壓力范圍相似，平均壓力有微小差別。壓力均衡性較好，PU值均低于平均壓力的10%，說明分區(qū)后管網(wǎng)性能沒有明顯降低，對系統(tǒng)性能的影響較小。endprint

利用最短路徑算法可得每個分區(qū)水表位置，其他分區(qū)邊界管道則為閥門位置。由圖2分區(qū)結(jié)構(gòu)可知，基于譜聚類的分區(qū)方法將干管節(jié)點(diǎn)也納入分區(qū)，因此，DMA1和DMA4具有流量流入流出，為串聯(lián)分區(qū)，DMA2和DMA3則為單進(jìn)口分區(qū)。串聯(lián)分區(qū)結(jié)構(gòu)的引入，使得DMA1和DMA4內(nèi)節(jié)點(diǎn)分區(qū)前后水流路徑不變，分區(qū)對這些節(jié)點(diǎn)沒有影響。

3結(jié)論

提出了基于譜聚類的給水管網(wǎng)分區(qū)方法，同時可確定每個分區(qū)的進(jìn)水點(diǎn)和閥門位置，并以一個真實給水管網(wǎng)說明本分區(qū)方法的可行性。本方法將給水管網(wǎng)拓?fù)浣Y(jié)構(gòu)通過譜方法映射到高維向量空間，并依據(jù)聚類將拓?fù)湎嗨乒?jié)點(diǎn)劃分到一個分區(qū)，遺傳算法與K均值算法相結(jié)合提高了算法效率，同時，本方法具有較強(qiáng)的健壯性，可根據(jù)要求實現(xiàn)不同規(guī)模的分區(qū)設(shè)計。

本文中不僅確定了分區(qū)邊界，也給出了進(jìn)水點(diǎn)位置，下一步工作可在此基礎(chǔ)上通過優(yōu)化進(jìn)水點(diǎn)減壓閥，將各分區(qū)內(nèi)壓力控制在合理范圍，從而在整體上降低漏損。

參考文獻(xiàn)：

[1]

MORRISON J， TOOMS S， ROGERS D. District metered areas guidance notes [M]. London： IWA Publication， 2007.

[2] 劉俊， 孫佳， 俞國平. 分區(qū)供水技術(shù)在漏損控制中的研究現(xiàn)狀與進(jìn)展[J].中國給水排水， 2010， 26（16）：710.

LIU J， SUN J， YU G P. Current situation and progress of water distribution system zoning technologies for water loss control [J]. China Water & Wastewater， 2010， 26（16）：710. （in Chinese）

[3] 凌文翠， 張濤， 強(qiáng)志民， 等. 城市供水管網(wǎng)獨(dú)立計量區(qū)域的研究與應(yīng)用進(jìn)展[J].中國給水排水， 2011， 27（13）：4650.

LING W C， ZHANG T， QIANG Z M， et al. Research and application of district metering area for urban water distribution network [J]. China Water & Wastewater， 2011， 27（13）：4650. （in Chinese）

[4] 李樹平. 日本給水管網(wǎng)布局理論與啟示[J].中國給水排水， 2014， 30（22）：4649.

LI S P. Review of Japanese theory on water distribution system layout [J]. China Water & Wastewater， 2014， 30（22）：4649. （in Chinese）

[5] 許剛， 朱子鵬， 劉文杰， 等. 大規(guī)模供水管網(wǎng)分級分區(qū)計量應(yīng)用研究[J]. 給水排水， 2014， 30（22）：9698.

XU G， ZHU Z P， LIU W J， et al. Application of district metered areas in large scale water distribution system [J]. Water & Wastewater Engineering， 2014， 30（22）：9698. （in Chinese）

[6] FERRARI G， SAVIC D， BECCIU G. A graph theoretic approach and sound engineering principles for design of district metered areas [J]. Journal of Water Resources Planning and Management， 2014， 140（12）： 04014036.

[7] ALVISI S， FRANCHINI M. A heuristic procedure for the automatic creation of district metered areas in water distribution systems [J]. Urban Water Journal， 2014， 11（2）： 137159.

[8] AWAD H， KAPELAN Z， SAVIC D. Optimal setting of timemodulated pressure reducing valves in water distribution networks using genetic algorithms [C] // Boxall & Maksimovié. Integrating Water Systems （CCWI 2009 Conference）. London： Taylor & Francis Group， 2009：3137.

[9] DI NARDO A， DI NATALE M， SANTONASTASO G F， et al. Water network sectorization based on graph theory and energy performance indices [J]. Journal of Water Resources Planning and Management， 2014， 140（5）： 620629.

[10] 張楠. 城市供水管網(wǎng)分區(qū)管理技術(shù)優(yōu)化研究[D]. 天津： 天津大學(xué)， 2012.endprint

ZHANG N. District metered areas optimization for water distribution systems [D]. Tianjin： Tianjin University， 2012.

[11] 劉俊， 俞國平. 結(jié)合圖論與地理信息系統(tǒng)的供水管網(wǎng)分區(qū)優(yōu)化[J]. 同濟(jì)大學(xué)學(xué)報（自然科學(xué)版）， 2012， 40（12）： 18631869.

LIU J， YU G P. Integration of graph theory systems and GIS for district metered areas of water distribution [J]. Journal of Tongji University （Natural Science）， 2012， 40（12）： 18631869. （in Chinese）

[12] DI NARDO A， DI NATALE M， SANTONASTASO G F， et al. An automated tool for smart water network partitioning [J]. Water Resour Manage， 2013， 27（13）： 44934508.

[13] DIAO K G.， ZHOU Y W， RAUCH W. Automated creation of district metered area boundaries in water distribution systems [J]. Journal of Water Resources Planning and Management， 2013， 139（2）： 184190.

[14] GIUSTOLISI G， RIDOLFI L. A novel infrastructure modularity index for the segmentation of water distribution networks [J]. Water Resources Research， 2014， 50（10）： 76487661.

[15] 葉健， 高金良， 刁美玲， 等. 分形理論在城市供水管網(wǎng)規(guī)劃中的應(yīng)用研究[J]. 工程設(shè)計學(xué)報， 2014， 21（6）：562565.

YE J， GAO J L， DIAO M L， et al. Application study on urban water supply network planning based on fractal theory [J]. Journal of Engineering Design， 2014， 21（6）：562565. （in Chinese）

[16] 何忠華， 袁一星. 基于分區(qū)模型的城市供水管網(wǎng)壓力監(jiān)測點(diǎn)布置[J]. 哈爾濱工業(yè)大學(xué)學(xué)報， 2014， 46（10）：3741.

HE Z H， YUAN Y X. Layout of pressure monitoring system based points in urban water distribution on district model [J]. Journal of Harbin Institute of Technology， 2014， 46（10）：3741. （in Chinese）

[17] NG A Y， JORDAN M I， WEISS Y. On spectral clustering： Analysis and an algorithm[C]// Dietterich T G， Becker S， Ghahramani. Advances in Neural Information Processing Systems， Cambridge， MA， MIT Press， 2002， 14： 849856.

[18] CAPOCCI A， SERVEDIO V D P， CALDARELLI G， et al. Detecting communities in large networks [J]. Physica A， 2005， 352（2/3/4）：669676.

[19] FERRARI G， SAVIC D， BECCIU G. A graph theoretic approach and sound engineering principles for design of district metered areas [J]. Journal of Water Resources Planning and Management，2014， 140（12）： 113.

[20] PRESCOTT S， ULANICKI B. Improved control of pressure reducing valves in water distribution networks [J]. Journal of Hydraulic Engineering， 2008，134（1）： 5665.

[21] FARLEY M. Leakage management and control： A best practice training manual [M]. WHO， 2001.

[22] BRAGALLI C， D'AMBROSIO C， LEE J， et al. On the optimal design of water distribution networks： a practical MINLP approach [J]. Optimization and Engineering， 2012， 13（2）： 219246.

（編輯王秀玲）endprint