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

高金良，姚　芳，葉　健

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

?

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

高金良，姚芳，葉健

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

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

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

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

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

1PMA分區(qū)

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

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

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

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

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

1)初始化S集合，此時集合S中只含有單一水源點v0，集合T中則包含拓撲圖中除水源點v0外的所有頂點，若供水管網(wǎng)模型中有m個水源，則運用迪杰斯特拉算法分別計算m次；

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

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

4分區(qū)合并

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

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

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

5工程案例

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

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

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

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

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

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

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

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

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

5.2聚類中心點到水源的最短路徑

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

表1　聚類中心點到兩個水源點的最短路徑長度

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

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

5.4分區(qū)合并

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

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

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

圖8　最短路徑拓撲結(jié)構(gòu)

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

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

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

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

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

分區(qū)編號壓力均值/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é)合工程實踐的自動PMA分區(qū)方法，首次將供水管網(wǎng)PMA分區(qū)總結(jié)為3個方面，即分區(qū)數(shù)目、分區(qū)入口和分區(qū)邊界.并運用相應算法解決這3個問題，形成最終的可行方案.

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

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

參考文獻

[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] 崔建國，于慶江，梁海榮. 城市給水系統(tǒng)優(yōu)化調(diào)度中的管網(wǎng)分區(qū)方法[J]. 太原理工大學學報，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)信息化管理與檢測技術(shù)應用研討會論文集. 北京：中國建筑工業(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)化設計兩步法[J]. 哈爾濱工業(yè)大學學報, 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)反問題流失定位[J]. 哈爾濱工業(yè)大學學報，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聚類算法的分析與應用[J]. 吉林建筑大學學報, 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è)大學, 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算法實現(xiàn)對整車配送線路的優(yōu)化[J]. 中國水運(理論版), 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ū)分析中的應用研究[D]. 西安:西安科技大學, 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]張紅娟. 基于非格點模型的蛋白質(zhì)結(jié)構(gòu)預測研究[D]. 大連:大連理工大學, 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)測點布置[J]. 哈爾濱工業(yè)大學學報，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

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

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

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

中圖分類號:TU991

文獻標志碼:A

文章編號: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