基于遺傳算法的航空物流配送路徑優(yōu)化分析

楊曉康，宋秀峰

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

0 引言

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

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

基于此，本文對傳統(tǒng)遺傳算法進(jìn)行優(yōu)化，針對航空物流種群數(shù)量單一、已陷入局部最優(yōu)解的問題，提出1種自適應(yīng)變異方法。該方法對傳統(tǒng)遺傳算法進(jìn)行了算法改進(jìn)以保證算法的收斂性，并引入Metorpolis準(zhǔn)則以提升算法的搜索能力，實(shí)現(xiàn)了航空物流配送路徑的優(yōu)化。

1 算法描述

1.1 遺傳算法

遺傳算法是通過模仿生物界遺傳規(guī)律構(gòu)建的1種全局搜索方法。遺傳算法首先根據(jù)適應(yīng)度值選擇合適的初始染色體，然后利用交叉變異形成下一代染色體，再由反復(fù)迭代計(jì)算獲得下一代種群，最后將最優(yōu)個(gè)體作為最優(yōu)解。圖1為1個(gè)標(biāo)準(zhǔn)的遺傳算法流程圖。

圖1 遺傳算法流程圖

1.1.1 初始種群編碼

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

(1)

式中：xi和yi分別為初始個(gè)體和子代個(gè)體的二進(jìn)制編碼。

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

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

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

(2)

由Fs形成1個(gè)隨機(jī)數(shù)K，將各個(gè)體適應(yīng)度累加到超過Fs后，選擇最后1個(gè)個(gè)體作為被選擇對象。

1.1.2 遺傳交叉和變異

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

圖2 單點(diǎn)交叉操作示意圖

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

(3)

對交叉、變異后的個(gè)體進(jìn)行適應(yīng)度評(píng)估，并保留適應(yīng)度高的個(gè)體。由于適應(yīng)度函數(shù)要求滿足非負(fù)特性[15]，選擇適應(yīng)度函數(shù)為：

(4)

式中：N為種群個(gè)體數(shù)。

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

(5)

1.2 算法改進(jìn)

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

在進(jìn)行變異適應(yīng)度改進(jìn)時(shí)，若當(dāng)前種群多樣性較好，不發(fā)生提前收斂，則放棄變異操作。若種群提前收斂，則根據(jù)多樣性情況分別處理。①種群多樣性較差，則根據(jù)自適應(yīng)變異進(jìn)行變異操作。②種群多樣性幾乎沒有，則引進(jìn)新的物種，增強(qiáng)變異的差異。

交叉概率Pc和變異概率Pm對算法收斂性有影響。當(dāng)Pc、Pm值較大時(shí)，則收斂速度較快，部分適應(yīng)度較高的個(gè)體遭到破壞，易陷入局部最優(yōu)解；當(dāng)Pc、Pm值較小時(shí)，則產(chǎn)生新個(gè)體速度較慢，易出現(xiàn)搜索停滯[12]。因此，利用自適應(yīng)原則來選擇Pc、Pm。其計(jì)算式為：

(6)

式中：Favg為種群平均適應(yīng)度；Pc_max、Pc_min分別為最大、最小交叉概率;E為總迭代數(shù)；e為當(dāng)前迭代數(shù)；F為個(gè)體適應(yīng)度。

(7)

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

當(dāng)個(gè)體適應(yīng)度小于平均適應(yīng)度時(shí)，通過進(jìn)行交叉、變異操作，賦予交叉適應(yīng)度個(gè)體較大交叉和較小變異概率。當(dāng)個(gè)體適應(yīng)度大于平均適應(yīng)度時(shí)，則根據(jù)優(yōu)良程度設(shè)置交叉變異概率，從而避免提前收斂。

當(dāng)種群變異改良后，引入模擬退火算法的改進(jìn)Metropolis準(zhǔn)則判定是否接受變異后個(gè)體。原有計(jì)算式為：

(8)

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

T0的衰減方式?jīng)Q定著速度和準(zhǔn)確性。本文采用指數(shù)降溫方式。式(9)為T0的衰減函數(shù):

t=δnT0

(9)

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

當(dāng)n比較小時(shí)，溫度的下降速度快。當(dāng)n比較大時(shí)，溫度的下降速度慢。通過選擇適當(dāng)?shù)摩闹悼梢钥刂茰囟鹊南陆邓俣?。改進(jìn)后的計(jì)算式為：

(10)

通過Metropolis準(zhǔn)則保證種群搜索能力，可避免陷入局部最優(yōu)解。

2 航空物流運(yùn)輸路徑優(yōu)化

2.1 模型建立

航空運(yùn)輸依托航空公司航線來實(shí)現(xiàn)物流運(yùn)輸。路徑規(guī)劃的關(guān)鍵是以最短路徑為目標(biāo)，獲得最優(yōu)化的航空運(yùn)輸路徑。在建立模型前，需假設(shè)n個(gè)機(jī)場的最大覆蓋率和機(jī)場間距都是已知的，模型中存在P個(gè)直通航路的樞紐城市，建立起最優(yōu)路徑下的n個(gè)機(jī)場和P個(gè)樞紐城市間的表達(dá)式為：

(11)

(12)

(13)

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

(14)

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

2.2 算法仿真測試

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

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

圖3 不同算法的最優(yōu)路徑

將改進(jìn)算法與傳統(tǒng)遺傳算法的收斂性能進(jìn)行比較，算法的收斂性能比較如表1所示。由表1可知，改進(jìn)后的遺傳算法較傳統(tǒng)遺傳算法獲得最優(yōu)解迭代次數(shù)更小、平均迭代計(jì)算時(shí)間更短、收斂速度更快、收斂精度更高。改進(jìn)遺傳算法表現(xiàn)出顯著的優(yōu)化效果。

表1 算法的收斂性能比較

3 結(jié)論

航空運(yùn)輸路徑規(guī)劃關(guān)系到物流運(yùn)輸成本，對物流行業(yè)的可持續(xù)發(fā)展具有重要影響。本文引入遺傳算法對路徑進(jìn)行優(yōu)化，并對遺傳算法進(jìn)行改進(jìn)，建立航空物流運(yùn)輸線路的數(shù)學(xué)優(yōu)化模型；通過自適應(yīng)變異方法提升變異差異，避免模型算法陷入局部最優(yōu)解，提升收斂精度；引入模擬退火算法的Metropolis準(zhǔn)則，提升路徑規(guī)劃效率，達(dá)到尋找最優(yōu)路徑的目標(biāo)。應(yīng)用于航空路徑多樞紐物流路徑規(guī)劃的結(jié)果表明，改進(jìn)算法可獲得運(yùn)輸路徑最短的目標(biāo)值，具有較高的實(shí)際應(yīng)用價(jià)值。