李飛宇,石振鋒,吳晨光,于美婷,袁一星
(1.哈爾濱工業(yè)大學(xué)市政環(huán)境工程學(xué)院,150090哈爾濱;2.哈爾濱工業(yè)大學(xué)數(shù)學(xué)系,150001哈爾濱)
配水管網(wǎng)管段改造排序的PageRank算法
李飛宇1,石振鋒2,吳晨光1,于美婷2,袁一星1
(1.哈爾濱工業(yè)大學(xué)市政環(huán)境工程學(xué)院,150090哈爾濱;2.哈爾濱工業(yè)大學(xué)數(shù)學(xué)系,150001哈爾濱)
針對城市配水管網(wǎng)管段改造比選排序問題,提出了基于PageRank的改進(jìn)的MPR-Pipe算法,實現(xiàn)了對管網(wǎng)節(jié)點和管段多種水力屬性的PR值求解.利用經(jīng)濟(jì)流量和管段單位水力坡降PR值,定義了管段改造的重要性度量,并以此作為改造比選排序的依據(jù).理論計算表明該算法求解效率較高,工程應(yīng)用案例表明該算法提出的管段改造比選排序方案有效、可行.
配水管網(wǎng);管段改造;PageRank;單位水力坡降;管段重要性
結(jié)合我國配水管網(wǎng)的實際情況,管網(wǎng)急需改造的原因主要包括:管網(wǎng)設(shè)備陳舊與老化;管網(wǎng)運行負(fù)荷較重;管網(wǎng)布局欠合理;水源新建及改造;更高的水質(zhì)安全需求;節(jié)能降耗.因此,在對供水管網(wǎng)進(jìn)行改造過程中應(yīng)用管網(wǎng)水力模型,分析供水管網(wǎng)的工況,合理地對供水管網(wǎng)進(jìn)行改造,特別是通過優(yōu)化管網(wǎng)改造的順序可以節(jié)約投資,最大限度地降低能量消耗,而且可以提高整個供水系統(tǒng)的安全性能,對于企業(yè)和社會都具有重要意義.為此,國內(nèi)外開展了管網(wǎng)改造方面的研究,主要包括:管段老化模型研究[1]、管網(wǎng)運行現(xiàn)狀模型研究[2-3]、管網(wǎng)運行成本模型研究[4]及管網(wǎng)改造決策模型研究[5-6],其中管網(wǎng)改造決策模型的建立與求解是最主要的研究方向,其結(jié)果可以直接指導(dǎo)管網(wǎng)改造問題[7].管段老化模型、管網(wǎng)運行現(xiàn)狀分析、管段運行成本經(jīng)濟(jì)型分析,一般在構(gòu)建和求解管網(wǎng)改造決策模型中起輔助作用[8].同時,國內(nèi)外還建立了多種優(yōu)化改造模型用于管網(wǎng)的改造,如基于多目標(biāo)優(yōu)化的管網(wǎng)改造決策模型[6]、基于遺傳算法的管網(wǎng)優(yōu)化模型[9].這些模型建模的思想、形式、復(fù)雜程度差異性較大,各有側(cè)重.
賦予靜態(tài)屬性和動態(tài)的狀態(tài)屬性后的供水管網(wǎng)在應(yīng)用過程中可抽象為網(wǎng)絡(luò).管網(wǎng)改造過程中管段的排序問題即可轉(zhuǎn)化為網(wǎng)絡(luò)中對連接邊的排序問題.Google網(wǎng)頁搜索過程中,通過網(wǎng)頁間的鏈接來評價網(wǎng)頁的重要性,這就是Google網(wǎng)頁搜索引擎中的核心算法——PageRank算法[10].隨著對 PageRank算法的廣泛研究,其不僅在自身網(wǎng)頁排序中應(yīng)用效果顯著,在很多領(lǐng)域都得到了應(yīng)用,如圖書管推薦技術(shù)、網(wǎng)絡(luò)安全評估、Web數(shù)據(jù)挖掘等.借鑒PageRank算法在其他行業(yè)中的應(yīng)用,利用管網(wǎng)改造管段排序問題和網(wǎng)頁排序問題的相似性,將PageRank算法引入城市配水管網(wǎng)改造的應(yīng)用中目前未見報道.本文首先介紹了PageRank算法,并評述了其優(yōu)缺點.結(jié)合城市配水管網(wǎng)的特殊性,提出了適于管網(wǎng)改造排序應(yīng)用的改進(jìn)的PageRank算法,并定義了管段的重要性度量,進(jìn)而給出管段改造排序的計算方法.最后,根據(jù)管段排序的結(jié)果并通過實例驗證,表明該算法描述管段重要性度量的定義是合理的、可行的,可為城市配水管網(wǎng)提供可行的科學(xué)改造方案.
1.1 PageRank算法簡介
PageRank算法是Google網(wǎng)頁搜索引擎中的核心算法,由Google的創(chuàng)始人Sergey Brin和Lawrence Page[10]于1998年提出并得到了成功應(yīng)用.其基本思想主要來自傳統(tǒng)文獻(xiàn)計量學(xué)中對文獻(xiàn)引用的研究和分析[11],即一篇文獻(xiàn)被其他文獻(xiàn)引用的越多,說明文獻(xiàn)的質(zhì)量就越高.假設(shè)網(wǎng)頁A鏈接網(wǎng)頁B,則可看作是網(wǎng)頁A對網(wǎng)頁B進(jìn)行投票,根據(jù)投票數(shù)來判斷網(wǎng)頁的重要性(PageRank值,簡稱PR值).PageRank技術(shù)根據(jù)整個Web的鏈接結(jié)構(gòu)來計算各個網(wǎng)頁的重要性值,構(gòu)造有向網(wǎng)頁圖G=<V,E>,其中頂點V為所有的網(wǎng)頁集合,邊 E為網(wǎng)頁中所有的鏈接集合,網(wǎng)頁A存在一條指向網(wǎng)頁B的鏈接即表示為網(wǎng)頁有向圖的邊E.PageRank算法的基本定義為
1.2 PageRank算法的不足
PageRank算法在Web頁面重要性應(yīng)用中存在兩個主要的不足,即P R值沉淀現(xiàn)象和“黑洞效應(yīng)”.在多個網(wǎng)頁彼此鏈接后形成的有向圖中,當(dāng)網(wǎng)頁鏈接形成的有向圖之外的網(wǎng)頁鏈接到該有向圖內(nèi)部的網(wǎng)頁時,就會出現(xiàn)有向圖內(nèi)部網(wǎng)頁傳遞不出去PR值而導(dǎo)致傳遞進(jìn)來的PR值一直滯留在此有向圖內(nèi)部,即PR值沉淀現(xiàn)象.圖 1解釋了該現(xiàn)象.在圖1中,網(wǎng)頁A、B、C、D內(nèi)部相互鏈接,無向外鏈接,網(wǎng)頁E、F分別鏈接網(wǎng)頁B和D,在應(yīng)用PageRank算法進(jìn)行迭代計算中,網(wǎng)頁E、F的PR值不能在網(wǎng)頁A、B、C、D形成的組內(nèi)貢獻(xiàn)出去而出現(xiàn)沉淀的現(xiàn)象.為此,Sergrey Brin和Law Page對PageRank算法進(jìn)行改進(jìn)[13],引入衰退因子D(Pi),對應(yīng)某一網(wǎng)頁的初始PR值,改進(jìn)算法即
其中‖P R(Pi)‖=1.
在求解式(2)描述的方程組時,其收斂性問題是關(guān)鍵.對于連通的有向Web圖G=<V,E>,設(shè)其中某個頂點的入度為0,由于其沒有對外貢獻(xiàn)PR值,P R值會逐漸減少,經(jīng)過有限次迭代之后,該連通圖內(nèi)所有頂點的PR值將全部為0,這就是PageRank算法存在的“黑洞效應(yīng)”,即入度為0的頂點就像黑洞一樣,將整個有向圖內(nèi)的P R值全部慢慢“吸收”.然而,針對“黑洞效應(yīng)”,Google并沒有公布其處理辦法,有些研究者認(rèn)為可以將Web有向圖內(nèi)所有的網(wǎng)頁均作為入度為0網(wǎng)頁的鏈接,這樣就能有效避免“黑洞效應(yīng)”.
針對PageRank算法存在的上述兩個不足,在管段排序應(yīng)用中,應(yīng)該根據(jù)給水管網(wǎng)的實際特點,對PageRank算法進(jìn)行適當(dāng)改進(jìn).
2.1 改進(jìn)的PageRank算法——MPR-Pipe
為將PageRank算法更好地應(yīng)用在給水管網(wǎng)的管段改造排序問題,對PageRank算法作如下兩點改進(jìn):
1)在網(wǎng)頁模型中,網(wǎng)頁的屬性值只體現(xiàn)了鏈接數(shù),各個鏈接只是數(shù)值上平分此網(wǎng)頁的PR值.給水管網(wǎng)中,每個管段具有更多實際意義的屬性值,如流量、流速、單位水頭損失等,不同的管段屬性值對管段的最終改造排序結(jié)果有重要的影響,因此,在管網(wǎng)模型中應(yīng)以管段屬性信息值的比例來分配該管網(wǎng)節(jié)點的PR值.本文選用單位水力坡降.
2)根據(jù)PageRank算法的介紹,由式(1)可知,PageRank的名次和該網(wǎng)頁被鏈接的數(shù)目基本一致,無論該網(wǎng)頁鏈接多少網(wǎng)頁均幾乎不會影響PR值.相反有多少網(wǎng)頁鏈接該網(wǎng)頁從根本上決定網(wǎng)頁P R值的大小.本文提出對管段進(jìn)行排序的改進(jìn)的PageRank算法由管網(wǎng)節(jié)點的正向鏈接和反向鏈接共同決定,這種改進(jìn)一方面結(jié)合了管網(wǎng)模型的實際情況,另一方面也有效地避免了在網(wǎng)頁模型中PageRank算法存在的沉淀現(xiàn)象和“黑洞效應(yīng)”.
記I(Ji,Jj)為管網(wǎng)節(jié)點Ji到節(jié)點Jj的單位水頭損失,I(:,Ji)為所有流入節(jié)點Ji,并與節(jié)點Ji鏈接的節(jié)點構(gòu)成的Ji單位水頭損失總和,I(Ji,:)為流出節(jié)點Ji,與節(jié)點Ji鏈接的節(jié)點構(gòu)成的Ji單位水頭損失總和.在節(jié)點總數(shù)為NJ的給水管網(wǎng)中,改進(jìn)的PageRank算法(modified PageRank for pipe,MPRPipe)可以概括為如下線性方程:
式中:i=1,2,...,NJ;
In(Ji)為流入管網(wǎng)節(jié)點 Ji的管網(wǎng)節(jié)點集合;Out(Ji)為從管網(wǎng)節(jié)點Ji流出的管網(wǎng)節(jié)點集合;c1和c2分別為流入與流出權(quán)重系數(shù)(介于0~1的常數(shù)),且c1+c2=1;d為阻尼因子,用于保證線性方程(3)的收斂性.
2.2 管段重要性度量的定義
通過方程組(3)求得供水管網(wǎng)中每個節(jié)點在流量、絕對水頭和自由水頭等屬性上的PR值.然而,管網(wǎng)改造過程中都是基于管段進(jìn)行的,因此,需要利用每個節(jié)點的PR值定義管段重要性的度量.考慮到管段的單位水力坡降和流量是刻畫管段輸水能力和經(jīng)濟(jì)指標(biāo)計算時的重要指標(biāo),本文將結(jié)合管段的單位水力坡降和實際計算流量與經(jīng)濟(jì)流量之間的關(guān)系來定義管段的重要性.設(shè)連接管段Pi的兩個節(jié)點分別為和的實際計算流量為,其經(jīng)濟(jì)流量為.則定義管段改造的重要性程度為
其中e1+e2=1.本文取e1=e2=0.5,利用供水管網(wǎng)中管段的單位水力坡降屬性來定義管段重要性度量,并稱為管段的PR值.由式(4)可以看出,當(dāng)管道實際流量越大于經(jīng)濟(jì)流量時,管段的PR值就越大,據(jù)此排序在前,表明管段越急需改造,因此,式(4)具有明顯的物理意義.該PR值標(biāo)明了所有管段改造的順序(不考慮管段改造的經(jīng)濟(jì)成本等因素).當(dāng)實際流量遠(yuǎn)小于經(jīng)濟(jì)流量時,從物理意義上講也急需改造.在實際工程應(yīng)用中,對這種管道的改造一般采用關(guān)閥改變供水管網(wǎng)邏輯拓?fù)浣Y(jié)構(gòu),或調(diào)整閥門開度改變這部分管道的水力工況狀態(tài)等方案來實現(xiàn)管網(wǎng)的改造,不在本文的討論范圍之內(nèi).
2.3 MPR-Pipe算法的數(shù)值求解
給定管網(wǎng)有向圖G=<V,E>,定義管網(wǎng)的鄰接矩陣P,若管段i鏈接管段j,且水流方向為從管段i到管段j,則Pi,j=I(Ji,Jj),否則Pi,j=0.即
其中m=m(x)=(I-d)eTx=(I-d)‖x‖1為常數(shù),于是可將式(6)簡化成線性方程組.記B=I-d(c1P1+ c2P2T),m=(I-d)v,則式(6)的求解過程轉(zhuǎn)化為對線性方程組(8)的求解,即
注意到管網(wǎng)中的節(jié)點數(shù)量通常較大,基于高斯消元法進(jìn)行求解效率較低.為此,本文采用Jacobi迭代法,建立迭代公式
則MPR-Pipe算法轉(zhuǎn)換后的等效線性方程組Bx=m的Jacobi迭代矩陣為
綜上,MPR-Pipe算法可描述為
算法1面向管段改造排序的改進(jìn)的PageRank算法
Input管網(wǎng)水力計算結(jié)果數(shù)據(jù)文件;阻尼因子d;流入和流出權(quán)重系數(shù)c1,c2;迭代終止精度ε;最大迭代次數(shù)MAX_Iter;
Output城市供水管網(wǎng)管段和節(jié)點的PR值;
Step 1讀取供水管網(wǎng)水力計算結(jié)果數(shù)據(jù)文件;
Step 2建立管段鄰接關(guān)系矩陣A_E;
Step 3由流入和流出權(quán)重系數(shù)c1,c2,建立與鄰接矩陣A_E相關(guān)的水力工況參數(shù)系數(shù)矩陣C_E;
利用線性方程組的Jacobi數(shù)值求解算法求解公式(6);
ifδ<εgoto Step 5;
end
Step 5根據(jù)節(jié)點的PR值,計算管段的PR值;Step 6保存管段和節(jié)點的PR值信息為數(shù)據(jù)文件.
3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計
設(shè)計如下數(shù)據(jù)結(jié)構(gòu)實現(xiàn)MPR-Pipe算法:
■節(jié)點的數(shù)據(jù)結(jié)構(gòu)描述如下:
struct NODE{ //節(jié)點結(jié)構(gòu)
long innNo;//內(nèi)部編號
double dFlow_PR; //流量PR值
double dSpeed_PR; //流速PR值
double dFall_PR; //壓降PR值
};
■管段的數(shù)據(jù)結(jié)構(gòu)描述如下:
struct PIPE{ //管段結(jié)構(gòu)
long innNo; //內(nèi)部編號
long from_innNo; //流出節(jié)點內(nèi)部編號
long to_innNo; //流入節(jié)點內(nèi)部編號
double dFlow_PR; //流量PR值
double dSpeed_PR; //流速PR值
double dFall_PR; //壓降PR值
double dFall_1000_PR;//單位水損PR值
};
■管網(wǎng)拓?fù)浣Y(jié)構(gòu)描述如下:
typedef struct ADJACENT_ELEMENT {
int no;
PIPE?pipe;
}A_E;
typedef struct COEFFICIENT_ELEMENT {
int col;
double value;
}C_E;
typedef struct WaterPipeNet {
vector<PIPE>pipe_list; //管段數(shù)組.
vector<NODE>node_list; //節(jié)點數(shù)組.
vector<vector<A_E>>row_type;//鄰接矩陣
vector<vector<A_E>>col_type;//鄰接矩陣
vector<vector<C_E>>cem;//系數(shù)矩陣
}GRAPH;
3.2 計算實例及分析
本文基于Embarcadero RAD XE 5平臺,利用C++編程實現(xiàn)了MPR-Pipe算法.以北方某市部分管網(wǎng)為例進(jìn)行了仿真計算和分析,其管網(wǎng)拓?fù)淙鐖D2所示.
在該管網(wǎng)拓?fù)浣Y(jié)構(gòu)中,由291條管段、259個節(jié)點及6個水廠構(gòu)成.在水力計算過程中,共計算了24個時段,水力計算的邊界約束不做列出.利用本文的MPR-Pipe算法針對該管網(wǎng)24個時段水力計算結(jié)果中的管段流量、流速、水頭損失和單位水頭損失等動態(tài)水力屬性分別進(jìn)行求解,花費的總計算時間為0.058 s.圖3給出了上述管網(wǎng)在23時、9時、14時和18時的管段改造重要性排序示意圖.
圖3中4個子圖中共標(biāo)識了8條管段,其在24個時段中,有超過18個時段均具有較大的P R值.也就是說,從管段改造應(yīng)用的意義上看,這8條管段為急需改造的管段,也是上述管網(wǎng)中的較“薄弱”管段.對于具有相同管材的管段,其阻力系數(shù)C值會隨著敷設(shè)年代的增加而逐漸變小,在相同的用水形式下,其單位管段水力坡降也會變大.根據(jù)管段重要性的定義,對于單位水力坡降較大的管段,如果計算得到的流量小于經(jīng)濟(jì)流量的管段,則其重要性將按照指數(shù)級(小于1)平緩;對于實際計算流量大于經(jīng)濟(jì)流量的管段,其重要性將按照指數(shù)級(大于1)提升,從而加速這部分管段的排序,成為急需改造的管段.
3.3 MPR-Pipe算法與傳統(tǒng)分析方法的比較
為了驗證本文算法的合理性和有效性,以高日高時為水力計算的基本工況,與傳統(tǒng)的管段運行負(fù)荷計算方法[14]得到的結(jié)果進(jìn)行了比較,結(jié)果如圖 4所示.其中管段運行負(fù)荷中的經(jīng)濟(jì)指標(biāo)等因素與本文中計算經(jīng)濟(jì)流量時設(shè)定的參數(shù)相同.可以看出,本文得到的8條急需改造的管段,其運行負(fù)荷普遍高于其他管段.在這一點上本文定義的重要性較好地包括了傳統(tǒng)的管段運行負(fù)荷分析的范疇.然而,在運行負(fù)荷分析方法中,有較多的管段處于略低負(fù)荷、經(jīng)濟(jì)負(fù)荷及略超負(fù)荷等,尚不能較好地給出管段改造的排序結(jié)果.本文提出的管段重要性度量可較好地對運行負(fù)荷偏高的管段實現(xiàn)數(shù)值上較大范圍的放大,而運行負(fù)荷較低的管段則實現(xiàn)了數(shù)值上較大范圍的縮小,從而可更有效地實現(xiàn)管段重要性兩個不同層級上的區(qū)分,也更有利于快速實現(xiàn)急需改造管段的選擇.因此,從傳統(tǒng)的管段改造角度看,本文算法得到的排序結(jié)果要優(yōu)于通過管段運行負(fù)荷分析得到的改造的管段集合.
綜上,本文提出的改進(jìn)的PageRank算法快速地實現(xiàn)了對管段改造方案的比選排序,該排序結(jié)果綜合反映了管段的單位水頭損失和經(jīng)濟(jì)流量的情況.對于敷設(shè)年代較久遠(yuǎn)的管段,因其單位水力坡降較大而可能成為排序中急需改造的管段.本文算法得到的排序結(jié)果已成功應(yīng)用于該城市這部分供水管網(wǎng)的實際改造.由于管徑的優(yōu)化選擇不在本文的討論范圍之內(nèi),這里僅給出了需要改造管段的優(yōu)先順序,而未給出這些管段改造后的管徑選擇方案.
1)基于PageRank算法,提出了面向城市配水管網(wǎng)改造管段排序應(yīng)用的改進(jìn)的 PageRank算法——MPR-Pipe算法.
2)基于MPR-Pipe算法,定義了管段改造排序的重要性度量——管段改造的PR值.
3)基于管段改造的PR值得到管段改造排序方案,實現(xiàn)了對北方某城市部分管網(wǎng)的實際改造應(yīng)用,表明本文的方法具有實用的工程意義和理論意義.
[1]WATSON T,MASON A.A hierarchical Bayesian model for the maintenance of water pipe networks[C]//Proceedings of the 7“International Conference on Hydroinfor-Matics.France:Nice,2006:2991-2998.
[2]GYERGYEK L,PERSEN S.Simulation and optimal control of large water distribution systems[J].Mathematics and Computers in Simulation,1982,96(2):214-216
[3]舒詩湖,何文杰,趙明,等.供水管網(wǎng)漏失檢測技術(shù)現(xiàn)狀與進(jìn)展[J].給水排水,2008,34(6):114-116.
[4]SAVIC D A,WALTERS G A.Genetic algorithms for least-cost design of water distribution networks[J].Journal of Water Resources Planning and Management,1997,123(2):67-77.
[5]MALM A,SVENSSON G,B?CKMAN H,et al.Prediction of water and wastewater networks rehabilitation based current age and material distribution[J].Water Science&Technology:Water Supply,2013,13(2):23-28.
[6]ROSHANI E,F(xiàn)ILION Y R.Multi-objective rehabilitation planning of water distribution systems under climate change mitigation scenarios [J]. Bridges,2014,10:9780784412312.321.
[7]SARGAONKAR A,KAMBLE S,RAO R.Model study for rehabilitation planning of water supply network[J].Computers,Environment and Urban Systems,2013,39:172-181.
[8]BEALE D J,MARLOW D R,COOK S.Estimating the cost and carbon impact of a long term water main rehabilitation strategy[J].Water Resources Management,2013,27(11):3899-3910.
[9]KANTA L,ZECHMAN E,BRUMBELOW K.Multiobjective evolutionary computation approach for redesigning water distribution systems to provide fire flows[J].Journal of Water Resources Planning and Management,2011,138(2):144-152.
[10]BRIN S,PAGE L.The anatomy of a large-scale hypertextual web search engine[J].Computer Networks and ISDN Systems,1998,30(1):107-117.
[11]GIBSON D.Device discovery and power management in embedded systems[C]//Proceedings of the Linux Symposium 2003.Ottawa:[s.n.],2003:213-224.
[12]AUSTIN D.How Google finds your needle in the web’s haystack[J].American Mathematical Society Feature Column,2006,10:12.
[13]PAGE L,BRIN S,MOTWANI R,et al.The PageRank citation ranking:bringing order to the web[J].Stanford Infolab,1999,9(1):1-14.
[14]趙洪濱.給水管網(wǎng)系統(tǒng)理論與分析[M].北京:中國建筑工業(yè)出版社,2003:312-313.
(編輯 劉 彤)
PageRank-based selection sort of pipe renewal in water distribution system
LI Feiyu1,SHI Zhenfeng2,WU Chenguang1,YU Meiting2,YUAN Yixing1
(1.School of Municipal and Environmental Engineering,Harbin Institute of Technology,150090 Harbin,China;2.Department of Mathematics,Harbin Institute of Technology,150001 Harbin,China)
A novel modified Page Rank algorithm for pipe renewal(MPR-Pipe)is presented to realize selection sort and provide Page Rank values of static and dynamic attributions of junctions and pipes in water distribution systems.The measurement of pipe renewal significance,well defined on the grounds of economic flow and unit hydraulic gradient,can be taken as the criterion for the selection sort of pipe renewal.Theoretical calculations confirm the high efficiency of the algorithm,and engineering application cases indicate the effectiveness and feasibility of the renewal plan based on MPR-Pipe algorithm.
water distribution system;pipe renewal;PageRank;unit hydraulic gradient;pipe significance
TU821.3
A
0367-6234(2015)08-0025-05
10.11918/j.issn.0367-6234.2015.08.006
2014-06-20.
國家自然科學(xué)基金(51178141);水體污染控制與治理科技重大專項(2012ZX07408-002-004-002).
李飛宇(1981—),男,博士研究生;袁一星(1957—),男,教授,博士生導(dǎo)師.
吳晨光,wu.cg@126.com.