改進(jìn)蟻群算法的航空物流運(yùn)輸路徑規(guī)劃仿真

郭 川,山君亮,芮茂雨

(空軍勤務(wù)學(xué)院航空運(yùn)輸與投送保障系,江蘇 徐州 221000)

1 引言

航空運(yùn)輸物流因其快速、機(jī)動(dòng)、高效的特點(diǎn)在現(xiàn)代物流運(yùn)輸方式中脫穎而出。隨著我國航空運(yùn)輸行業(yè)的發(fā)展,去往同一個(gè)地點(diǎn)的貨物有多條航空輸送路徑可以選擇,如何選擇最優(yōu)路徑,對企業(yè)節(jié)省運(yùn)輸成本、縮短貨物運(yùn)輸時(shí)間有著非常重要的意義。

航空物流運(yùn)輸路徑的規(guī)劃不是單一的數(shù)學(xué)選擇問題,需要借助計(jì)算機(jī)技術(shù)和現(xiàn)代優(yōu)化方法對其展開求解[1]。例如:邢小虎等人[2]提出利用隨機(jī)遺傳算法對航空物流運(yùn)輸路徑求解,獲取不同途經(jīng)點(diǎn)和到達(dá)點(diǎn)之間的穩(wěn)定線路,解決MTSP問題,構(gòu)建多目標(biāo)路徑規(guī)劃模型,以此為依據(jù)實(shí)現(xiàn)航空物流運(yùn)輸路徑規(guī)劃,該方法在路徑規(guī)劃中的危險(xiǎn)度高,精準(zhǔn)度低。崔葉竹等人[3]提出應(yīng)用人工魚群算法對航空物流運(yùn)輸路徑求解,根據(jù)航空物流運(yùn)輸路徑設(shè)定約束條件,結(jié)合VPR數(shù)學(xué)模型模擬魚群覓食過程,對以上模型展開優(yōu)化,以此為依據(jù)實(shí)現(xiàn)航空物流運(yùn)輸路徑規(guī)劃,該方法在路徑規(guī)劃中高度代價(jià)高,性能低。張洪海等人[4]提出基于改進(jìn)A*(A-star)算法的航空物流運(yùn)輸路徑求解方法。采用柵格法展開環(huán)境建模,多方位考慮外在因素,結(jié)合曼哈頓距離線性組合設(shè)計(jì)啟發(fā)函數(shù)構(gòu)建多約束航空物流運(yùn)輸路徑規(guī)劃模型,以此為依據(jù)實(shí)現(xiàn)航空物流運(yùn)輸路徑規(guī)劃,該方法路徑規(guī)劃航程長,運(yùn)輸成本高。

為了解決上述方法中存在的問題,提出考慮多因素耦合的航空物流運(yùn)輸路徑規(guī)劃方法。為更精準(zhǔn)優(yōu)化空中運(yùn)輸?shù)穆窂?首先明確運(yùn)輸影響條件,設(shè)計(jì)目標(biāo)函數(shù),獲取在多種條件約束下的研究目標(biāo),優(yōu)化蟻群算法,得到航空運(yùn)輸路徑的最優(yōu)解,并通過實(shí)驗(yàn)對該方法的實(shí)用性完成驗(yàn)證。

2 路徑規(guī)劃

2.1 模型構(gòu)建

為了解決傳統(tǒng)航空物流運(yùn)輸多種路徑復(fù)雜且多樣化的弊端,考慮多因素耦合的航空物流運(yùn)輸路徑規(guī)劃方法,對影響航空物流運(yùn)輸路徑的各種因素展開分析。一般情況下,影響航空物流運(yùn)輸路徑規(guī)劃的因素[5]有如下三個(gè):

1)距離因素

最重要的因素就是距離,各航線點(diǎn)中的航線距離是確定的,當(dāng)航線點(diǎn)之間沒有航線時(shí)用0表示。由于航線之間的距離值過大,使用此數(shù)值會(huì)將其它約束條件的影響降低到很小,從而影響到最終結(jié)果,所以要統(tǒng)一所有參數(shù),將航線之間的距離值限制在(0,1)之間,表達(dá)式如下:

(1)

式中,航線之間距離約束條件為D,兩個(gè)航線點(diǎn)間確切距離為d,航線點(diǎn)之間最遠(yuǎn)距離為max。

2)天氣因素

由于天氣較為復(fù)雜,為了將其簡單化,對天氣影響劃分:對運(yùn)輸飛機(jī)影響巨大(記成1)、大(記成0.9)、適中(記成0.6)、小(記成0.3)、無影響(記成0)。在求解過程中,隨機(jī)出現(xiàn)上述情況y,當(dāng)y=1時(shí),表示天氣對航行影響巨大,在路徑規(guī)劃中,需要避開這一航線點(diǎn),防止因天氣影響航空物流運(yùn)輸。

3)飛機(jī)密度因素

在一個(gè)航空路線上飛機(jī)太多也可能造成飛機(jī)之間距離太近,進(jìn)而造成航空事故。在航空運(yùn)輸路徑規(guī)劃時(shí),飛機(jī)密度q=c/m也尤為重要。其中,飛機(jī)數(shù)量為c,航線上承擔(dān)飛機(jī)的最大數(shù)量限度為m。當(dāng)q=1時(shí),表示飛機(jī)密度對飛行影響巨大,在路徑規(guī)劃中,需要避開這一航線點(diǎn),防止航線上飛機(jī)過多,導(dǎo)致相撞引發(fā)飛行事故。

在路徑規(guī)劃中,依照不同因素影響的程度不同對其加權(quán),當(dāng)yi≠1并且qi≠1時(shí):

(2)

式中,g(c)為航線點(diǎn),di/max為加權(quán)后的距離約束條件,yi為加權(quán)后的天氣約束條件,ci/MI為加權(quán)后的飛機(jī)密度約束條件。權(quán)值重新規(guī)劃,當(dāng)yi=1或者qi=1時(shí),這一航線點(diǎn)不可以通過。

2.2 約束條件

在路徑規(guī)劃過程中,有很多限制路徑規(guī)劃的約束條件[6]。如下

1)當(dāng)量航程約束

引入當(dāng)量航程he(bi,bj)概念,其表達(dá)式為:

he(bi,bj)=h(bi,bj)/δij

(3)

式中,bi、bj為任意兩個(gè)航線點(diǎn),h(bi,bj)為幾何航程,δij為相對燃油里程。當(dāng)量航程越短,其燃油經(jīng)濟(jì)性[7]越高。

2)集結(jié)時(shí)間窗約束

(4)

式中,當(dāng)bi∈F,允許最大地面延誤時(shí)間為Φi,當(dāng)bi∈T,允許的最大空中等待時(shí)間為Φi。

3)拓?fù)浣Y(jié)構(gòu)約束[8]

航空物流運(yùn)輸路徑Y(jié)可以抽象理解為Steiner樹[9],如圖1(a)所示,則Y的拓?fù)浣Y(jié)構(gòu)為:

圖1 航空物流運(yùn)輸路徑圖

①所有航線點(diǎn)的出入度是1。

②所有脫離點(diǎn)出度小于2、入度是1,集結(jié)點(diǎn)相反,入度小于2,出度是1。

4)流量平衡約束[10]

對于所有的航線點(diǎn),流入和流出節(jié)點(diǎn)流量相等,所以同一Steiner點(diǎn)的3條邊存在約束,集結(jié)點(diǎn)與脫離點(diǎn)的流量平衡約束表達(dá)式如下。

(5)

航線銜接點(diǎn)流量平衡約束表達(dá)式如下。

wvl=wvl′,vl∈v,vl′∈v

(6)

式中,vl、vl′是相鄰的兩個(gè)銜接點(diǎn)。

5)飛行受限區(qū)[11]約束

根據(jù)我國《民用航空法》規(guī)定,任何航空器非經(jīng)許可,不得進(jìn)入禁區(qū)、限制區(qū)及危險(xiǎn)區(qū)。飛行受限區(qū)即為上述區(qū)域。根據(jù)圖1(b),飛行受限區(qū)約束可表示為:

(7)

(8)

式中,地球半徑表示為TE。

6)油耗約束

飛機(jī)的燃油攜帶量是經(jīng)過精準(zhǔn)計(jì)算其載物時(shí)最大起飛重量以及機(jī)場航道最大承重獲得的,所以要依據(jù)飛機(jī)燃油量規(guī)劃其物流運(yùn)輸?shù)木嚯x。

7)任務(wù)時(shí)間要求約束

有時(shí)效性,必須在時(shí)效內(nèi)完成運(yùn)輸任務(wù)。

8)途經(jīng)點(diǎn)約束

在物流運(yùn)輸過程中必須經(jīng)過的航線點(diǎn)。

9)航線距離約束

根據(jù)燃油和時(shí)效的影響,飛機(jī)的航線距離必須低于同等重量下的最大飛行距離。

3 最優(yōu)路徑計(jì)算

3.1 優(yōu)化蟻群算法

在多種條件約束下,采用實(shí)時(shí)優(yōu)化的蟻群算法[12-13],對航空物流運(yùn)輸多路徑模型求解,實(shí)現(xiàn)對運(yùn)輸路徑的優(yōu)化。

(9)

式中,oml(y)為時(shí)刻y連接點(diǎn)的信息濃度,ε為信息素的相對重要性,δ為啟發(fā)信息的相對重要性。

對螞蟻移動(dòng)路徑的及時(shí)刷新,使得蟻群的移動(dòng)方式更新為以下:

(10)

蟻群可依據(jù)實(shí)時(shí)釋放的不同信息素搜索出路徑反常狀況,每當(dāng)路徑發(fā)生異常,蟻群會(huì)迅速完成下一輪最優(yōu)路徑的規(guī)劃選擇與信息迭代[14]。

3.2 步驟設(shè)計(jì)

1)依據(jù)航空物流干擾信息建立多路徑規(guī)劃模型,明確實(shí)時(shí)優(yōu)化蟻群的約束條件。

2)設(shè)定目標(biāo)函數(shù)。

3)蟻群更新移動(dòng)起點(diǎn)設(shè)定在創(chuàng)建的模型中多條路徑的中心點(diǎn),對多條路徑同時(shí)移動(dòng)。

4)蟻群在移動(dòng)到下一個(gè)更新節(jié)點(diǎn)的過程中,每一個(gè)個(gè)體都會(huì)釋放并自動(dòng)檢索以時(shí)間為標(biāo)準(zhǔn)的信息素,完成信息濃度的更新。

5)更新完所有路徑節(jié)點(diǎn)信息,獲得最優(yōu)路徑,完成航空物流運(yùn)輸路徑規(guī)劃。

6)在優(yōu)化過程中,時(shí)間信息素差距影響著蟻群的更新速度,差距越大則更新越快,完成路徑優(yōu)化速度越快。

3.3 最優(yōu)路徑的平滑處理

通常情況下,實(shí)時(shí)優(yōu)化蟻群算法求解的最優(yōu)路徑是連續(xù)的曲線。由于曲線中有凹凸點(diǎn),即最優(yōu)路徑本身是連續(xù)的但其一階導(dǎo)數(shù)不連續(xù)。最優(yōu)路徑的平滑處理[15]就是為了使實(shí)時(shí)優(yōu)化蟻群算法求解的曲線和一階導(dǎo)數(shù)均是連續(xù)。

由于多種原因約束限制,航空器在從航線點(diǎn)S點(diǎn)行進(jìn)到航線點(diǎn)N后無法直接沿NV繼續(xù)行駛,因此,需要在SN和NV之間展開平滑處理,如圖2所示。

圖2 路徑平滑示意圖

如果SN和NV之間可以展開平滑(去掉尖角∠SNV),用圓弧連接兩個(gè)航線點(diǎn)?！蟂NV的平分線和NV之間較小邊的中垂線相交于P1,P1為圓心SN和NV之間相切的圓,則該圓半徑表達(dá)式為:

(11)

以同樣的方式對NV和NV展開處理,3個(gè)直線段和2個(gè)圓弧段組成了S→F之間的最優(yōu)路徑,以此完成整個(gè)航空物流運(yùn)輸路徑的規(guī)劃。

4 實(shí)驗(yàn)分析

為了驗(yàn)證考慮多因素耦合的航空物流運(yùn)輸路徑規(guī)劃方法的整體有效性,需要對其展開相關(guān)測試。利用百度地圖獲取部分地理數(shù)據(jù)作為實(shí)驗(yàn)測試范圍。設(shè)置起始點(diǎn)為G,終點(diǎn)為H,采用文獻(xiàn)[2]提出的MTSP路軌規(guī)劃模型及其遺傳算法、文獻(xiàn)[3]提出的人工魚群算法、文獻(xiàn)[4]提出的改進(jìn)A*(A-star)算法與所提方法對航空物流運(yùn)輸路徑展開規(guī)劃,規(guī)劃結(jié)果如圖3所示。

圖3 航空物流路徑規(guī)劃結(jié)果

由圖3可知四種方法均能完成航空物流運(yùn)輸路徑規(guī)劃任務(wù)。所提方法在路徑規(guī)劃時(shí)途經(jīng)太原和北京兩個(gè)重要中轉(zhuǎn)點(diǎn),而MTSP路軌規(guī)劃模型及其遺傳算法(文獻(xiàn)[2]方法)、人工魚群算法(文獻(xiàn)[3]方法)、改進(jìn)A*(A-star)算法(文獻(xiàn)[4]方法)并沒有途經(jīng)此處,表明所提方法在航空物流運(yùn)輸路徑規(guī)劃中可應(yīng)用性更強(qiáng)。

航空物流運(yùn)輸路徑規(guī)劃優(yōu)化時(shí)間直接影響著路徑規(guī)劃結(jié)果,采用不同方法的路徑規(guī)劃結(jié)果如圖4所示。

圖4 不同方法的路徑規(guī)劃時(shí)間

分析圖4可知,所提方法路徑規(guī)劃時(shí)間最短,始終保持在10ms以內(nèi),其它三種方法在航空物流運(yùn)輸路徑規(guī)劃中的時(shí)間是所提方法的30倍以上,表明所提方法在路徑規(guī)劃中機(jī)動(dòng)性強(qiáng)、路徑優(yōu)化速度快。因?yàn)樗岱椒紤]多耦合因素構(gòu)建多約束航空物流運(yùn)輸路徑規(guī)劃模型,采用實(shí)時(shí)優(yōu)化蟻群算法展開多路徑同時(shí)優(yōu)化。大大縮短了路徑規(guī)劃的時(shí)間。

將航程(飛行器的實(shí)際飛行距離)作為指標(biāo),不同路徑規(guī)劃方法的航程如表1所示。

表1 不同路徑規(guī)劃方法的航程

由表1可知。起始點(diǎn)和終點(diǎn)一致的情況下,經(jīng)過多次實(shí)驗(yàn),所提方法的航空物流平均航程在1194km,遠(yuǎn)低于其它三種方法的運(yùn)輸航程,表明所提方法在航空物流運(yùn)輸路徑規(guī)劃中效率高,可以有效降低運(yùn)輸成本。

將高度代價(jià)作為指標(biāo),不同方法的規(guī)劃路徑的高度代價(jià)如圖5所示。

圖5 不同方法的高度代價(jià)

由圖5可知所提方法在多次實(shí)驗(yàn)后的高度代價(jià)波動(dòng)穩(wěn)定,MTSP路軌規(guī)劃模型及其遺傳算法、人工魚群算法和改進(jìn)A*(A-star)算法的高度代價(jià)波動(dòng)很大,并且人工魚群算法高度代價(jià)最高達(dá)到600,而所提方法的高度代價(jià)僅在190,實(shí)驗(yàn)結(jié)果表明所提方法在航空物流運(yùn)輸路徑規(guī)劃中性能高。

航空物流運(yùn)輸?shù)穆窂揭?guī)劃必須在減少全局路徑危險(xiǎn)程度的基礎(chǔ)上完成運(yùn)輸任務(wù),因此在本節(jié)實(shí)驗(yàn)中,選取危險(xiǎn)度作為方法評價(jià)指標(biāo)。危險(xiǎn)度指標(biāo)的計(jì)算公式如下:

(12)

式中,λ(pij)表示運(yùn)輸飛機(jī)根據(jù)飛行點(diǎn)R和障礙物pij處的高度得到的風(fēng)險(xiǎn)位置,rsafe表示安全閾值。n為局部航空環(huán)境中鄰近的障礙物數(shù)量。根據(jù)此公式計(jì)算不同方法的危險(xiǎn)度量化指標(biāo)如圖6所示。

圖6 不同方法的危險(xiǎn)度

分析圖6可知,文獻(xiàn)方法的危險(xiǎn)度始終在0.6以上,其中文獻(xiàn)[2]方法的最高危險(xiǎn)度高于0.8。所提方法對航空物流路徑規(guī)劃的危險(xiǎn)度最高值在0.3左右,并且隨著實(shí)驗(yàn)次數(shù)的增加逐漸降低,最低值低于0.1。此測試結(jié)果表明考慮多因素耦合的航空物流運(yùn)輸路徑規(guī)劃方法精準(zhǔn)度高。

5 結(jié)束語

航空物流運(yùn)輸中存在同地點(diǎn)多路徑,無法快速選擇最優(yōu)路徑的問題,為了解決該問題,提出考慮多因素耦合的航空物流運(yùn)輸路徑規(guī)劃方法。通過對航空物流運(yùn)輸路徑的干擾因素展開分析,構(gòu)建多約束航空物流運(yùn)輸路徑規(guī)劃模型,采用實(shí)時(shí)優(yōu)化蟻群算法獲取模型最優(yōu)解,實(shí)現(xiàn)航空物流運(yùn)輸路徑的規(guī)劃。解決了目前存在的問題,為今后航空物流運(yùn)輸路徑研究奠定了基礎(chǔ)。