劉俊　周鵬

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

關(guān)鍵詞：給水管網(wǎng)；分區(qū)；聚類；優(yōu)化

中圖分類號(hào)：TU991

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674-4764（2016）06-0142-06

給水管網(wǎng)分區(qū)是在系統(tǒng)性能影響最小的情況下通過安裝閥門、水表形成獨(dú)立供水區(qū)域，便于優(yōu)化調(diào)度、漏損控制等各方面的管理，以適應(yīng)信息化、智能化、精細(xì)化的要求。管網(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ī)模時(shí)，搜索終止，則可得到滿足要求的分區(qū)。這類方法可獲得各種分區(qū)方案供決策者選定，或者通過模型分析獲得水力最優(yōu)方案。相比于廣度優(yōu)先搜索算法的局部搜索，深度優(yōu)先搜索算法可從整體上獲得給水管網(wǎng)樹狀結(jié)構(gòu)，并通過優(yōu)化算法獲得減壓閥最佳位置，進(jìn)而實(shí)現(xiàn)分區(qū)，或者確定各水源供水范圍。另外，也可以最短路徑算法為基礎(chǔ)，通過壓力均衡性確定分，或者通過管道介數(shù)中心性選定閥門、水表位置，以實(shí)現(xiàn)分區(qū)。

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

筆者提出一種基于復(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)聚類，繼而實(shí)現(xiàn)滿足要求的分區(qū)。

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

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

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

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

3）確定閥門、水表位置：PageRank算法確定每個(gè)分區(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)，實(shí)現(xiàn)分區(qū)設(shè)計(jì)，因此，在獲得指定數(shù)量的分區(qū)時(shí)，每個(gè)分區(qū)的規(guī)模不是嚴(yán)格相同。

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

譜平分法利用第二小特征值對應(yīng)的特征向量實(shí)現(xiàn)兩個(gè)分區(qū)的優(yōu)化劃分。如果需要得到多個(gè)分區(qū)，則需要對子分區(qū)重復(fù)該方法。為了提高分區(qū)效率，采用NJW多路譜算法，即根據(jù)多個(gè)第二最小特征向量，通過聚類算法直接獲得指定數(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ū)。第二特征向量確定方法如下：

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

1.4確定閥門、水表位置

在確定分區(qū)范圍后，接下來要確定水表和閥門的位置。在每個(gè)分區(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ū)間連接管道，則這個(gè)管道即為進(jìn)水點(diǎn)，也就是水表位置，其他連接管道則為閥門位

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

2.分區(qū)實(shí)例

以圖2所示環(huán)狀給水管網(wǎng)為例驗(yàn)證所提分區(qū)方法的有效性。該給水管網(wǎng)含有1個(gè)水源，36個(gè)用水點(diǎn)，58根管道，具有復(fù)雜的環(huán)狀結(jié)構(gòu)。設(shè)定分區(qū)數(shù)量為4個(gè)。

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

K均值算法是局部優(yōu)化方法，遺傳算法是一種全局優(yōu)化方法，二者結(jié)合將增加收斂速度，由圖3可知，經(jīng)過25次進(jìn)化后種群即實(shí)現(xiàn)收斂。另外，每一代的最佳個(gè)體都能搜索到最佳聚類。

在確定分區(qū)邊界后，需要確定每個(gè)分區(qū)的進(jìn)水點(diǎn)和設(shè)置閥門的管道。為此根據(jù)PageRank算法分析每個(gè)節(jié)點(diǎn)的中心性，給水管網(wǎng)末端節(jié)點(diǎn)中心性較

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

3.結(jié)論

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

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