基于風險預(yù)警-遺傳算法耦合的河道水利工程設(shè)施巡查路線規(guī)劃研究

摘 要：傳統(tǒng)的河道水利工程設(shè)施巡查選點及路線規(guī)劃高度依賴工作人員從業(yè)經(jīng)驗，容易造成巡查選點覆蓋面不足，不能及時發(fā)現(xiàn)河道水利工程設(shè)施問題，因此如何開展河道巡查路線規(guī)劃，合理規(guī)劃巡河路線，實現(xiàn)對存在風險隱患的水利工程設(shè)施巡查更廣泛的覆蓋面以及更高效的巡查效率很有必要?；陲L險預(yù)警-遺傳算法耦合的方法，研究建立河道水利工程設(shè)施風險預(yù)警模型與河道巡查路線規(guī)劃模型，實現(xiàn)了對河道水利工程設(shè)施巡查路線規(guī)劃。中河道水利工程設(shè)施風險預(yù)警模型采用熵權(quán)-Topsis方法計算得出巡查對象風險等級，通過耦合基于遺傳算法的河道巡查路線規(guī)劃模型，以巡查對象風險等級作為河道巡查路線規(guī)劃模型輸入數(shù)據(jù)，最終求解出河道巡查路線。通過在廣州市河涌監(jiān)測中心日常巡河作業(yè)實踐應(yīng)用證明，基于風險評估-遺傳算法耦合方法規(guī)劃的巡河路線較傳統(tǒng)經(jīng)驗路線更合理，在風險設(shè)施巡查覆蓋面及巡查時間效率上都有更佳的表現(xiàn)。

關(guān)鍵詞：風險預(yù)警；路線規(guī)劃；河道巡查；水利工程設(shè)施

中圖分類號：TV1 文獻標識碼：A 文章編號：1001-9235（2024）09-0110-08

1 研究背景

近年來，廣東各地在加大河長制、湖長制激勵問責方面創(chuàng)新方式方法，有效促進各級河長湖長和責任部門履職盡責，為了提高河道巡查效率，廣州市河涌監(jiān)測中心通過建立基于河道巡查工作的河道及附屬設(shè)施風險預(yù)警模型、河道巡查路線規(guī)劃模型，持續(xù)推進差異化巡河機制的技術(shù)應(yīng)用和治理探索。

河道水利工程設(shè)施巡查是保障水利工程安全運行的重要工作，是河道管理的重要組成部分，如何對現(xiàn)場巡查現(xiàn)狀快速做出決策，促進決策人員對河道水利工程設(shè)施巡查規(guī)劃功能加強的需求日益增加。因此，更加先進的規(guī)劃策略引進將會給巡查工作帶來更大的優(yōu)勢。

目前傳統(tǒng)的河道水利工程設(shè)施巡查選點及路線規(guī)劃高度依賴工作人員從業(yè)經(jīng)驗，容易造成巡查選點覆蓋面不足，不能及時發(fā)現(xiàn)河道水利工程設(shè)施問題。為此，有必要開展河道巡查路線規(guī)劃研究，合理規(guī)劃巡河路線，實現(xiàn)對存在風險隱患的水利工程設(shè)施巡查更廣泛的覆蓋面以及更高效的巡查效率。

河道水利工程設(shè)施巡查路線規(guī)劃問題類似于旅行商（Travelling Salesman Problem， TSP）［1-2］問題，是組合優(yōu)化領(lǐng)域的典型問題，TSP一直以來都是計算機科學中的熱門研究課題，描述為1個商人從任意城市出發(fā)，不重復不遺漏地訪問每一個城市，最后返回出發(fā)地，其目標是找出一條包含所有城市的最短路徑。

目前求解旅行商問題的算法有多種，主要可分為兩類，分別為精確算法和啟發(fā)式算法。精確算法能夠得出旅行商問題的最優(yōu)解，但是隨著要求的問題規(guī)模變大，精確算法的時間復雜度也迅速增加，因此，使用啟發(fā)式算法求解旅行商問題是目前的1個熱點研究方向。關(guān)于求解TSP方面，學者們已開展了大量的研究，比如2020年，Cinar等［3］重新設(shè)計基本TSA，解決了置換編碼的優(yōu)化問題，提出了DTSA來解決TSP。2022年，Zhang等［4］提出了DSSA算法，該算法設(shè)計了一種全局擾動策略，DSSA算法在求解TSP 中具有較強的競爭性和魯棒性。2022年，Skinderowicz［5］提出了FACO算法，該算法在求解大規(guī)模實例時，性能優(yōu)于目前的許多ACO算法。

目前，解決TSP已經(jīng)存在了許多成熟的算法，這些算法能夠在較短的時間內(nèi)求得TSP較優(yōu)的近似解或者最優(yōu)解。然而，隨著TSP數(shù)據(jù)規(guī)模的增大，這些算法的效率和性能也會遇到一些瓶頸，例如求解時間變長或者陷入局部最優(yōu)解。因此，在這些算法的基礎(chǔ)上，科學家們也著重于研究進一步提高算法的求解速度和求解質(zhì)量，以此來滿足日益增長的數(shù)據(jù)規(guī)模。

2 技術(shù)路線

河道水利工程設(shè)施巡查路線規(guī)劃［6-9］問題類似于旅行商問題［10-11］，是組合優(yōu)化領(lǐng)域的典型問題。TSP可描述為1個商人從任意城市出發(fā)，不重復不遺漏地訪問每一個城市，最后返回出發(fā)地，其目標是找出一條包含所有城市的最短路徑。

河道水利工程設(shè)施巡查路線規(guī)劃問題有別于一般TSP，一般TSP的假設(shè)前提是每個需要經(jīng)過的“城市”重要性權(quán)重都是一樣的。河道水利工程設(shè)施巡查路線規(guī)劃問題則需要考慮水利工程設(shè)施風險等級，風險等級越高，需要巡查的概率應(yīng)越高。以此，在求解TSP前，首先需要正確評估水利工程設(shè)施風險等級［12］。

本研究首先通過熵權(quán)-Topsis方法確定水利工程設(shè)施風險等級，然后通過遺傳算法求解最優(yōu)巡查路線，具體技術(shù)路線框架，見圖1。

3 模型建立

3. 1 風險預(yù)警模型

本次河道水利工程設(shè)施風險評估模型主方法采用熵權(quán)-Topsis方法［13］計算風險權(quán)重和巡查對象風險等級，利用層次分析法（Analytic HierarchyProcess，AHP）進行調(diào)權(quán)擬合，增強模型泛化使用效果，進一步用K-means無監(jiān)督學習方法［14-15］計算出河道及附屬設(shè)施風險等級劃分結(jié)果。

河道及附屬設(shè)施風險預(yù)警模型通過對風險等級進行分類，定義風險等級分別為一般風險（1級）、較大風險（2級）、重大風險（3級）、特大風險（4級）。不同的風險等級對應(yīng)的標識定義，見表1。

風險預(yù)警模型通過河道及附屬設(shè)施巡查發(fā)現(xiàn)的歷史問題數(shù)據(jù)，定義風險相關(guān)評價指標，計算各評價指標的信息熵，確定指標權(quán)重，以關(guān)聯(lián)河道堤防、水閘、泵站的空間位置為建模特征、河道及附屬設(shè)施風險等級為標簽的模型訓練數(shù)據(jù)，通過聚類算法，進一步計算風險評價分值，最后通過聚類算法劃分巡查對象的風險等級。模型中K-means 聚類算法模型特征及數(shù)據(jù)輸入，見表2。

3. 2 巡查路線規(guī)劃模型

本次研究中，根據(jù)水利工程風險等級、巡查頻率、巡查時長、水利工程地理空間分布等因素，應(yīng)用遺傳算法（Genetic Algorithm），求解河道巡查路線規(guī)劃問題。遺傳算法是一種模擬自然進化過程的優(yōu)化算法，其原理基于達爾文的進化論和遺傳學理論，它通過模擬自然界中的遺傳操作，逐代進化搜索解空間中的最優(yōu)解。本研究中，應(yīng)用遺傳算法流程如下。

a）初始化種群。首先，生成一個初始的種群，其中每個個體代表問題的一個潛在解。這些個體可以通過隨機生成、或者根據(jù)先驗知識創(chuàng)建，每個基因?qū)?yīng)1個參數(shù)值，初始化t←0進化代數(shù)計數(shù)器，隨機生成M 個個體作為初始群體P（t），例如x1、x2、x3等。

b）適應(yīng)度評估。對于每個個體，定義一個適應(yīng)度函數(shù)來評估其在解空間中的優(yōu)劣程度，計算P（t）中各個個體的適應(yīng)度值。

c）選擇操作。通過選擇操作，從當前種群中選擇一部分優(yōu)秀的個體作為父代用于繁殖下一代。

d）交叉操作。在交叉操作中，從選擇的父代中選擇2個個體，通過某種方式對它們的基因進行交叉，生成新的個體。交叉的方式可以是單點交叉、多點交叉、均勻交叉等。

e）變異操作。變異操作是為了引入種群中的多樣性，防止陷入局部最優(yōu)解。在變異操作中，對新生成的個體進行基因的隨機變化，通常是通過隨機改變某些基因值或位置，并通過以上運算得到下一代群體P（t+1）。

f）形成新種群。通過選擇、交叉和變異操作，形成新的種群。新種群中包含父代中的一部分個體以及通過交叉和變異操作生成的新個體。

g）重復迭代。重復進行選擇操作、交叉操作、變異操作、形成新種群，直到滿足終止條件。終止條件可以是達到一定的迭代次數(shù)、找到滿意的解，或者適應(yīng)度達到某個閾值等。

h）輸出結(jié)果。輸出最優(yōu)解及其適應(yīng)度值。

4 模型實踐與應(yīng)用

4. 1 風險預(yù)警模型應(yīng)用

本次研究中，針對廣州市河涌監(jiān)測中心河道巡查范圍內(nèi)1 817條河道、3 273個堤防、1 177個水閘、868個泵站、298座水庫作為巡查對象，巡查范圍內(nèi)水利設(shè)施的位置分布，見圖2。

按照每月選取總量3%的設(shè)施進行巡查，對上述水利工程設(shè)施數(shù)據(jù)及歷史問題數(shù)據(jù)進行業(yè)務(wù)屬性分析。其中，業(yè)務(wù)屬性以四大維度進行分類，分別為巡查記錄、問題隱患發(fā)現(xiàn)、問題整改/辦結(jié)情況及問題逾期未辦結(jié)情況。在四大維度基礎(chǔ)上，定義13個評估指標指標，分別為距離上一次巡查相隔月數(shù)、歷史巡查問題發(fā)現(xiàn)頻率、上年度巡查發(fā)現(xiàn)問題平均數(shù)、嚴重及以上問題數(shù)、較重問題數(shù)、一般問題數(shù)、在規(guī)定時間內(nèi)未辦結(jié)問題數(shù)、距離最近一次未辦結(jié)問題相隔天數(shù)、逾期未辦結(jié)總數(shù)、逾期0. 5～1 a未辦結(jié)數(shù)、逾期1～2 a未辦結(jié)數(shù)、逾期2 a以上未辦結(jié)數(shù)、嚴重及以上問題逾期未辦結(jié)數(shù)。各指標權(quán)重，見表3。

本次研究中，預(yù)先設(shè)定的4個類別數(shù)量，采用熵權(quán)-Topsis 方法對上述13 個指標進行風險權(quán)重計算。根據(jù)獲得的標準化矩陣和各指標權(quán)重計算加權(quán)標準化矩陣，通過定義正負理想解（正理想解和負理想解分別為各指標在標準化矩陣中的最大值和最小值），分別計算評價對象各評價指標與正負理想解的歐氏距離。根據(jù)各評價對象與正負理想解的距離即相對接近程度，計算綜合評價值得到風險評價分值，再利用層次分析法［16］進行調(diào)權(quán)擬合，從而增強模型泛化使用效果。再通過K-means 無監(jiān)督學習方法計算出每個類別的數(shù)據(jù)中心，Kmeans算法通過最小化每個類別內(nèi)數(shù)據(jù)點的方差，即將數(shù)據(jù)點與其所屬類別中心的距離最小化，以確保每個數(shù)據(jù)點都屬于距離其最近的類別中心為目標進行迭代，得出對應(yīng)于4個類別的聚類結(jié)果以及其分值劃分范圍，分別為：0～0. 044、>0. 044～0. 105、>0. 105～0. 248、0. 248以上。計算結(jié)果見表4。

結(jié)合水利工程GIS空間位置信息與風險等級對應(yīng)的標識定義，生成河道水利工程設(shè)施風險評估計算結(jié)果分布，見圖3。

4. 2 巡查路線規(guī)劃應(yīng)用

首先通過結(jié)合根據(jù)水利工程風險等級，水利工程地理空間分布等因素，采用單鏈層次聚類的方法組織巡查任務(wù)包。研究中，依托單鏈層次聚類方法，根據(jù)輸入模型數(shù)據(jù)中的各個巡查對象經(jīng)緯度坐標信息計算巡查對象兩兩之間的距離，得出兩兩距離矩陣，選擇矩陣中最小距離巡查對象納入最大最小時長閾值判斷。把小于最小閾值巡查對象進行合并，形成新對象，然后將合并前的2個巡查對象巡查通勤時間進行累計，且經(jīng)緯度取2個對象平均值，得出的新巡查對象將納入到下一輪的為組建巡查包庫，參與下一輪巡察包組建。當巡查對象合并后在最大最小閾值判斷范圍內(nèi)，則組建巡察包。當在大于最大閾值則進行標記，并在下次不進行合并計算。基于已經(jīng)組建好的巡查任務(wù)包進行線路規(guī)劃，以尋找最優(yōu)的路徑為目標，找到一條最短路徑，以最小的成本或時間完成巡查任務(wù)。

在河涌巡查線路規(guī)劃中，可能存在巡查時間窗口、巡查點的訪問限制等約束，將巡查點表示為圖的節(jié)點，巡查路徑表示為邊，構(gòu)建圖模型。在給定的約束條件下，通過找到最優(yōu)的組合或排列來達到最優(yōu)解，并用遺傳算法構(gòu)建巡查路線，輸出巡查包里的順序路線。動態(tài)組織巡查任務(wù)包流程見圖4。

基于已經(jīng)組建好的巡查任務(wù)包進行巡查線路規(guī)劃，將其轉(zhuǎn)化為旅行商問題尋找最優(yōu)的路徑［8］。本項目實際應(yīng)用中，以找到一條成本最小或時間最短的巡查路線為目標，使用遺傳算法［7］對上述問題進行求解，對5 318個巡查點組建成的1 110個巡查任務(wù)包，成功規(guī)劃巡查路線，部分結(jié)果見表5。

訓練線路規(guī)劃采用一種啟發(fā)式方法以生成巡查最短路徑，按照上述動態(tài)組織巡查任務(wù)包流程方式初始化巡查人員自定義參數(shù)包括人員單日工作時長、行進速度、單個工程巡查耗時、距離計算即兩兩水利工程的經(jīng)緯度進行換算出地表距離，采用層次聚類，最終輸出最短巡查線路任務(wù)包列表。

以表5里最后1條路線規(guī)劃為例：'新涌內(nèi)閘'， '八沙節(jié)制閘'，'南沙區(qū)新涌水閘'，'民生水閘'，'民生一隊閘'，'新涌二隊閘'，兩兩水利工程相隔距離矩陣，見表6。

通過使用遺傳算法求解該問題的最短巡查線路得出最短路徑為：'新涌內(nèi)閘'，'新涌二隊閘'，'八沙節(jié)制閘'，'南沙區(qū)新涌水閘'，'民生水閘'，'民生一隊閘'。該最短路徑的路徑長度為8 km，該最短路線規(guī)劃成果，見圖5。

最終形成預(yù)警分析專題軟件。將河道巡查的風險等級、巡查路線、巡查計劃等模型結(jié)果結(jié)合地理空間能力以及實際業(yè)務(wù)需求，構(gòu)建預(yù)警分析專題，解決巡河過程中巡查覆蓋面不足、人工排班、隨機抽取巡查對象等問題，形成具有界面化的軟件，軟件界面效果見圖6。

5 結(jié)論與分析

本文基于風險預(yù)警-遺傳算法耦合的方法，對廣州市河涌監(jiān)測中心河道巡查范圍內(nèi)水利工程設(shè)施進行了風險分級，通過單鏈層次聚類針對5 318個巡查點組建成1 110個巡查任務(wù)包，最后采用遺傳算法成果求解最優(yōu)巡查路線。實際應(yīng)用中，基于求解的最優(yōu)巡查路線，廣州市河涌監(jiān)測中心累計開展巡查730次，上報問題744個，已辦結(jié)126個，幫助巡查人員有針對性地巡查高風險區(qū)域和關(guān)注重點問題，減少巡查盲區(qū)，減少了不同巡查對象路線耦合造成的路線重復巡查頻次，減輕了巡查人員的工作負擔，對河道基層管養(yǎng)的減負增效有積極幫助，可為傳統(tǒng)的河道巡查管理工作提供新的嘗試與思路。

參考文獻：

［1］ 邊錦華，張曉霞. 求解TSP問題的一種變領(lǐng)域遺傳算法［J］. 福建電腦，2023，39（12）：24-27.

［2］ 王建忠，唐紅. TSP問題的一種快速求解算法［J］. 微電子學與計算機，2011，28（1）：7-10.

［3］ CINAR A C，KORKMAZ S，KIRAN M S. A discrete tree-seed algorithm for solving symmetric traveling salesman problem［J］.Engineering Science and Technology， an International Journal，2020， 23（4）： 879-890.

［4］ ZHANG Z， HAN Y. Discrete sparrow search algorithm for symmetric traveling salesman problem ［J］. Applied Soft Computing， 2022，118. DOI： 10. 1016/j. asoc. 2022. 108469.

［5］ SKINDEROWICZ R. Improving ant colony optimization efficiency for solving large TSP instances［J］. Applied Soft Computing， 2022，120. DOI： 10. 1016/j. asoc. 2022. 108653.

［6］ 李彥強，王建輝. 基于遺傳算法的無人機編隊高速公路巡檢任務(wù)規(guī)劃方法［J］. 市政技術(shù)，2023，41（11）：67-73.

［7］ 張大威，張明廣，劉文浩，等. 基于柵格遺傳算法的采購供應(yīng)物流配送車輛路線規(guī)劃方法［J］. 物流科技，2023，46（6）：4-7.

［8］ 史健. 基于改進遺傳算法的鮮活農(nóng)產(chǎn)品物流配送規(guī)劃方法研究［J］. 佳木斯大學學報（自然科學版），2023，41（3）：151-155.

［9］ 趙力萱，吳澤駒，何康園，等. 碳減排背景下定制公交路線規(guī)劃方法［J］. 交通運輸研究，2022，8（3）：56-65.

［10］ 王勇臻，陳燕，于瑩瑩. 求解多旅行商問題的改進分組遺傳算法［J］. 電子與信息學報，2017，39（1）：198-205.

［11］ 張碩航，郭改枝. 多旅行商模型及其應(yīng)用研究綜述［J］. 計算機科學與探索，2022，16（7）：1516-1528.

［12］ 許林濤. 丹山攔河閘止水工程系統(tǒng)風險評價技術(shù)研究［J］. 水利技術(shù)監(jiān)督，2021（6）：223-227.

［13］ 王莉芳. 基于組合賦權(quán)與灰色改進TOPSIS方法的受災(zāi)點應(yīng)急物質(zhì)需求緊迫性分級評價［J］. 安全與環(huán)境工程，2017，24（6）：94-100.

［14］ 張嘉龍. 基于相異度與鄰域的K-means初始聚類中心選擇算法［J］. 計算機時代，2021（8）：57-59，62.

［15］ 吳海麗. 大數(shù)據(jù)挖掘中的K-means 無監(jiān)督聚類算法的改進［J］. 現(xiàn)代電子技術(shù)，2020，43（19）：118-121.

［16］ 王金鳳，韋鵬，馬飛. 層次分析法在應(yīng)急預(yù)案事故災(zāi)難類風險評估中的應(yīng)用［J］. 質(zhì)量與認證，2024（1）：50-52.

（責任編輯：李燕珊）