07FABIAO枚舉和動(dòng)態(tài)規(guī)劃法在污水管網(wǎng)布局優(yōu)化中的應(yīng)用

枚舉和動(dòng)態(tài)規(guī)劃法在污水管網(wǎng)布局優(yōu)化中的應(yīng)用陳國(guó)棟尹士君湯金如王穎（沈陽(yáng)建筑大學(xué)市政與環(huán)境工程學(xué)院，遼寧，沈陽(yáng)，110168）摘要：用VB語(yǔ)言編寫(xiě)污水管網(wǎng)布局優(yōu)化計(jì)算程序，由污水有向網(wǎng)絡(luò)圖出發(fā)，以污水管網(wǎng)系統(tǒng)費(fèi)用最低為優(yōu)化目標(biāo)，并結(jié)合圖論理論知識(shí)，應(yīng)用枚舉法將污水管網(wǎng)的所有可能布局形式全部列出，同時(shí)利用水力參數(shù)優(yōu)化計(jì)算，進(jìn)行動(dòng)態(tài)規(guī)劃剪枝，選出污水管網(wǎng)最優(yōu)的布局形式及其水力參數(shù)。應(yīng)用結(jié)果表明,該方法可節(jié)省約11.9%的工程總投資,對(duì)實(shí)際工程設(shè)計(jì)具有重要的指導(dǎo)意義。關(guān)鍵詞：污水管網(wǎng)；有向網(wǎng)絡(luò)圖；枚舉法；動(dòng)態(tài)規(guī)劃法；布局優(yōu)化TheOptimizeddistributionofSewagenetworkwithEnumerationAlgorithmandDynamicProgrammingChenGuodong,YinShijun,TangJinru,WangYing(SchoolofMunicipalandEnvironmentalEngineering,ShengyangJianzhuUniversity,Shengyang,Abstract:BasedonVBlanguagethatprogrammestheoptimizeddistributionofsewagenetwork,formdirectedgraphofsewagenetwork,optimalaimisminimalcost,linkgraphtheoryknowledge,applyEnumerationAlgorithmtolistallsewagenetworkdistributionformanduseoptimizedcalculationofhydraulicparameter,makeuseofdynamicprogrammingtocutawaydisadvantageprogramsandselecttheoptimizeddistributionaswellashydraulicparametersofsewagenetwork.Theresultsindicatedthatthemethodismoreeconomicalthanotheroptimizedprogramsabout11.9%,hasimportantguidingsignificancefordesignofactualengineering.Keyword:sewagenetwork;directedgraph;enumerationalgorithm;dynamicprogramming;distributionoptimization污水管網(wǎng)平面布置的優(yōu)化設(shè)計(jì)原則是使管線短，管道工程量最小，水流通暢且節(jié)省能量。正確的定線是合理經(jīng)濟(jì)地設(shè)計(jì)污水管道系統(tǒng)的先決條件，對(duì)不同的定線方案的優(yōu)化選擇更具實(shí)用價(jià)值。目前國(guó)內(nèi)在平面布局優(yōu)化方面已有的研究，大部分是利用圖論知識(shí)，給圖中的線段賦予不同的權(quán)值(通常是管道的費(fèi)用)，運(yùn)用Dijkstra算法和Kruskal算法求得管網(wǎng)布局的最優(yōu)方案。這些研究的不足之處在于：對(duì)污水管網(wǎng)系統(tǒng)，在布局方案沒(méi)有確定的情況下，下游管道的費(fèi)用權(quán)值會(huì)隨上游管道形式的改變而改變，所以它屬于變權(quán)值問(wèn)題。而圖論中，對(duì)于變權(quán)值問(wèn)題現(xiàn)在還沒(méi)有一個(gè)令人滿意的解決方法。因此本文利用枚舉法和動(dòng)態(tài)規(guī)劃法，避開(kāi)了費(fèi)用權(quán)值的問(wèn)題，提出了布局優(yōu)化的新方法。1模型分析及建立根據(jù)污水的排水區(qū)域的情況，可以用有向網(wǎng)絡(luò)圖表示污水的流向關(guān)系。污水管網(wǎng)的布局形式是枝狀的，并且是有向網(wǎng)絡(luò)圖的子圖；由圖論理論知識(shí)，一個(gè)有向圖的子圖的形式是不唯一的，也就是說(shuō)污水管網(wǎng)可行的布局形式是多個(gè)的，而且其數(shù)目的大小與圖的大小成同一增大趨勢(shì)。布局優(yōu)化的方法是利用枚舉法找出有向圖的所有子圖，目標(biāo)就在這些子圖中利用參數(shù)優(yōu)化選擇最優(yōu)的一種，也就是管網(wǎng)布局的最優(yōu)方案[1]。1.1優(yōu)化的思想本程序需要解決兩個(gè)關(guān)鍵問(wèn)題：（1）用枚舉法把污水管網(wǎng)有向圖中所有可行的布局形式全部列出，對(duì)每一種布局形式逐個(gè)進(jìn)行參數(shù)優(yōu)化，而在參數(shù)優(yōu)化中把污水管道每一管段所有可行的方案全部列出，對(duì)這些方案逐個(gè)進(jìn)行水力計(jì)算。（2）利用動(dòng)態(tài)規(guī)劃法對(duì)不優(yōu)的方案進(jìn)行剪除，并對(duì)剩余的優(yōu)化方案進(jìn)行經(jīng)濟(jì)技術(shù)綜合比較，從中列出工程造價(jià)最低的方案就是最優(yōu)布局形式下的最優(yōu)設(shè)計(jì)方案[2]。該方法既可以在所有可行的污水管網(wǎng)布局形式下選出最優(yōu)的布局以及管道的水力參數(shù)，又可以節(jié)省計(jì)算機(jī)的內(nèi)存，從而使普通的PC就可以滿足計(jì)算要求。1.2枚舉布局方案根據(jù)污水管網(wǎng)有向圖的關(guān)系對(duì)原始數(shù)據(jù)作如下假設(shè)：(1)管網(wǎng)中檢查井都抽象為節(jié)點(diǎn)，保留有流量匯入的節(jié)點(diǎn)和地勢(shì)狀態(tài)改變處的節(jié)點(diǎn)，其它節(jié)點(diǎn)不計(jì)；(2)各節(jié)點(diǎn)匯水面積、集中流量、比流量、地面標(biāo)高已知；(3)相鄰節(jié)點(diǎn)之間的地面坡度是常數(shù)；以其兩點(diǎn)的平面距離作為管道的長(zhǎng)度，且為已知量。對(duì)于有p條邊的污水管網(wǎng)有向圖如圖1，根據(jù)圖論中樹(shù)的性質(zhì)，有q個(gè)節(jié)點(diǎn)的樹(shù)，由q-1條邊組成。根據(jù)這個(gè)性質(zhì)，在污水管網(wǎng)有向圖中的所有可能的下游節(jié)點(diǎn)數(shù)目如圖2，它生成的污水管網(wǎng)布局應(yīng)由8根管道組成，而污水管網(wǎng)所有布局形式的個(gè)數(shù)為24=16。運(yùn)用計(jì)算機(jī)求解時(shí)，要把污水有向網(wǎng)絡(luò)圖的信息儲(chǔ)存起來(lái)，有向圖的關(guān)聯(lián)矩陣M是表示圖中節(jié)點(diǎn)關(guān)系的圖表。關(guān)聯(lián)矩陣M=()是一個(gè)m×n階矩陣，m和n分別是上游節(jié)點(diǎn)數(shù)和下游節(jié)點(diǎn)數(shù)。其中Aij=0 上游節(jié)點(diǎn)i和下游節(jié)點(diǎn)j不相接；Aij=1 上游節(jié)點(diǎn)i和下游節(jié)點(diǎn)j第一個(gè)節(jié)點(diǎn)相接；Aij=2 上游節(jié)點(diǎn)i和下游節(jié)點(diǎn)j第二個(gè)節(jié)點(diǎn)相接；Aij=3 上游節(jié)點(diǎn)i和下游節(jié)點(diǎn)j第三個(gè)節(jié)點(diǎn)相接；圖1 污水有向網(wǎng)絡(luò)圖圖2節(jié)點(diǎn)關(guān)聯(lián)矩陣圖Fig．1DirectedgraphofsewagenetworkFig．2Graphofnodeincidencematrix（1）由圖2可以看出節(jié)點(diǎn)1，2，4，5這四個(gè)節(jié)點(diǎn)各有兩個(gè)下游節(jié)點(diǎn)，由于污水管網(wǎng)的性質(zhì)，一個(gè)節(jié)點(diǎn)下游只能有一根管段與之相連接，根據(jù)這個(gè)性質(zhì)和節(jié)點(diǎn)關(guān)聯(lián)矩陣可以把污水管網(wǎng)所有布局形式列出，然后把污水有向網(wǎng)絡(luò)圖（圖1）相應(yīng)的節(jié)點(diǎn)編號(hào)與Aij相對(duì)應(yīng)，得出污水管網(wǎng)的所有布局形式下的上下游節(jié)點(diǎn)編號(hào)；同時(shí)可以根據(jù)每一種布局的上游節(jié)點(diǎn)編號(hào)的個(gè)數(shù)求得節(jié)點(diǎn)上游接管數(shù)。（2）對(duì)每一種布局形式的管網(wǎng)節(jié)點(diǎn)，在遵循下游節(jié)點(diǎn)的編號(hào)要大于其上游所有節(jié)點(diǎn)編號(hào)的原則的基礎(chǔ)上進(jìn)行重新編號(hào)，使編號(hào)符合參數(shù)優(yōu)化計(jì)算的需要。首先從第一個(gè)節(jié)點(diǎn)開(kāi)始遍歷，如果節(jié)點(diǎn)的上游接管數(shù)為0或者其下游節(jié)點(diǎn)的上游接管數(shù)是1，可以從小到大依次編號(hào)，如果上游接管數(shù)大于1時(shí)，則跳過(guò)該節(jié)點(diǎn)，暫不對(duì)該節(jié)點(diǎn)編號(hào)，直到遍歷所有節(jié)點(diǎn)；然后再?gòu)牡谝粋€(gè)節(jié)點(diǎn)開(kāi)始遍歷，對(duì)上游接管數(shù)大于1的節(jié)點(diǎn)，接上次的編號(hào)逐個(gè)進(jìn)行節(jié)點(diǎn)編號(hào)，直到遍歷所有節(jié)點(diǎn)；最后對(duì)沒(méi)有編號(hào)的節(jié)點(diǎn)依次進(jìn)行編號(hào)，直到最后一個(gè)節(jié)點(diǎn)。（3）對(duì)每一種布局形式的管長(zhǎng)、匯水面積、集中流量、地面標(biāo)高等原始參數(shù)，使之與新節(jié)點(diǎn)編號(hào)進(jìn)行對(duì)應(yīng)。對(duì)于某種平面布置方案是否最優(yōu)，取決于該平面布置方案優(yōu)化設(shè)計(jì)計(jì)算結(jié)果，因此已定管線下的參數(shù)優(yōu)化設(shè)計(jì)計(jì)算是平面優(yōu)化布置的基礎(chǔ)。1.3優(yōu)化計(jì)算方案污水管網(wǎng)是一種重力流的枝狀結(jié)構(gòu)，污水管道設(shè)計(jì)計(jì)算是從上游管段開(kāi)始，逐漸向下游遞推的。對(duì)于每一種布局形式下每一根設(shè)計(jì)管段，先選出一個(gè)最小的標(biāo)準(zhǔn)設(shè)計(jì)管徑；計(jì)算當(dāng)前管段的設(shè)計(jì)流量，按最大充滿度進(jìn)行水力計(jì)算，如果流速、埋深、水力坡度等條件不符合要求時(shí)，則進(jìn)行參數(shù)調(diào)整，計(jì)算出管段的第一個(gè)設(shè)計(jì)方案，如此循環(huán)不斷增加管徑計(jì)算新方案，直至新方案的設(shè)計(jì)參數(shù)管徑D、流速v、埋圖5最優(yōu)管網(wǎng)布局圖圖6最劣管網(wǎng)布局Fig．5TheoptimalsewagenetworklayoutFig．6Thetenth-ratesewagenetworklayout程序優(yōu)化總共得出197個(gè)方案，其中每個(gè)布局形式的最優(yōu)方案，計(jì)算結(jié)果如表1所示。而最優(yōu)布局形式為第4布局方案如圖5所示，投資費(fèi)用為46.4549萬(wàn)元；最劣布局形式為第14布局方案如圖6所示，投資費(fèi)用為52.7475元。從優(yōu)化的結(jié)果可得出，利用管網(wǎng)布局優(yōu)化模型得到的最優(yōu)布局與最劣布局的投資費(fèi)用相差達(dá)6.2926萬(wàn)元，相當(dāng)于最劣布局形式投資費(fèi)用的11.9％左右。說(shuō)明采用該方法進(jìn)行污水管網(wǎng)布局優(yōu)化是有效的、經(jīng)濟(jì)的。3．結(jié)論（1）結(jié)合圖論和枚舉法的理論，提出了一種新的優(yōu)化模型。從污水管網(wǎng)的有向網(wǎng)絡(luò)圖出發(fā)，采用枚舉法可以選出污水管網(wǎng)所有布局和參數(shù)的所有可行方案，從而實(shí)現(xiàn)布局優(yōu)化的目的；（2）利用動(dòng)態(tài)剪枝的方法，將造價(jià)、埋深、流速和管徑作為剪枝的限定條件，保留下可能成為最優(yōu)化的設(shè)計(jì)方案，并且可以解決計(jì)算機(jī)內(nèi)存不足的問(wèn)題；（3）該優(yōu)化模型比其他已有布局優(yōu)化方法更全面，更能節(jié)省工程造價(jià)，且設(shè)計(jì)管段愈多，效果愈明顯；（4）該方法同樣也適用于雨水管道和合流制管道的設(shè)計(jì)。參考文獻(xiàn)：[1]楊宏軍、吳學(xué)偉.改進(jìn)單親遺傳算法應(yīng)用于污水管網(wǎng)的布局優(yōu)化[J].廣州大學(xué)學(xué)報(bào)，Vo1.4.No.22005[2]尹士君.利用枚舉和動(dòng)態(tài)規(guī)劃法實(shí)現(xiàn)污水管道的最優(yōu)化設(shè)計(jì)[J].給水排水,Vol.30.No.12.2004[3]嚴(yán)煦世、劉遂慶.給水排水管網(wǎng)系統(tǒng)[M].北京:中國(guó)建筑工業(yè)出版社,2002[4]王之暉等.排水管網(wǎng)系統(tǒng)平面布置的優(yōu)化設(shè)計(jì)研究[J].給水排水,Vol.32No.52006[5]徐俊明.圖論及其應(yīng)用[M].合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社,1998[6