基于遺傳算法解決線路網巡護問題論述

薛云飛，段 剛

（蘭州交通大學，甘肅 蘭州 730050）

1 概述

2018年4月16日，美國運籌與管理學會（INFORMS）在其舉辦的2018商業分析與運籌年會中，表彰了6個隊伍，中國石油天然氣集團的天然氣運輸管道優化軟件的制作團隊就是這六個隊伍中的一個。在過去的五年中，中國的天然氣總使用量幾乎翻了一番，天然氣管道長度正以十分迅猛的速度增長。本文針對如何更科學地安排巡護路徑來進行研究，采用遺傳算法進行算法設計，更科學且貼近實際，能夠幫助兩區段的巡護管理處節省成本，也能為以后的各線路網維護工作的安排巡護路徑工作提供依據，十分具有現實意義。

遺傳算法是一種經典的智能進化算法，它是采用模擬生物在自然界中的生存繁衍，逐漸適應其生存環境的方式來獲得問題的近似最優值，它會根據問題的目標函數構成一個適應度函數，而問題解的各個可能取值稱為染色體，一系列的染色體構成一個種群。這一種群中的各個染色體經過若干代的交叉、變異、選擇，逐漸趨于問題的最優解，在滿足設定的最大迭代次沒有更優值之后進行停止，取值趨向最優解[1]。

2 問題描述及假設

2.1 模型

巡護車輛從起點出發，對所有管道進行維護，每條管道通過的次數必須大于等于1次，每條管道有固定的時間花費，要求制定合理的巡護方案，使得總花費時間最小。

G=（V，E）表示巡護網絡，V={0,1,2,...n}，其中 0表示起點，E={（i，j）|i，jV，i≠j}為弧集，Tij表示 vi，vj兩點之間的巡護時間,其中vi，vj兩點之間存在鏈且不存在其他點Cij，表示尋護車輛巡護邊[Vi，vj]的次數，他要求每條邊至少巡護一次。

以上是對簡單的巡護模型的目標進行描述，目標函數的意思使得巡護時間最短，且每條邊至少要求巡護一次，同時要求能夠滿足巡護的路徑是連續的，由于各種問題要求不同，因此本文未給出詳細模型。

2.2 遺傳算法算法步驟?

Step1 啟動程序，輸入參數，使得能夠給出一個有N個染色體的初始群體pop(t),其中t=1；

Step2 將群體帶入停止規則若停止規則滿足，則算法停止；否則，對群體pop(t)中每一個染色體popi(t)計算其適應值；

Step3 從群體pop(t)中隨機選一些染色體構成一個種群newpop(t+1)={popj(t)|j=1,2,…,N};

Step4 通過交叉，交叉概率,得到有N個染色體的crosspop(t+1)；

Step5 對每個新個體依變異概率進行變異，形成mutpop(t+1);t=t+1,新的群體pop(t)=mutpop(t);返回步驟2；

Step6 對獲得的解的適值進行比較，獲得較好的解，輸出結果。

3 算例

為了方便理解，本文引入了一個簡單的例子，線路網鄰接對稱矩陣見表1，表示點之間的距離。同時，在本文的基礎上，本算例要求線路需要兩天內最少巡護一次，且巡護單位巡護完成后要回到出發位置，且工作3～6h之間有休息時間，同時每輛車工作兩天至少休息一天。

表1 鄰接矩陣

通過本文中描述的過程，得到以下結果：

1）6為始點第一輛車向左巡護6→5→4→3（工作4.5h午休）→2→1總共工作時間7.5h在1休息第二天返回，至此第一輛車工作兩天，進行休息；

第三天第二輛車出發巡護向左巡護6→5→4→3（工作4.5h午休）→2→1總共工作時間7.5h在1休息第四天返回，至此第二輛車工作兩天，進行休息；

第一輛車第四天休息，第五天繼續工作左巡護6→5→4→3（工作4.5h午休）→2→1總共工作時間7.5h在1休息第六天返回；

六天一周期。

2）6為始點第三輛車向右巡護6→7→8→9（工作4.2h午休）→10→11總共工作時間7.2h在11休息第二天返回，第三天休息；

第四輛車第三天從6出發向右巡護6→7→8→9（工作4.2h午休）→10→11總共工作時間7.2h在11休息第四天返回，第五天休息；

第三輛車第四天休息，第五天繼續工作向右巡護6→7→8→9（工作4.2h午休）→10→11總共工作時間7.2h在11休息第六天返回；

六天一周期。

結果為總共使用4輛車，巡護時間較短。通過本文，可以較好的得到一個較優的解，能夠滿足一般巡護需求，因此證明本文能夠對今后巡護問題的研究做出一定的貢獻。

4 結論

文章旨在對一般的巡護問題進行描述，同時提出了關于巡護問題的見解，對巡護問題的研究解決能夠起到一定的作用，巡護問題屬于NP問題，構成高質量的啟發式算法是十分具有現實意義的，也是今后需要解決的問題。