尋夢新聞LINE@每日推播熱門推薦文章，趣聞不漏接❤️
原文題目：Optimization of Potable Water Distribution and Wastewater Collection Networks: A Systematic Review and Future Research Directions
作者：Wanqing Zhao ; Thomas H. Beach ; Yacine Rezgui
第一作者單位：Cardiff School of Engineering, Cardiff University, Cardiff, U.K.
期刊：IEEE Transactions on Systems, Man, and Cybernetics: Systems
發表時間：May 2016
關鍵詞：Artificial intelligence, hydraulics, network optimization, wastewater collection networks (WWCNs), water distribution networks (WDNs)
供水系統和排水系統是複雜的城市用水基礎設施的基本成分。這樣的供水和排水網路需要加以合理的設計以有助於未來的改裝、擴建和維護活動。因此，需要適當的優化方法來降低設計成本，提高效率，同時也需要滿足消費者獲取清潔水和排放廢水的需求。本文首先回顧了對城市供水系統和排水系統所使用的優化手段，然後從城市供水、排水系統的目標和約束出發，對不同的優化方法討論了其複雜性和優缺點，並以此為基礎對未來的優化方法進行了討論。
城市供水系統與排水系統的優化方法複雜而多樣。為了對這些方法進行分析，首先要以一定的方法對各種優化方法進行分類，本文對優化方法的分類如圖1所示。
圖1在給水與排水系統優化中所使用的算法分類
這些優化方法中，傳統的確定性優化方法、現代的元啟發式優化方法與多目標優化方法是在給水系統與排水系統中都得到了廣泛應用。元啟發式優化方法中，又可以細分為兩類：一類在每一步只得到一個解（如模擬退火算法），另一類在每一步都得到一組解（如遺傳算法）。還有一些算法是只在供水系統或是只在排水系統中使用，如分解的優化方法（以Dijkstra最短路徑算法為例）一般只用於供水系統，而直觀的啟發式優化方法（以用於目標檢測的SSD算法為例）一般只用於排水系統。
01
城市供水系統的優化
對於供水系統與排水系統，目前都可以利用各種軟件進行建模並加以分析。建設一套城市供水系統或排水系統，都是在給定了水力學等一系列約束的條件下，通過選取合適的給水/排水系統構建方式（管道、泵站等的設計）以最小的成本滿足各種約束。以城市供水系統為例。其優化方程可以寫作圖2的形式。其中水頭損失可以用海澄-威廉公式進行計算。
圖2城市供水系統的優化方程
圖2中的方程含義如下：
(1)：目標函數（成本）的最小化；
(2)：管道種類的範圍；
(3)(4)：表示每段管道都屬於某一種管道；
(5)：每個節點流量守恒；
(6)(7)：管道中水頭損失的水力學關係；
(8)：水頭損失需要滿足的約束條件。
整體的優化目標便是尋找一種管網設計方式，使得成本最小化。
這個問題可由0-1背包問題多項式歸約得到，因此屬於NP難問題。與此同時，它也是一個非線性的組合最優化問題。傳統的優化算法最早被用來解決該問題，但傳統的優化算法其時間複雜度是管道數量的指數函數；使用線性規劃的方法可以降低複雜度，但其往往無法跳出局部最優解；動態規劃方法在面對環狀管網的計算非常複雜；使用拉格朗日法進行解決，也有可能陷入局部最優。在這樣的情形下，元啟發式算法便發揮了其作用。其中遺傳算法（使用0-1或整數編碼處理離散管徑）及其變種在供水管網的優化中最為常用，蟻群、粒子群、差異演化等算法也在城市供水系統的優化中得到了一些應用，且有部分研究顯示蟻群算法在複雜網路中的表現稍好於遺傳算法。
供水系統優化的另一種思路是將複雜的大網路分解為若干個子網路進行優化，這在漏損控制中十分常見。當考慮多個目標時，多目標優化的方法便需要加以考慮。多目標優化的解常用帕累托前沿面的形式表示，而在供水系統中進行多目標優化則常用各種遺傳算法的變種，如NSGA-II。
目前對於不同的優化算法，尚未對其進行大規模計算分析，以衡量這些算法的時間複雜度差異；這意味著目前尚難以確定尋優效率較高，且計算時間較少的優化算法。
02
城市排水系統的優化
對於城市排水系統，其優化方程更為複雜，可用圖3進行表述。在城市排水系統中，常用曼寧公式計算污水的水力學行為。
圖3城市排水系統的優化方程
在圖3中的方程含義如下：
(1)：目標函數（成本）的最小化；
(2)：管道種類的範圍；
(3)-(5)：每段管道的流量約束；
(6)-(9)：管道節點的高程約束；
(10)：管道的充滿度不能超過最大設定值；
(11)-(13)：檢查井的高程約束。
這一系列的方程都建立在管網最大設計流量的基礎上。
對於城市排水系統的優化設計，離散微分動態規劃化是過去最為常用的傳統優化方法，但是受大型網路的限制，且需要在計算管徑時添加一些與中心角相關的假設。早期的啟發式算法中，則往往對管道中水深與半徑的關係進行了一些假定，導致結果偏離最優解。現代的元啟發式算法中，模擬退火算法、緊急搜尋與元胞自動機都在排水系統的優化中得到了不少應用，而遺傳算法同樣應用廣泛。在城市排水系統的優化中，將精英遺傳算法與自適應遺傳算法相結合的精英自適應遺傳算法有著良好的優化效果。蟻群優化算法也可以用於城市排水系統的優化，但其需要對排水系統優化問題中的一些連續變量（如管道坡度或高程）進行離散化，這使得蟻群優化算法的效果受到了一定影響。粒子群算法的應用較為少見，其在城市排水系統的優化中有一定的發揮潛力。
對於城市排水系統的多目標優化，將元胞自動機與NSGA相結合可以發揮二者的優勢，並規避二者的一些劣勢。使用元胞自動機可以對遺傳算法的局部搜尋能力進行補充，同時又可以利用遺傳算法的全局搜尋能力，從而起到良好的多目標優化效果。在城市排水系統的多目標優化中，目標函數往往為成本與內澇量。
雖然元啟發式算法在解決城市排水系統中有著全局搜尋能力較強，計算複雜度較低等優勢，但由於城市排水系統的問題空間往往特別大，且存在著大量約束，元啟發式算法生成初始可行解的難度往往較高。一種解決方法是將元啟發式算法與傳統優化算法（如二次規劃）相結合，利用傳統優化算法解決一些需要連續優化，且約束較強的部分問題。
03
展望
雖然目前對城市供水系統與排水系統，存在著大量的方法進行優化，但對於這些不同的優化方法，尚缺乏一個有效的平台比較不同方法複雜度。未來可以建立一套問題庫，在問題庫中包含不同類型的城市供水/排水系統，將不同的算法在相同的計算平台上進行大規模計算分析，從而能夠更好地比較不同算法解決不同問題的效率與複雜度。
本文對城市供水系統與排水系統中優化算法的使用現狀進行了綜述，對不同的優化算法進行了分類討論，並關注了這些算法的使用條件與使用方法。在本文最後，作者指出，目前對於這些不同的優化算法，尚缺乏一個通用的有效手段對不同算法的複雜性進行比較，並認為在統一基準上進行的大規模計算分析是一種可行的手段。本文中所提到的不同算法，在未來的研究中可以根據不同的問題加以利用；同時對不同優化算法的複雜性加以評估，也是一個未來可以考慮的方向。
https://ieeexplore.ieee.org/document/7185445/
