改進蟻群算法的航空物流運輸路徑規劃仿真

郭 川,山君亮,芮茂雨

(空軍勤務學院航空運輸與投送保障系,江蘇 徐州 221000)

1 引言

航空運輸物流因其快速、機動、高效的特點在現代物流運輸方式中脫穎而出。隨著我國航空運輸行業的發展,去往同一個地點的貨物有多條航空輸送路徑可以選擇,如何選擇最優路徑,對企業節省運輸成本、縮短貨物運輸時間有著非常重要的意義。

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

為了解決上述方法中存在的問題,提出考慮多因素耦合的航空物流運輸路徑規劃方法。為更精準優化空中運輸的路徑,首先明確運輸影響條件,設計目標函數,獲取在多種條件約束下的研究目標,優化蟻群算法,得到航空運輸路徑的最優解,并通過實驗對該方法的實用性完成驗證。

2 路徑規劃

2.1 模型構建

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

1)距離因素

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

(1)

式中,航線之間距離約束條件為D,兩個航線點間確切距離為d,航線點之間最遠距離為max。

2)天氣因素

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

3)飛機密度因素

在一個航空路線上飛機太多也可能造成飛機之間距離太近,進而造成航空事故。在航空運輸路徑規劃時,飛機密度q=c/m也尤為重要。其中,飛機數量為c,航線上承擔飛機的最大數量限度為m。當q=1時,表示飛機密度對飛行影響巨大,在路徑規劃中,需要避開這一航線點,防止航線上飛機過多,導致相撞引發飛行事故。

在路徑規劃中,依照不同因素影響的程度不同對其加權,當yi≠1并且qi≠1時:

(2)

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

2.2 約束條件

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

1)當量航程約束

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

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

(3)

式中,bi、bj為任意兩個航線點,h(bi,bj)為幾何航程,δij為相對燃油里程。當量航程越短,其燃油經濟性[7]越高。

2)集結時間窗約束

(4)

式中,當bi∈F,允許最大地面延誤時間為Φi,當bi∈T,允許的最大空中等待時間為Φi。

3)拓撲結構約束[8]

航空物流運輸路徑Y可以抽象理解為Steiner樹[9],如圖1(a)所示,則Y的拓撲結構為:

圖1 航空物流運輸路徑圖

①所有航線點的出入度是1。

②所有脫離點出度小于2、入度是1,集結點相反,入度小于2,出度是1。

4)流量平衡約束[10]

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

(5)

航線銜接點流量平衡約束表達式如下。

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

(6)

式中,vl、vl′是相鄰的兩個銜接點。

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

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

(7)

(8)

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

6)油耗約束

飛機的燃油攜帶量是經過精準計算其載物時最大起飛重量以及機場航道最大承重獲得的,所以要依據飛機燃油量規劃其物流運輸的距離。

7)任務時間要求約束

有時效性,必須在時效內完成運輸任務。

8)途經點約束

在物流運輸過程中必須經過的航線點。

9)航線距離約束

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

3 最優路徑計算

3.1 優化蟻群算法

在多種條件約束下,采用實時優化的蟻群算法[12-13],對航空物流運輸多路徑模型求解,實現對運輸路徑的優化。

(9)

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

對螞蟻移動路徑的及時刷新,使得蟻群的移動方式更新為以下:

(10)

蟻群可依據實時釋放的不同信息素搜索出路徑反常狀況,每當路徑發生異常,蟻群會迅速完成下一輪最優路徑的規劃選擇與信息迭代[14]。

3.2 步驟設計

1)依據航空物流干擾信息建立多路徑規劃模型,明確實時優化蟻群的約束條件。

2)設定目標函數。

3)蟻群更新移動起點設定在創建的模型中多條路徑的中心點,對多條路徑同時移動。

4)蟻群在移動到下一個更新節點的過程中,每一個個體都會釋放并自動檢索以時間為標準的信息素,完成信息濃度的更新。

5)更新完所有路徑節點信息,獲得最優路徑,完成航空物流運輸路徑規劃。

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

3.3 最優路徑的平滑處理

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

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

圖2 路徑平滑示意圖

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

(11)

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

4 實驗分析

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

圖3 航空物流路徑規劃結果

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

航空物流運輸路徑規劃優化時間直接影響著路徑規劃結果,采用不同方法的路徑規劃結果如圖4所示。

圖4 不同方法的路徑規劃時間

分析圖4可知,所提方法路徑規劃時間最短,始終保持在10ms以內,其它三種方法在航空物流運輸路徑規劃中的時間是所提方法的30倍以上,表明所提方法在路徑規劃中機動性強、路徑優化速度快。因為所提方法考慮多耦合因素構建多約束航空物流運輸路徑規劃模型,采用實時優化蟻群算法展開多路徑同時優化。大大縮短了路徑規劃的時間。

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

表1 不同路徑規劃方法的航程

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

將高度代價作為指標,不同方法的規劃路徑的高度代價如圖5所示。

圖5 不同方法的高度代價

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

航空物流運輸的路徑規劃必須在減少全局路徑危險程度的基礎上完成運輸任務,因此在本節實驗中,選取危險度作為方法評價指標。危險度指標的計算公式如下:

(12)

式中,λ(pij)表示運輸飛機根據飛行點R和障礙物pij處的高度得到的風險位置,rsafe表示安全閾值。n為局部航空環境中鄰近的障礙物數量。根據此公式計算不同方法的危險度量化指標如圖6所示。

圖6 不同方法的危險度

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

5 結束語

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