基于改進蟻群算法的鉆井救援車輛路徑規(guī)劃①

徐英卓,李 凱,周 俊

1(西安石油大學(xué) 計算機學(xué)院,西安 710065)

2(山脈科技股份有限公司,西安 710075)

1 引言

鉆井過程存在著大量復(fù)雜和不確定性因素,鉆井事故隨時都有可能發(fā)生.當(dāng)事故發(fā)生時,及時地進行應(yīng)急救援十分必要.要使救援人員和物資盡可能最快地到達待救援事故點,合理地規(guī)劃最優(yōu)救援路徑尤為重要.傳統(tǒng)的路徑規(guī)劃算法(如Dijkstra 算法、A*算法)存在計算效率低、易陷入局部最優(yōu)等缺點.近年來,隨著各種基于生物學(xué)的智能算法的出現(xiàn),蟻群算法在路徑規(guī)劃領(lǐng)域中得到應(yīng)用.蟻群算法是一種適于解決組合優(yōu)化問題的啟發(fā)式搜索算法,但當(dāng)問題規(guī)模較大時易陷入局部困境[1].為此,學(xué)者們對該算法進行改進,如徐坤等[2]將信息素揮發(fā)因子采用萊維飛行模式更新,提高了算法的全局尋優(yōu)能力;王帥等[3]將蟻群算法與遺傳算法結(jié)合,改進算法參數(shù)信息,提高了搜索范圍的多樣性,但收斂速度有待改善.當(dāng)前,針對蟻群算法在救援車輛路徑規(guī)劃方面的應(yīng)用研究還不夠完善,大多是針對多個救援點組合優(yōu)化支援單個受災(zāi)點,未綜合考慮實時路況、天氣等因素對救援路徑選擇的影響.而對于突發(fā)情況下的鉆井應(yīng)急救援,通常待救援點不止一個,且油田井場路網(wǎng)復(fù)雜,直接利用基本蟻群算法進行救援車輛路徑規(guī)劃時會存在一定的局限性,因此,本文提出基于改進蟻群算法的鉆井救援車輛路徑規(guī)劃研究,旨在為鉆井事故應(yīng)急救援規(guī)劃出最優(yōu)的物資配送路徑,以提高應(yīng)急救援效率.

2 基于改進蟻群算法的路徑規(guī)劃算法

2.1 蟻群算法基本原理及數(shù)學(xué)模型

蟻群算法是從螞蟻覓食的群體行為啟發(fā)而得出[2],蟻群在覓食過程中會在其走過的路徑上留下一種信息素[4],而螞蟻群體總是傾向在信息素濃度高的路線上覓食,相同時間內(nèi)較短路徑上的信息素含量最高,因此蟻群能準(zhǔn)確找到食物與巢穴之間的最短路徑.蟻群算法的數(shù)學(xué)模型通常借助TSP 問題進行描述[5].

2.2 改進蟻群算法

基本蟻群算法在求解轉(zhuǎn)移概率時僅依據(jù)路徑上的信息素含量和路徑長度,未考慮外界影響因素,如天氣、道路擁堵及道路等級等;另外,螞蟻搜索最優(yōu)解時根據(jù)信息素濃度進行狀態(tài)轉(zhuǎn)移,若剛開始某路徑上累積較多信息素,螞蟻會大概率選擇該路徑,但此路徑不一定最優(yōu),從而導(dǎo)致陷入局部最優(yōu).為此本文在救援路徑規(guī)劃時,對蟻群算法進行以下兩方面的改進:

(1)對轉(zhuǎn)移概率的改進

在實際救援路徑選擇時,有的路徑雖短,但由于道路狹窄不平或擁堵等,通過該路徑所需時間反而較長,因此,要想規(guī)劃出一條用時最短的救援路線,還需考慮影響車輛通行時間的外界因素,包括天氣、道路擁堵及道路等級.而這些因素對車輛通行的影響程度(即權(quán)重)各不相同,為此本文利用層次分析法(AHP)確定它們的權(quán)重[7].先將層次結(jié)構(gòu)分為目標(biāo)層Z和準(zhǔn)則層A,設(shè)目標(biāo)層的路徑權(quán)重為Wij,準(zhǔn)則層各指標(biāo)為:道路長度、交通流量、道路等級和天氣狀況,它們對于目標(biāo)層的權(quán)重分別為:w1、w2、w3、w4,見圖1.

圖1 路徑權(quán)重層次分析模型

為計算權(quán)重系數(shù)w1、w2、w3、w4,根據(jù)文獻[7]的數(shù)據(jù)和決策者經(jīng)驗判斷,構(gòu)造判斷矩陣A,見表1.

表1 判斷矩陣

2.3 基于改進蟻群算法的救援車輛路徑規(guī)劃

現(xiàn)實中鉆井救援車輛路徑規(guī)劃問題很復(fù)雜,為便于求解,本文對有些問題進行了簡化:(1)只有一個救援中心,救援車完成救援后都回到救援中心,等待下一次救援;(2)僅考慮救援車路上的行駛時間,不考慮為事故點服務(wù)的時間.設(shè)事故點(即待救援點)個數(shù)為n,救援中心有m輛型號相同的車,由于救援對時間要求高,因此目標(biāo)函數(shù)是求救援點到達所有事故點用時最少的行駛路線,定義為:

3 仿真實驗

為了驗證本文所提出的路徑規(guī)劃算法的有效性,采用Matlab 編程實現(xiàn)該算法并進行如下實驗:建立有12 個節(jié)點的路網(wǎng),節(jié)點0 為救援中心,節(jié)點1～節(jié)點11 表示各事故點,現(xiàn)救援車需從節(jié)點0 將物資運送到各事故點進行救援,各事故點的坐標(biāo)及其物資需求量見表2.

表2 各事故點坐標(biāo)及其物資需求量表

蟻群算法相關(guān)參數(shù)設(shè)置為:螞蟻數(shù)量m=20,α=1,β=1,權(quán)重指數(shù)λ=2,通過求解得到最優(yōu)路徑規(guī)劃結(jié)果和每次迭代的最短路徑見圖2,其最優(yōu)路徑為:

圖2 改進蟻群算法的最優(yōu)路徑規(guī)劃和每次迭代的最短路徑長度

0→3→8 →9→5→0;0→1→11→6→2→4→0;0→7→10→0,救援路徑全長為:498.8.

若采用基本蟻群算法進行救援路徑規(guī)劃(見圖3),通過求解得到的最優(yōu)路徑為:

圖3 基本蟻群算法的路徑規(guī)劃結(jié)果

0→3→8 →9→5→11→1→0;0→6→2→4→10→0;0→7→0,救援路徑全長為:451.3.

從以上結(jié)果可以看出:利用改進的蟻群算法進行路徑規(guī)劃得到的救援路徑總長度比基本蟻群算法得到的路徑總長度有所增加,但前者考慮了真實路網(wǎng)中影響車輛運行時間的外界因素(如天氣、交通流量等),其路徑更切實際,且算法在收斂速度、最優(yōu)解的搜索空間方面都有較大的提高,從而使實際上完成救援物資配送所需的總時間更短.

4 應(yīng)用實例

我們結(jié)合所承擔(dān)的陜西省自然科學(xué)研究計劃項目“基于物聯(lián)網(wǎng)的油田事故災(zāi)難應(yīng)急救援向?qū)絼討B(tài)管理方法研究”,依據(jù)本文提出的路徑規(guī)劃方法,開發(fā)了“油田事故應(yīng)急救援物資配送路徑規(guī)劃系統(tǒng)”,并選擇了XX 油田發(fā)生過多次事故的典型區(qū)塊對系統(tǒng)進行了應(yīng)用測試.以XX 油田的典型鉆井區(qū)塊為例,事故點分別為YC_101、YC_102、YC_103、YC_104、YC_105、YC_106、YC_107、YC_108、YC_109、YC_110,其位置分布見圖4,救援中心用 ∴標(biāo)注,事故點用0表示,設(shè)各事故點救援物資需求量(單位為t)分別為0.2、1.2、1.5、0.6、0.7、1.6、0.4、0.7、1.3、0.6,利用本文算法求出的最優(yōu)救援路經(jīng)(見圖4 不同顏色標(biāo)注)為:

圖4 最優(yōu)救援物資配送路徑規(guī)劃圖

①救援中心→YC_107→YC_103→YC_102→YC_101→YC_106→救援中心

②救援中心→YC_109→YC_110→YC_105→YC_104→YC_108→救援中心

根據(jù)以往該區(qū)塊的事故救援情況,上述路徑規(guī)劃結(jié)果與實際路網(wǎng)相符.

5 結(jié)論

利用改進蟻群算法進行鉆井救援車輛路徑規(guī)劃的方法,不僅保留了基本蟻群算法的優(yōu)點,還克服了它易陷入局部最優(yōu)的缺點,同時由于考慮了影響道路通行的外界因素,使整個算法具有更強的實用性.通過仿真實驗與應(yīng)用測試表明,該路徑規(guī)劃方法能滿足油田鉆井應(yīng)急救援應(yīng)用要求.