高金良，姚　芳，葉　健

(哈爾濱工業(yè)大學(xué) 市政環(huán)境工程學(xué)院，哈爾濱 150090)

?

結(jié)合圖論的供水管網(wǎng)PMA分區(qū)方法

高金良，姚芳，葉健

(哈爾濱工業(yè)大學(xué) 市政環(huán)境工程學(xué)院，哈爾濱 150090)

摘要:供水管網(wǎng)壓力分區(qū)(PMA)以壓力調(diào)控為主，兼顧區(qū)域計(jì)量，可有效地控制城市管網(wǎng)漏失，為此，提出結(jié)合圖論的PMA分區(qū)方法，首先運(yùn)用自適應(yīng)AP聚類算法結(jié)合經(jīng)濟(jì)性計(jì)算對(duì)供水管網(wǎng)進(jìn)行初步分區(qū)，確定分區(qū)數(shù)目；然后運(yùn)用迪杰斯特拉(Dijkstra)算法計(jì)算各個(gè)聚類中心點(diǎn)到水源的最短路徑，確定各個(gè)分區(qū)的供水管段；建立分區(qū)邊界優(yōu)化模型，運(yùn)用模擬退火算法求解該模型；最后結(jié)合人工經(jīng)驗(yàn)對(duì)部分分區(qū)進(jìn)行適當(dāng)合并，形成最終方案并運(yùn)用于Y市供水管網(wǎng)實(shí)例，取得良好結(jié)果.該種分區(qū)方法是以計(jì)算機(jī)算法為主體并結(jié)合人工經(jīng)驗(yàn)，很大程度降低分區(qū)的工作量，并且比傳統(tǒng)的人工試錯(cuò)分區(qū)具有更大的搜索空間，可用于指導(dǎo)實(shí)際供水管網(wǎng)的PMA分區(qū).

關(guān)鍵詞:PMA分區(qū)；圖論；AP聚類算法；迪杰斯特拉算法；模擬退火算法

近年來(lái)，供水管網(wǎng)分區(qū)成為國(guó)內(nèi)外控漏研究領(lǐng)域的一大熱點(diǎn)，國(guó)際上普遍認(rèn)可這種“分而治之”的分區(qū)思想.將供水管網(wǎng)進(jìn)行分區(qū)后，能夠找到供水管網(wǎng)漏失主要原因，由消極被動(dòng)轉(zhuǎn)變?yōu)榉e極主動(dòng)地控漏，有利于加強(qiáng)水質(zhì)監(jiān)測(cè)及壓力管理[1-4].國(guó)內(nèi)外的供水行業(yè)學(xué)者和研究人員都對(duì)供水管網(wǎng)分區(qū)控漏進(jìn)行了積極探究，研究的分區(qū)方法主要分為區(qū)域計(jì)量分區(qū)、壓力分區(qū)和管理分區(qū).其中，壓力分區(qū)被認(rèn)為是最具有經(jīng)濟(jì)效益的方法.城市供水管網(wǎng)壓力分區(qū)技術(shù)最早起源于20世紀(jì)80年代，以供水管網(wǎng)漏損隨著水壓上升而增大的規(guī)律為理論基礎(chǔ)，依據(jù)地形、水壓分布等因素將管網(wǎng)分為若干壓力管理區(qū)，通過(guò)對(duì)所有或部分管理區(qū)進(jìn)行壓力控制，降低管網(wǎng)的平均壓力實(shí)現(xiàn)減少管網(wǎng)漏失等目的.May[5]和Godwin[6]指出供水管網(wǎng)中漏失總量與壓力呈指數(shù)關(guān)系，可以通過(guò)降低整個(gè)管網(wǎng)或局部區(qū)域壓力來(lái)降低漏失水量；Stering[7]將供水管網(wǎng)劃分為若干個(gè)壓力管理區(qū)域，通過(guò)控制閥門的開啟，實(shí)現(xiàn)供水管網(wǎng)壓力的優(yōu)化控制.我國(guó)對(duì)供水管網(wǎng)壓力分區(qū)的研究起步較晚，崔建國(guó)等[8]通過(guò)對(duì)節(jié)點(diǎn)壓力、壓力變化靈敏度及管網(wǎng)的供水分界線的分析，綜合考慮管網(wǎng)布置區(qū)的規(guī)劃和地形情況，對(duì)復(fù)雜管網(wǎng)進(jìn)行分區(qū)管理；周玉文等[9]提出應(yīng)綜合考慮區(qū)域計(jì)量分區(qū)原則、壓力分區(qū)原則及管理分區(qū)原則進(jìn)行分區(qū)規(guī)劃的新思路，并對(duì)分區(qū)改造后的管網(wǎng)進(jìn)行了模擬分析.

一般來(lái)說(shuō)，管網(wǎng)的爆管率、漏失量、管件及其他設(shè)備的故障率均與管網(wǎng)中水壓存在正相關(guān)性[10].實(shí)時(shí)掌握管網(wǎng)水壓分布情況對(duì)于控制管網(wǎng)漏失[11]、降低爆管事故發(fā)生率及供水能耗具有重要意義[12]，而供水管網(wǎng)PMA分區(qū)是壓力分區(qū)控制的基礎(chǔ).PMA分區(qū)是并行分區(qū)，區(qū)域之間不存在對(duì)下一區(qū)域串聯(lián)供水的情況，該情況下形成的分區(qū)可以對(duì)每個(gè)區(qū)域單獨(dú)進(jìn)行壓力控制.同時(shí)，與傳統(tǒng)的人工試錯(cuò)分區(qū)方法相比，PMA分區(qū)具有更大的搜索空間，能提高分區(qū)適用性.本文結(jié)合工程實(shí)際，綜合運(yùn)用圖論的思想，將供水管網(wǎng)轉(zhuǎn)化為圖的結(jié)構(gòu)，對(duì)供水管網(wǎng)進(jìn)行PMA分區(qū).

1PMA分區(qū)

供水管網(wǎng)的分區(qū)數(shù)目直接影響分區(qū)方案的優(yōu)劣.分區(qū)數(shù)目少，供水管網(wǎng)的壓力管理不徹底，會(huì)導(dǎo)致許多節(jié)點(diǎn)壓力過(guò)高，降低降漏效果；分區(qū)數(shù)目多，投資費(fèi)用增加，且對(duì)供水管網(wǎng)拓?fù)浣Y(jié)構(gòu)造成擾動(dòng)，易導(dǎo)致供水不穩(wěn)定.本文用自適應(yīng)AP聚類算法并結(jié)合經(jīng)濟(jì)效益對(duì)供水管網(wǎng)進(jìn)行初步分區(qū)，確定分區(qū)數(shù)目.在分區(qū)過(guò)程中，投資費(fèi)用主要指安裝減壓站費(fèi)用.如圖1所示，投資費(fèi)用與分區(qū)數(shù)目呈線性關(guān)系，經(jīng)濟(jì)效益開始隨分區(qū)數(shù)目的增加而增加較快，逐漸增速變緩，因此，投資回報(bào)與分區(qū)數(shù)目的關(guān)系呈向下拋物線關(guān)系.自適應(yīng)AP聚類算法由Fery B J和Dueck D于2007年首次提出[13].該算法不需要指定聚類數(shù)目，而是在算法運(yùn)行過(guò)程中設(shè)定圖中所有點(diǎn)到其類中心點(diǎn)的距離之和為目標(biāo)函數(shù)，隨著迭代的進(jìn)行，不斷搜索與變換聚類中心點(diǎn)的位置與數(shù)目，使目標(biāo)函數(shù)最小[14].本文利用自適應(yīng)AP聚類算法的特點(diǎn)，合理地確定分區(qū)數(shù)目，使投資效益最大化.

圖1　分區(qū)數(shù)目與投資效益的關(guān)系

確定分區(qū)數(shù)目時(shí)，以用水節(jié)點(diǎn)的X坐標(biāo)、Y坐標(biāo)和自由水頭這3個(gè)參數(shù)進(jìn)行歸一化計(jì)算后用于定義節(jié)點(diǎn)的三維位置.算法開始時(shí)需設(shè)定Pi值，通常Pi為i節(jié)點(diǎn)與其他所有節(jié)點(diǎn)相似度的平均值，也可根據(jù)需要自行設(shè)定值，值越大則聚類數(shù)目越多，反之，值越小則聚類數(shù)目越少[15].由于聚類前每個(gè)節(jié)點(diǎn)都具有成為聚類中心的可能性，開始定義所有節(jié)點(diǎn)的Pi均相等.輸入這些參數(shù)進(jìn)行第一次聚類運(yùn)算，得到各個(gè)點(diǎn)的類歸屬和聚類數(shù)目，計(jì)算各個(gè)類中節(jié)點(diǎn)所具有的降漏潛力，從而得到這種聚類方案下的經(jīng)濟(jì)效益，結(jié)合投資回收期確定分區(qū)數(shù)目是否可行，進(jìn)而調(diào)整P值進(jìn)行下一次AP聚類，直到計(jì)算得出使投資回報(bào)期最短的初步聚類方案.

2確定供水管網(wǎng)PMA分區(qū)區(qū)域入口

供水管網(wǎng)PMA分區(qū)是不完全分區(qū)模式.本文采用鄰接矩陣表示管網(wǎng)拓?fù)洌\(yùn)用迪杰斯特拉(Dijkstra)算法[16]計(jì)算聚類中心到水源的最短路徑，并將最短路徑定義為各個(gè)區(qū)域的供水入口.供水管網(wǎng)的主干管部分不進(jìn)行區(qū)域劃分，但初步分區(qū)時(shí)所有節(jié)點(diǎn)均參與聚類，最后需剔除節(jié)點(diǎn)大多分布在主干管上的區(qū)域.計(jì)算步驟如下[17]：

1)初始化S集合，此時(shí)集合S中只含有單一水源點(diǎn)v0，集合T中則包含拓?fù)鋱D中除水源點(diǎn)v0外的所有頂點(diǎn)，若供水管網(wǎng)模型中有m個(gè)水源，則運(yùn)用迪杰斯特拉算法分別計(jì)算m次；

2)計(jì)算集合T中各頂點(diǎn)到水源點(diǎn)v0的距離，將距離最小的頂點(diǎn)u加入到集合S中；

3)計(jì)算頂點(diǎn)u到集合T中各頂點(diǎn)的距離，若經(jīng)過(guò)頂點(diǎn)u到頂點(diǎn)t的距離值比原來(lái)不經(jīng)過(guò)頂點(diǎn)u到水源點(diǎn)v0的距離值小，則修改t的距離值；

4)重復(fù)步驟2)和3)直到供水管網(wǎng)拓?fù)鋱D中所有的頂點(diǎn)都由集合T轉(zhuǎn)移到集合S中，算法結(jié)束.

3區(qū)域邊界優(yōu)化模型建立及求解

確定區(qū)域入口后，若此時(shí)直接對(duì)聚類邊界進(jìn)行關(guān)閥，將會(huì)有大量節(jié)點(diǎn)無(wú)法供水，這對(duì)供水管網(wǎng)擾動(dòng)太多.此時(shí)需要對(duì)分區(qū)邊界進(jìn)行優(yōu)化，以減小對(duì)管網(wǎng)的擾動(dòng)，實(shí)現(xiàn)分區(qū).

3.1區(qū)域邊界優(yōu)化模型

供水管網(wǎng)分區(qū)的基本要求是保證其供水安全性，即分區(qū)后供水管網(wǎng)中所有節(jié)點(diǎn)均能與水源節(jié)點(diǎn)連通并保證其供水的連通性.初步聚類后，需要對(duì)各個(gè)初步分區(qū)進(jìn)行節(jié)點(diǎn)連通性判斷，通過(guò)改變孤立節(jié)點(diǎn)的類歸屬，保證各個(gè)分區(qū)節(jié)點(diǎn)全連通.各個(gè)類中的節(jié)點(diǎn)全部連通后，可通過(guò)邊界優(yōu)化，盡量將分區(qū)對(duì)管網(wǎng)的擾動(dòng)程度降到最低.本文建立一個(gè)拓?fù)潆x散優(yōu)化模型，以確定分區(qū)邊界.

1)優(yōu)化變量.優(yōu)化模型的變量為分區(qū)邊界點(diǎn)的類歸屬.然而分區(qū)邊界的點(diǎn)并不固定，優(yōu)化過(guò)程中隨著某節(jié)點(diǎn)類歸屬的變化，周圍節(jié)點(diǎn)就有可能從非分區(qū)邊界點(diǎn)變?yōu)榉謪^(qū)邊界點(diǎn).因此，該模型以供水管網(wǎng)拓?fù)鋱D中所有節(jié)點(diǎn)的類歸屬作為優(yōu)化變量，類歸屬的數(shù)量固定不變，由AP聚類算法得出.所有節(jié)點(diǎn)的類歸屬矩陣如下

(1)

2)目標(biāo)函數(shù).確定分區(qū)邊界的目的是使分區(qū)可行，因此，需要降低分區(qū)對(duì)原管網(wǎng)的擾動(dòng).此時(shí)應(yīng)盡可能地找出分區(qū)邊界上流量較小的管段，關(guān)閉這樣的管段對(duì)管網(wǎng)供水影響較小.定義管段流量作為全管網(wǎng)鄰接矩陣的權(quán)值，目標(biāo)函數(shù)為使所有邊界管段的權(quán)值之和最小，適應(yīng)度函數(shù)如下

(2)

式中：fedge為邊界管段的流量，最短路徑管段流量不參與目標(biāo)函數(shù)計(jì)算，L/s.

但是上節(jié)已建立的各個(gè)節(jié)點(diǎn)的最短路徑結(jié)構(gòu)構(gòu)成了供水管網(wǎng)最基本的拓?fù)淠Ｊ?，且最短路徑通常?huì)成為區(qū)域之間的連接管段.因此，在分區(qū)邊界優(yōu)化過(guò)程中，為了不干擾優(yōu)化結(jié)果，最短路徑管段流量直接記為0.

3)約束條件.優(yōu)化過(guò)程中，可通過(guò)保證各個(gè)類所有節(jié)點(diǎn)的連通性來(lái)確保管網(wǎng)的供水安全性，因此，在優(yōu)化迭代過(guò)程中約束條件為每一代聚類中心點(diǎn)與該類內(nèi)部所有節(jié)點(diǎn)的連通性必須保證.

3.2區(qū)域邊界優(yōu)化模型求解

建立的模型屬于離散變量拓?fù)鋬?yōu)化模型.優(yōu)化過(guò)程中，拓?fù)涔?jié)點(diǎn)的屬性需要不斷改變，并且每次迭代過(guò)程需要隨機(jī)對(duì)拓?fù)涔?jié)點(diǎn)屬性進(jìn)行擾動(dòng)，從而挑選出最佳種群進(jìn)行下一次迭代，模擬退火算法能夠很好地解決該問(wèn)題.模擬退火(simulated annealing)算法是1982年Kirkpatrick等[18-19]提出的一種針對(duì)NP完全問(wèn)題的算法.本節(jié)在初步聚類的基礎(chǔ)上，將初步聚類結(jié)果作為模擬退火算法的初始解，運(yùn)用標(biāo)準(zhǔn)模擬退火算法優(yōu)化局部區(qū)域(分區(qū)邊界部分)，通過(guò)迭代得到最優(yōu)方案，模擬算法中的相關(guān)參數(shù)在工程案例中設(shè)置.

4分區(qū)合并

供水管網(wǎng)分區(qū)邊界優(yōu)化完成后，關(guān)閉所有的邊界管段進(jìn)行水力計(jì)算，此時(shí)由于關(guān)閉管段過(guò)多，極易導(dǎo)致水力條件無(wú)法滿足用戶需求.因此，結(jié)合人工經(jīng)驗(yàn)對(duì)部分區(qū)域進(jìn)行合并，保證供水要求.合并形式主要為縱向合并和橫向合并.初步分區(qū)并計(jì)算最短路徑后，若有兩個(gè)聚類中心共用一條供水路徑，則對(duì)供水管網(wǎng)分區(qū)進(jìn)行縱向合并，以保證主干管直接向所有區(qū)域供水，如圖2所示；若分區(qū)之間連接管段較多，完全關(guān)斷會(huì)導(dǎo)致局部供水壓力不足，此時(shí)需要對(duì)這兩個(gè)分區(qū)進(jìn)行橫向合并，合并后可以兩個(gè)入口綜合控壓，也可以再通過(guò)最短路徑計(jì)算出一條供水管線，如圖3所示.

圖2　分區(qū)縱向合并示意

圖3　分區(qū)橫向合并示意

5工程案例

本文運(yùn)用Y市的實(shí)際供水管網(wǎng)，收集其供水管網(wǎng)運(yùn)行基礎(chǔ)信息，得出最高時(shí)和最低時(shí)供水管網(wǎng)自由水頭分布，結(jié)果見圖4、5.可以看出，為滿足供水管網(wǎng)末端壓力供給，整個(gè)管網(wǎng)壓力偏高.過(guò)高的壓力是本市漏失嚴(yán)重的重要原因.因此，結(jié)合圖論對(duì)Y市供水管網(wǎng)進(jìn)行PMA分區(qū)，劃分出具有降壓潛力的區(qū)域?qū)嵤毫刂?，探索該方法的可行性與適用性.

圖4　用水最高時(shí)供水管網(wǎng)自由水頭分布

圖5　用水最低時(shí)供水管網(wǎng)自由水頭分布

5.1AP聚類初步分區(qū)確定分區(qū)數(shù)目

結(jié)合實(shí)際工程進(jìn)行調(diào)研，Y市水司制水成本為0.65元/t，減壓站的購(gòu)置和安裝的總費(fèi)用為20萬(wàn)元，壓力控制設(shè)備年運(yùn)行費(fèi)用為1萬(wàn)元，當(dāng)?shù)匾蠊┧畨毫ψ畹筒坏玫陀?0 m自由水頭.優(yōu)化過(guò)程中，分區(qū)數(shù)降到20以內(nèi)時(shí)，管道改造費(fèi)用為0；分區(qū)數(shù)在20以上時(shí)，管道改造費(fèi)用隨著分區(qū)數(shù)的增加呈指數(shù)級(jí)增漲.

建立的優(yōu)化模型變量為自適應(yīng)AP聚類算法中的P值，優(yōu)化目標(biāo)為最大化年經(jīng)濟(jì)收益.因?yàn)樽兞繂我?，運(yùn)用進(jìn)退法依次計(jì)算P值，P的初始值按AP聚類算法默認(rèn)值，取-0.063 4，初始步長(zhǎng)為0.1，經(jīng)濟(jì)函數(shù)出現(xiàn)折點(diǎn)后步長(zhǎng)逐步減半迭代.最終優(yōu)化結(jié)果：P取值為-2.292 8，投資回收期為1.8 a，分區(qū)數(shù)為17.優(yōu)化過(guò)程各變量如圖6所示.

圖6　結(jié)合AP聚類算法的經(jīng)濟(jì)性計(jì)算結(jié)果

AP聚類算法依據(jù)節(jié)點(diǎn)的X坐標(biāo)，Y坐標(biāo)和自由水頭這3個(gè)屬性進(jìn)行聚類，P=-2.292 8時(shí)，最終得到的初步分區(qū)結(jié)果如圖7所示，管網(wǎng)被劃分為17個(gè)區(qū)域，分別用不同顏色表示.

圖7　初步聚類結(jié)果

5.2聚類中心點(diǎn)到水源的最短路徑

初步聚類得到17個(gè)區(qū)域的聚類中心后，分別計(jì)算17個(gè)聚類中心點(diǎn)到水源點(diǎn)的最短路徑.將管道的水頭損失作為最短路徑計(jì)算中點(diǎn)與點(diǎn)之間的權(quán)值，運(yùn)用迪杰斯特拉算法計(jì)算各個(gè)聚類中心點(diǎn)到兩個(gè)水源的最短路徑，最短路徑的長(zhǎng)度即水頭損失之和，結(jié)果如表1所示.可以看出，大部分聚類中心點(diǎn)到兩個(gè)水廠的最短路徑均相同，因此，無(wú)論從到哪個(gè)水源考慮，均不影響區(qū)域入口的確定.

表1　聚類中心點(diǎn)到兩個(gè)水源點(diǎn)的最短路徑長(zhǎng)度

5.3分區(qū)邊界優(yōu)化模型

初步分區(qū)及分區(qū)入口確定后，運(yùn)用模擬退火算法對(duì)分區(qū)邊界進(jìn)行優(yōu)化，優(yōu)化變量為管網(wǎng)中所有節(jié)點(diǎn)的類歸屬；適應(yīng)度函數(shù)為劃分的17個(gè)區(qū)域之間所有邊界管段的流量之和；約束條件為優(yōu)化過(guò)程中必須保持每個(gè)區(qū)域內(nèi)所有節(jié)點(diǎn)相互連通.最大迭代代數(shù)設(shè)置為300，終止條件設(shè)置為連續(xù)20代不接受新解則終止迭代.模擬退火算法迭代過(guò)程中適應(yīng)度函數(shù)終值總流量為42.94 L/s.最優(yōu)解中各區(qū)域間管段連接數(shù)如表2所示.

5.4分區(qū)合并

分區(qū)優(yōu)化邊界確定后，此時(shí)若將所有區(qū)域間連接管段均關(guān)閉，還是會(huì)導(dǎo)致水力條件無(wú)法滿足供水要求，因此，需要結(jié)合人工經(jīng)驗(yàn)對(duì)分區(qū)進(jìn)行適當(dāng)合并.此時(shí)會(huì)有部分區(qū)域的節(jié)點(diǎn)完全分布在主干管上，這種分布在主干管上的區(qū)域無(wú)法進(jìn)行壓力控制，不作PMA分區(qū)處理.

表2　區(qū)域間連接管段數(shù)量

由表2可以看出，6和16、5和14、1和13、1和14、7和13 這幾個(gè)分區(qū)之間管段連接數(shù)較多.最短路徑結(jié)構(gòu)以及聚類中心點(diǎn)類編號(hào)如圖8所示，可以看出，這些管段連接數(shù)較多的區(qū)域在空間拓?fù)浣Y(jié)構(gòu)也通常是鄰近區(qū)域，可以進(jìn)行合并.2和12分區(qū)分布在同一條主干管上，應(yīng)首先進(jìn)行合并區(qū)域，17節(jié)點(diǎn)數(shù)過(guò)少，不適合單獨(dú)形成分區(qū)，2、12分區(qū)管段連接數(shù)為8條管段，因此，2、12、17分區(qū)合并為一個(gè)區(qū)域；管段相互連接較多應(yīng)該一起合并的有1、5、7、13、14這5個(gè)分區(qū)，分區(qū)4在這5個(gè)分區(qū)供水后端，因此，將1、4、5、7、13、14合并為一個(gè)分區(qū)；6和16由于連接管段數(shù)過(guò)多，若完全關(guān)斷這些管段會(huì)導(dǎo)致供水壓力不足，將這兩個(gè)區(qū)域進(jìn)行合并，合并后該區(qū)域通過(guò)兩條主管線供水，若有壓力富裕，可在兩條管線上均安裝壓力控制設(shè)備；分區(qū)9和15的大部分節(jié)點(diǎn)均分布在主干管上，并且靠近水源，這兩個(gè)區(qū)域無(wú)法單獨(dú)進(jìn)行壓力控制，因此，不作分區(qū)處理.分區(qū)完全合并后，共形成7個(gè)PMA分區(qū).最終分區(qū)結(jié)果如圖9所示.

圖8　最短路徑拓?fù)浣Y(jié)構(gòu)

5.5分區(qū)結(jié)果分析

分區(qū)完成后，將區(qū)域之間的連接管段關(guān)閉后得到供水管網(wǎng)日用水量最高時(shí)和最低時(shí)供水管網(wǎng)自由水頭分布,如圖10、11所示.比較圖10、11和圖4、5可以看出，供水管網(wǎng)進(jìn)行分區(qū)后，用水量最低時(shí)和最高時(shí)的自由水頭均呈一定程度下降.此時(shí)對(duì)各個(gè)分區(qū)的壓力統(tǒng)計(jì)結(jié)果如表3所示.可以看出，7個(gè)分區(qū)的壓力歸一化方差均小于0.4，符合要求.Y市供水管網(wǎng)要求的自由水頭值必須大于20 m，從表3可以看出，分區(qū)形成后滿足供水要求.所以，該分區(qū)策略可用于指導(dǎo)實(shí)際供水管網(wǎng)PMA分區(qū)，并能夠取得良好漏失控制效果.

圖9　最終分區(qū)結(jié)果

圖10　分區(qū)后用水量最高時(shí)自由水頭分布

圖11　分區(qū)后用水量最低時(shí)自由水頭分布

分區(qū)編號(hào)壓力均值/m壓力歸一化方差最小自由水頭/m125.820.2622.90227.900.3823.55325.120.3521.96426.910.1723.16526.630.2122.97626.090.3322.49726.270.2922.80

6結(jié)論

1)結(jié)合圖論提出一種結(jié)合工程實(shí)踐的自動(dòng)PMA分區(qū)方法，首次將供水管網(wǎng)PMA分區(qū)總結(jié)為3個(gè)方面，即分區(qū)數(shù)目、分區(qū)入口和分區(qū)邊界.并運(yùn)用相應(yīng)算法解決這3個(gè)問(wèn)題，形成最終的可行方案.

2)現(xiàn)有的關(guān)于供水管網(wǎng)分區(qū)研究通常都是指定分區(qū)數(shù)目后再分區(qū)[20]，但對(duì)分區(qū)數(shù)目不能給出合理解釋.本文首次將經(jīng)濟(jì)計(jì)算引入到分區(qū)數(shù)目的確定中，提出了分區(qū)數(shù)目確定的合理化方法，提供了一種新的計(jì)算思路，具有很強(qiáng)的工程實(shí)用價(jià)值.

3)分區(qū)邊界形成后，結(jié)合人工經(jīng)驗(yàn)進(jìn)行分區(qū)合并來(lái)保證供水安全性，分區(qū)合并的原則是盡可能地保留分區(qū)，對(duì)水力條件無(wú)法滿足或供水路徑?jīng)_突無(wú)法形成PMA分區(qū)的部分進(jìn)行分區(qū)合并.

參考文獻(xiàn)

[1] DI NARDO A, DI NATALE M, MUSMARRA D, et al. A district sectorization for water network protection from intentional contamination[J]. Procedia Engineering, 2014,70:515-524.

[2] DI NARDO A, DI NATALE M, SANTONASTASO G F, et al. Divide and conquer partitioning techniques for smart water networks[J]. Procedia Engineering, 2014,89:1176-1183.

[3] DE PAOLA F, FONTANA N, GALDIERO E, et al. Optimaldesign of district metered areas in water distribution networks[J]. Procedia Engineering, 2014,70:449-457.

[4] MAMADE A, LOUREIRO D, COVAS D, et al. Spatial andtemporal forecasting of water consumption at the DMA level using extensive measurements[J]. Procedia Engineering, 2014,70:1063-1073.

[5] MAY J. Pressuredepend leakage[J]. World Water Environment Engineering,1994(10):15-19.

[6] GODWIN S J. The results of the experimental program on leakage and leakage control[J]. Water Research Center,1980(56):52-154.[7] STERING A. Leakagereduction by optimized control of valves in water networks[J]. Trans Inst MC, 1984,127(13):67-68.

[8] 崔建國(guó)，于慶江，梁海榮. 城市給水系統(tǒng)優(yōu)化調(diào)度中的管網(wǎng)分區(qū)方法[J]. 太原理工大學(xué)學(xué)報(bào)，2004,5(35):605-608.

CUI J G, YU Q J, LIANG H R. Study on the method dividing districts of water distribution network in optimal dispatch of city water system[J]. Journal of Taituan University of Technology,2004,35(5):605-608.

[9] 周玉文，刁克功，吳珊，等. 城市供水管網(wǎng)分區(qū)初步研究[C]//供水管網(wǎng)信息化管理與檢測(cè)技術(shù)應(yīng)用研討會(huì)論文集. 北京：中國(guó)建筑工業(yè)出版社，2005:213-221.

ZHOU Y W, DIAO K G, WU S, et al. Preliminary study of urban water supply network partition[C]//Civil Engineering Society of China.Collected Papers on Application of Information Management and Detection Technology System for Water Supply Network Rap Session. Beijing:China Building Industry Press,2005:213-221.

[10]張世澤，袁一星，李玉華. 城市供水管網(wǎng)優(yōu)化設(shè)計(jì)兩步法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2009, 41(4):111-117.

ZHANG S Z, YUAN Y X, LI Y H. Two-step method for optimal design of water distribution system[J]. Journal of Harbin Institute of Technology, 2009, 41(4):111-117.

[11]董深，呂謀，盛澤斌，等. 基于遺傳算法的供水管網(wǎng)反問(wèn)題流失定位[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2013, 45(2):106-128.

DONG S, LU M, SHENG Z B, et al. Inverse transient leakage location of water supply network based on genetic algorithm[J]. Journal of Harbin Institute of Technology,2013, 45(2):106-128.

[12]MOUNCE S R，BOXALL J B，MACHELL J. Development and verification of an online artificial intelligence system for detection of bursts and other abnormal flows [J]. Journal of Water Resources Planning and Management, 2010, 136(3):309-318.

[13]FERY B J，DUDCK D. Clustering by passing messages between data points[J]．Science,2007,315 (5814)：972-976.

[14]郭秀娟，陳瑩. AP聚類算法的分析與應(yīng)用[J]. 吉林建筑大學(xué)學(xué)報(bào), 2013,30(4):58-61.

GUO X J, CHEN Y. Analysis and application on AP clustering algorithm[J]. Journal of Jilin Jianzhu University, 2013,30(4):58-61.

[15]何晏成. 基于近鄰傳播和凝聚層次的文本聚類方法[D]. 哈爾濱:哈爾濱工業(yè)大學(xué), 2010:60.

HE Y C. A document clustering method based on affinity propagation and agglomerative hierarchical clustering[D].Harbin: Harbin Institute of Technology,2010:60.

[16]張念. 用Dijkstra算法實(shí)現(xiàn)對(duì)整車配送線路的優(yōu)化[J]. 中國(guó)水運(yùn)(理論版), 2007,5(5):141-142.

ZHANG N. Implement the optimization of vehicle distribution line based on Dijkstra algorithm[J]. China Water Transport, 2007,5(5):141-142.

[17]楊蔓. 最短路徑算法在煤礦安全分區(qū)分析中的應(yīng)用研究[D]. 西安:西安科技大學(xué), 2009:77.

YANG M. The study on the analysis of shortest path algorithm in the coal mine safety subarea[D]. Xi’an: Xi’an University of Science and Technology,2009:77.

[18]CARSTEN D. Optical design of multilayer achromatic waveplate by simulated annealing algorithm[J]. Chinese Journal of Astronomy and Astrophysics, 2008(3):349-361.

[19]張紅娟. 基于非格點(diǎn)模型的蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)研究[D]. 大連:大連理工大學(xué), 2006:55.

ZHANG H J. The research on the protein structure prediction based on the off-lattice protein model[D]. Danlian: Danlian University of Technology,2006:55.

[20]何忠華，袁一星. 基于分區(qū)模型的城市供水管網(wǎng)壓力監(jiān)測(cè)點(diǎn)布置[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2014,46(10):37-41.

HE Z H, YUAN Y X. Layout of pressure monitoring points in urban water distribution system based on district model[J].Journal of Harbin Institute of Technology,2014,46(10):37-41.

(編輯劉彤)

doi：10.11918/j.issn.0367-6234.2016.08.011

收稿日期:2015-11-07

基金項(xiàng)目:國(guó)家自然科學(xué)基金(51278148)；國(guó)家水體污染控制與治理科技重大專項(xiàng)(2014ZX07405002)；廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目(2011A090200040)

作者簡(jiǎn)介:高金良(1971—)，男，副教授，碩士生導(dǎo)師

通信作者:姚芳，yaofang0525@163.com

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

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

文章編號(hào):0367-6234(2016)08-0067-06

Optimization of water supply network PMA partition by graph theory

GAO Jinliang, YAO Fang, YE Jian

(School of Municipal and Environmental Engineering,Harbin Institute of Technology, Harbin 150090, China)

Abstract:The water supply pipe network pressure management area (PMA) partition, which is pressure-control oriented and regional metrology considered, effectively controls the leakage rate of urban water supply network. PMA partition with graph theory is proposed in this study. First of all, to initially partition the water supply network and set the partition number with adaptive AP clustering algorithm and economic calculation. Secondly, Dijkstra algorithm is adopted to calculate the shortest path of each cluster center point to the source of the water and determine the position of each division of the water supply pipe, and then establish a partition boundary optimization model and apply simulated annealing algorithm to solve the model. Finally, combine some partitions properly with artificial expertise and form the final plan. This partition, computer algorithm oriented and combined with artificial expertise, embraces larger search space than the traditional artificial partition of trial and error and can guide the actual water supply network PMA partition.

Keywords:PMA partition; graph theory; AP clustering algorithm; Dijkstra algorithm; simulated annealing algorithm