基于遺傳算法解決線路網(wǎng)巡護(hù)問題論述

薛云飛，段 剛

（蘭州交通大學(xué)，甘肅 蘭州 730050）

1 概述

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

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

2 問題描述及假設(shè)

2.1 模型

巡護(hù)車輛從起點(diǎn)出發(fā)，對所有管道進(jìn)行維護(hù)，每條管道通過的次數(shù)必須大于等于1次，每條管道有固定的時(shí)間花費(fèi)，要求制定合理的巡護(hù)方案，使得總花費(fèi)時(shí)間最小。

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

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

2.2 遺傳算法算法步驟?

Step1 啟動(dòng)程序，輸入?yún)?shù)，使得能夠給出一個(gè)有N個(gè)染色體的初始群體pop(t),其中t=1；

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

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

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

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

Step6 對獲得的解的適值進(jìn)行比較，獲得較好的解，輸出結(jié)果。

3 算例

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

表1 鄰接矩陣

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

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

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

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

六天一周期。

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

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

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

六天一周期。

結(jié)果為總共使用4輛車，巡護(hù)時(shí)間較短。通過本文，可以較好的得到一個(gè)較優(yōu)的解，能夠滿足一般巡護(hù)需求，因此證明本文能夠?qū)窈笱沧o(hù)問題的研究做出一定的貢獻(xiàn)。

4 結(jié)論

文章旨在對一般的巡護(hù)問題進(jìn)行描述，同時(shí)提出了關(guān)于巡護(hù)問題的見解，對巡護(hù)問題的研究解決能夠起到一定的作用，巡護(hù)問題屬于NP問題，構(gòu)成高質(zhì)量的啟發(fā)式算法是十分具有現(xiàn)實(shí)意義的，也是今后需要解決的問題。