基于遺傳算法的航空物流配送路徑優化分析

楊曉康，宋秀峰

(1.山東外貿職業學院國際運輸與物流系民航教研室，山東 青島 266100；2.青島歌爾聲學科技有限公司 ，山東 青島 266041)

0 引言

航空物流作為現代物流重要的組成部分，具有時間短、服務性好、覆蓋面廣的優勢，受到各物流企業的重視[1]。隨著全球一體化的加快發展，航空物流面臨著諸多挑戰和機遇。較高的運營成本，以及嚴格的空中、地面運輸服務設施，給航空物流的發展帶來嚴峻考驗。加大對物流配送路徑的優化已成為降低運營成本、提高經濟效益的有效途徑[2]。然而，物流配送路徑的優化是一個復雜度高的數學問題，涉及現代化的優化算法[3]。

目前，針對航空物流配送路徑優化，較普遍的優化算法為遺傳算法和粒子群算法[4-5]。遺傳算法可對航空物流配送點進行優化計算，獲得時間窗約束條件下的物流配送點架構[6]。基于遺傳算法和粒子群算法的智能混合算法，從安全、成本方面實現物流配送優化[7]。盡管遺傳算法已被應用到物流配送的相關研究中，但由于常規遺傳算法存在的固有缺陷，如計算難度大、收斂性差、搜索效益低的問題，因而要實現航空物流配送速度和服務體系的改善還存在較大限制[8]。

基于此，本文對傳統遺傳算法進行優化，針對航空物流種群數量單一、已陷入局部最優解的問題，提出1種自適應變異方法。該方法對傳統遺傳算法進行了算法改進以保證算法的收斂性，并引入Metorpolis準則以提升算法的搜索能力，實現了航空物流配送路徑的優化。

1 算法描述

1.1 遺傳算法

遺傳算法是通過模仿生物界遺傳規律構建的1種全局搜索方法。遺傳算法首先根據適應度值選擇合適的初始染色體，然后利用交叉變異形成下一代染色體，再由反復迭代計算獲得下一代種群，最后將最優個體作為最優解。圖1為1個標準的遺傳算法流程圖。

圖1 遺傳算法流程圖

1.1.1 初始種群編碼

在使用遺傳算法前，需將問題轉化為機器可識別的數據信息。考慮到二進制編碼對計算機內存要求較高，故選擇采用格雷碼編碼方式[9]。具體為：

(1)

式中：xi和yi分別為初始個體和子代個體的二進制編碼。

X=xmxm-1…x2x1為二進制的編碼形式。通過對問題進行格雷碼編碼處理，可進行遺傳選擇、交叉、變異操作。

選擇是從群體中挑選優勢個體，進行交叉變異操作并獲得下一代的過程。自遺傳算法中采用蒙特卡洛算子選擇初始個體。對于每個個體，存在1個適應度值F(xi)。對于整個群體，存在1個總適應度Fs。個體適應度與群體總適應度之間的關系式為：

Fs=F(x1)+F(x2)+K+F(xN)

(2)

由Fs形成1個隨機數K，將各個體適應度累加到超過Fs后，選擇最后1個個體作為被選擇對象。

1.1.2 遺傳交叉和變異

生物遺傳中存在普遍的基因重組現象。遺傳算法通過交叉操作模擬生物遺傳中的基因重組來提升算法的搜索能力。遺傳交叉首先在上一代子體中隨機選擇1段交叉區段，然后通過基因交叉，消除其中的相同區段，最終形成新的基因。圖2為1種典型的單點交叉操作示意圖。

圖2 單點交叉操作示意圖

變異可以對已有基因形式進行重組，從而進一步提升種群搜索能力。首先，設定變異概率Pm；然后，對編碼后染色體串上的每個基因均形成1個隨機數ri。當ri

(3)

對交叉、變異后的個體進行適應度評估，并保留適應度高的個體。由于適應度函數要求滿足非負特性[15]，選擇適應度函數為：

(4)

式中：N為種群個體數。

對優化后的算法，確立迭代種植條件。當優化結果滿足該終止條件，則算法終止。本文確定的終止條件如式(5)所示。

(5)

1.2 算法改進

傳統遺傳算法基于單一種群的選擇、遺傳和變異來獲得子代群體。如單一種群多樣性較好，則具有了較好的自適應能力。如單一種群多樣性較差，則搜索空間有限，易陷入局部最優解。因此，從遺傳算法變異操作入手，采用自適應變異方法增強變異差異[10]，可避免陷入局部最優解；同時，引入模擬退火算法的Metropolis準則[11]，判斷其是否接受變異產生的個體，可提升算法收斂精度。

在進行變異適應度改進時，若當前種群多樣性較好，不發生提前收斂，則放棄變異操作。若種群提前收斂，則根據多樣性情況分別處理。①種群多樣性較差，則根據自適應變異進行變異操作。②種群多樣性幾乎沒有，則引進新的物種，增強變異的差異。

交叉概率Pc和變異概率Pm對算法收斂性有影響。當Pc、Pm值較大時，則收斂速度較快，部分適應度較高的個體遭到破壞，易陷入局部最優解；當Pc、Pm值較小時，則產生新個體速度較慢，易出現搜索停滯[12]。因此，利用自適應原則來選擇Pc、Pm。其計算式為：

(6)

式中：Favg為種群平均適應度；Pc_max、Pc_min分別為最大、最小交叉概率;E為總迭代數；e為當前迭代數；F為個體適應度。

(7)

式中：Pm_max、Pm_min分別為最大、最小變異概率。

當個體適應度小于平均適應度時，通過進行交叉、變異操作，賦予交叉適應度個體較大交叉和較小變異概率。當個體適應度大于平均適應度時，則根據優良程度設置交叉變異概率，從而避免提前收斂。

當種群變異改良后，引入模擬退火算法的改進Metropolis準則判定是否接受變異后個體。原有計算式為：

(8)

式中：P(i->j)為變異概率，取值范圍為(0.1]；f(j)為初始解；f(i)為目標函數。

T0的衰減方式決定著速度和準確性。本文采用指數降溫方式。式(9)為T0的衰減函數:

t=δnT0

(9)

式中:常數δ∈(0,1)；n為模擬退火算法的循環次數；T0為初始溫度,T0>0;t為溫度控制參數，隨著迭代次數的增加而逐漸變小。

當n比較小時，溫度的下降速度快。當n比較大時，溫度的下降速度慢。通過選擇適當的δ值可以控制溫度的下降速度。改進后的計算式為：

(10)

通過Metropolis準則保證種群搜索能力，可避免陷入局部最優解。

2 航空物流運輸路徑優化

2.1 模型建立

航空運輸依托航空公司航線來實現物流運輸。路徑規劃的關鍵是以最短路徑為目標，獲得最優化的航空運輸路徑。在建立模型前，需假設n個機場的最大覆蓋率和機場間距都是已知的，模型中存在P個直通航路的樞紐城市，建立起最優路徑下的n個機場和P個樞紐城市間的表達式為：

(11)

(12)

(13)

式(12)表示一個城市只配送一次。式(13)表示航班由某地出發，完成配送和返回該地。根據城市進行實數編碼，隨機形成種群。為保證模型取得最大適應度值，選擇線路最大長度的倒數值作為算法的適應度值，即：

(14)

由父代種群中隨機選擇個體進行適應度比較，并選出適應度最大的個體遺傳到下一代。采用洗牌交叉方式將基因相互混合，并在交叉后恢復位置。完成交叉后，隨機選擇基于序組上對應臨界基因值替換原有值，完成交叉變異操作。

2.2 算法仿真測試

本文以全國34個城市機場為對象進行算法仿真分析。首先，對34個城市分別進行編號。以編號1為配送地點，歷經33個配送城市后，解決回到編號1的一條最短航運配送線路的規劃問題。設定種群個體數為300個，最大迭代次數為500次，種群交叉概率為0.95，變異概率為0.3。

將改進算法與傳統遺傳算法進行比較，獲得優化配送結果。不同算法的最優路徑如圖3所示。傳統遺傳算法的尋優路徑最短距離為2 380.69 km，而采用改進遺傳算法的尋優路徑最短距離為1 570.26 km。由此可知，改進的遺傳算法獲得的最優路徑長度明顯更小，即算法的全局最優解尋優能力更優。

圖3 不同算法的最優路徑

將改進算法與傳統遺傳算法的收斂性能進行比較，算法的收斂性能比較如表1所示。由表1可知，改進后的遺傳算法較傳統遺傳算法獲得最優解迭代次數更小、平均迭代計算時間更短、收斂速度更快、收斂精度更高。改進遺傳算法表現出顯著的優化效果。

表1 算法的收斂性能比較

3 結論

航空運輸路徑規劃關系到物流運輸成本，對物流行業的可持續發展具有重要影響。本文引入遺傳算法對路徑進行優化，并對遺傳算法進行改進，建立航空物流運輸線路的數學優化模型；通過自適應變異方法提升變異差異，避免模型算法陷入局部最優解，提升收斂精度；引入模擬退火算法的Metropolis準則，提升路徑規劃效率，達到尋找最優路徑的目標。應用于航空路徑多樞紐物流路徑規劃的結果表明，改進算法可獲得運輸路徑最短的目標值，具有較高的實際應用價值。