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

徐英卓,李 凱,周 俊

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

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

1 引言

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

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

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

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

2.2 改進(jìn)蟻群算法

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

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

在實(shí)際救援路徑選擇時(shí),有的路徑雖短,但由于道路狹窄不平或擁堵等,通過該路徑所需時(shí)間反而較長(zhǎng),因此,要想規(guī)劃出一條用時(shí)最短的救援路線,還需考慮影響車輛通行時(shí)間的外界因素,包括天氣、道路擁堵及道路等級(jí).而這些因素對(duì)車輛通行的影響程度(即權(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)為:道路長(zhǎng)度、交通流量、道路等級(jí)和天氣狀況,它們對(duì)于目標(biāo)層的權(quán)重分別為:w1、w2、w3、w4,見圖1.

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

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

表1 判斷矩陣

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

4 應(yīng)用實(shí)例

我們結(jié)合所承擔(dān)的陜西省自然科學(xué)研究計(jì)劃項(xiàng)目“基于物聯(lián)網(wǎng)的油田事故災(zāi)難應(yīng)急救援向?qū)絼?dòng)態(tài)管理方法研究”,依據(jù)本文提出的路徑規(guī)劃方法,開發(fā)了“油田事故應(yīng)急救援物資配送路徑規(guī)劃系統(tǒng)”,并選擇了XX 油田發(fā)生過多次事故的典型區(qū)塊對(duì)系統(tǒng)進(jìn)行了應(yīng)用測(cè)試.以XX 油田的典型鉆井區(qū)塊為例,事故點(diǎn)分別為YC_101、YC_102、YC_103、YC_104、YC_105、YC_106、YC_107、YC_108、YC_109、YC_110,其位置分布見圖4,救援中心用 ∴標(biāo)注,事故點(diǎn)用0表示,設(shè)各事故點(diǎn)救援物資需求量(單位為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é)果與實(shí)際路網(wǎng)相符.

5 結(jié)論

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