基于AGA的多目標停機位優(yōu)化分配

王晨曦，黃 辰

(沈陽航空航天大學(xué) 民用航空學(xué)院，沈陽 110136)

隨著國民經(jīng)濟的快速發(fā)展和人民生活水平的提高，航空運輸業(yè)在我國的交通運輸業(yè)中占據(jù)的比重也越來越大，民航逐漸成為人們出行的首選。但是機場的基礎(chǔ)設(shè)施建設(shè)與不斷增多的民航運輸需求量幾乎不成正比，因此造成機場服務(wù)設(shè)施短缺，尤其是機場的停機位資源已經(jīng)不堪重負。停機位作為機場的重要資源，是實現(xiàn)航班快速安全?？?、保證航班之間有效連接、提高整個機場服務(wù)效率和整個機場系統(tǒng)容量的一個重要因素。

針對機場停機位分配的問題，國內(nèi)外的學(xué)者已經(jīng)進行了深入的研究，并且取得了一些研究成果。Deng等[1]設(shè)計了一種基于生態(tài)協(xié)同進化策略和增強粒子群優(yōu)化的改進量子進化算法，將不同時間段的航班分配到了合適的停機位上。王丹琴[2]將改進的量子進化算法應(yīng)用到了停機位分配中，目標函數(shù)為旅客步行距離最短、停機位使用最充分和空閑時間最均衡。李蘋蘋等[3]將聚類與GA算法結(jié)合，建立以沖突調(diào)整率、航班靠橋率和機位預(yù)分配的魯棒性的多目標優(yōu)化模型，并且對目標函數(shù)采用線性加權(quán)法來設(shè)置各個目標的權(quán)重。李博[4]在模型中采用了一種基于遺傳算法和蟻群優(yōu)化算法相結(jié)合的兩階段算法。孫萌[5]提出了自適應(yīng)協(xié)同進化蟻群優(yōu)化算法，建立以機場和航空公司效益最大化以及旅客最滿意的停機位分配優(yōu)化模型。劉繼琳等[6]以停機位占有數(shù)量最小建立數(shù)學(xué)模型，并用遺傳算法進行求解。孫淑光等[7]結(jié)合遺傳與禁忌搜索算法兩者的優(yōu)點，建立以最小空閑時間的平方和最大機位使用效率的數(shù)學(xué)模型。李亞玲等[8]提出一種動態(tài)、靈活分配停機位的禁忌搜索算法，以停機位利用率最大化以及旅客行走距離最小化為目標。陳前等[9]在合理分配停機位空閑時間的基礎(chǔ)上，建立了避免沖突的停機位分配模型，用遺傳算法進行模型的求解。王春曉[10]基于PTVACO構(gòu)建以旅客步行最短、航班占有率最大以及停機位空閑時間最均衡的多目標優(yōu)化模型，并且采用加權(quán)法進行了無量化處理。Cheng[11]提出滿足動態(tài)和靜態(tài)指派的方法。Ding等[12]考慮過度約束停機位的條件。Nikulin等[13]將參考計劃的絕對偏差引入到模型中。Wang等[14]將航班分類后以最小化所有延誤航班再指派導(dǎo)致的干擾設(shè)置為目標研究停機位分配問題。Dormdorf等[15]基于啟發(fā)式算法進行求解停機位分配問題，大大提高了效率。Liu等[16]應(yīng)用序貫博弈以及混合集合規(guī)劃的方法對模型求解停機位分配問題，節(jié)省了時間。閆萍等[17]以最小化航班停機位分配的擾動性為優(yōu)化目標，建立停機位動態(tài)再分配混合整數(shù)規(guī)劃模型。

綜上，國內(nèi)外學(xué)者運用多種方法對停機位分配問題進行研究，優(yōu)化的目標主要是旅客行走距離最短、機場資源利用最大化、延誤等待時間最小化等。上述研究的約束條件中，某些軟約束會被當作硬約束來進行建模，從而會存在飛機分配不到停機位的情況發(fā)生。同時，采用進化算法在求解停機位優(yōu)化問題時仍存在收斂速度慢、陷入局部最優(yōu)等問題。因此，本文首先將最小化油耗和最大化靠橋率作為優(yōu)化目標，建立停機位分配的多目標優(yōu)化數(shù)學(xué)模型，綜合兩個目標對停機位優(yōu)化分配產(chǎn)生的影響。其次，引入一種適合全局搜索的自適應(yīng)遺傳算法，使用分段階梯函數(shù)來優(yōu)化交叉、變異算子，并且對適應(yīng)度函數(shù)進行動態(tài)線性標定，確保在迭代初期，種群中每一個個體都有尋優(yōu)的機會，從而提高算法的能力。最后，通過仿真結(jié)果驗證所提出的模型和算法能夠得到合理有效的停機位分配方案。

1 多目標停機位分配模型

1.1 問題假設(shè)

停機位分配涉及到的影響因素較多，為方便計算機仿真，作出如下假設(shè)：

(1) 假設(shè)信息完整：所有要研究的航班機位信息齊全，然后按照這些信息來安排航班，分配停機位；

(2) 假設(shè)時間段有限：由于停機位分配是一個實時動態(tài)的情況，相鄰的兩航班之間的狀態(tài)會相互影響，如果不設(shè)定時間段很難求出最優(yōu)的解決方案。因此，假設(shè)只分配一個時間段內(nèi)的飛機，就可以求出最優(yōu)解；

(3) 假設(shè)機場停機位容量夠用：在研究的航班數(shù)和時間范圍內(nèi)，機場機位足夠所有飛機?？浚床粫霈F(xiàn)機場超負荷的狀況。

1.2 目標函數(shù)

首先給出構(gòu)造模型所需要的符號、參數(shù)和變量的含義，如表1所示。

表1 問題參數(shù)與決策變量

飛機在起飛和著陸滑行過程中，會產(chǎn)生大量的滑行油耗，航空公司為了提高其效益希望減少這部分的消耗，飛機滑行平均油耗的目標函數(shù)為

(1)

此外，從資源利用方面來考慮，最大化靠橋率也就是最小化機位資源浪費?；诤桨嗫繕蚵蕵?gòu)建的目標函數(shù)為

(2)

綜上兩個單目標函數(shù)，用線性加權(quán)法對每一個子目標函數(shù)Fi(x)(i=1,2)賦值不同的權(quán)重wi(x)(i=1,2)，wi(x)的數(shù)值大小代表函數(shù)Fi(x)的重要程度。油耗量和靠橋率具有不同的量綱，因此不能簡單地設(shè)置權(quán)重因子來得到最終的多目標函數(shù)，需要對效用函數(shù)歸一化處理后才能進行計算。處理后的函數(shù)為

(3)

φi=max{|Fi(x)|}

(4)

其中:φi是規(guī)范化修正值，它起到將不同量綱的目標進行歸一化處理的作用，使得不同的量綱的函數(shù)可以放到一個函數(shù)式子進行求解。

將式(1)、(2)同式(3)聯(lián)立，便可以得到最終的多目標停機位分配研究的總函數(shù)

(5)

目標函數(shù)中的第一項為飛機滑行的平均油耗，第二項為飛機的最大化靠橋率。

1.3 約束條件

(1)在某一個時間范圍內(nèi)，一個停機位只能被一個航班占用。

(6)

(2)當航班i?？吭谕C位k上時，yik=1，否則yik=0。

yik∈{0,1}?i∈N,k∈M

(7)

(3)判斷兩個航班是否連續(xù)使用同一個停機位。其中sijk是一個0-1決策變量，當?shù)趈個航班在第i個航班離開停機位k之后進入停機位k，則sijk=1，否則為0。

sijk∈{0,1} ?i,j∈N,k∈M

(8)

(9)

(10)

(4)每一個航班進入停機位之前，最多有且只有一個相鄰的前序航班，航班離開停機位之后，最多有且只有一個后繼航班。

(11)

(12)

(5)兩個進港的航班不能同一時間都分配給同一個停機位。

sijk+sjik≤1 ?i,j∈N,?k∈M,i≠j

(13)

(6)飛機的進港時刻一定小于它的離港時刻。

(14)

2 自適應(yīng)遺傳算法

2.1 機位分配編碼

在解決停機位分配的實際問題上，因為航班的數(shù)量過多，如果使用二進制編碼，編碼過程較為復(fù)雜，所以采用整數(shù)編碼形式。假設(shè)有8個航班，4個停機位，每個進港的航班都已經(jīng)按照預(yù)計的進港時間先后順序進行排列，排列的序號即為航班的編碼，停機位也根據(jù)停機位編號的大小順序進行排序，如圖1所示。

圖1 航班所停靠的停機位整數(shù)編碼形式

2.2 動態(tài)線性標定適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的作用就是區(qū)分出個體的好壞，是選擇過程中的參考依據(jù)。本研究的目標為求解函數(shù)最小值，可以將多目標分配停機位分配的總函數(shù)Q取倒數(shù)轉(zhuǎn)換為遺傳算法中的適應(yīng)度函數(shù)

(15)

計算出個體之間的適應(yīng)度函數(shù)值大小有可能相近，導(dǎo)致算法的選擇功能被弱化。對上述公式進行動態(tài)線性標定，確保在開始迭代時，種群中每一個個體都有尋優(yōu)機會。隨著迭代次數(shù)的增加，優(yōu)秀的個體就會被保存下來，且計算不占用時間。適應(yīng)度函數(shù)公式如下

(16)

(17)

2.3 選擇算子

從已產(chǎn)生的歷史群體中以特定的概率選擇出優(yōu)良個體組建一個新的種群繼續(xù)繁衍下去，個體是否被選擇取決于其適應(yīng)度值大小，適應(yīng)度值越高，其被選擇去組建新種群的概率也越高。常見的選擇算子的方法有輪盤賭選擇法、錦標賽法、排序選擇法等。本文選擇輪盤賭選擇法，其在選擇個體時不根據(jù)個體的選擇概率，而是將所累積的概率進行選擇，且最終的選擇誤差很小。

2.4 自適應(yīng)交叉變異算子

隨著算法迭代次數(shù)的不斷增加，交叉和變異概率在這個過程中不斷調(diào)整，以產(chǎn)生更優(yōu)的個體。交叉操作實現(xiàn)基因的重組，變異操作實現(xiàn)基因的創(chuàng)新。交叉算子和變異算子之間相互配合，使得算法在多個局部空間達到收斂，最終可以提高全局收斂的速度和效果。如果當代的染色體的適應(yīng)度值較為集中，此時則需要更激烈的交叉和變異，提高交叉概率Pc和變異概率Pm，反之降低。自適應(yīng)調(diào)整的公式如下

(18)

(19)

其中:Fmax為進化過程中個體適應(yīng)度函數(shù)最大值；Favg為進化過程中個體適應(yīng)度平均值；F′為兩個個體中較大個體的適應(yīng)度函數(shù)值；F為待變異運算的個體適應(yīng)度函數(shù)值；Pc1>Pc2>Pc3,Pm1>Pm2>Pm3且為區(qū)間(0,1)內(nèi)的某個值，在優(yōu)化過程中自適應(yīng)調(diào)整。圖2、圖3為參數(shù)自適應(yīng)的調(diào)整過程。

圖2 自適應(yīng)的Pc概率

圖3 自適應(yīng)的Pm概率

自適應(yīng)的遺傳算法流程圖如圖4所示。

圖4 算法流程圖

3 仿真模擬計算

3.1 實驗環(huán)境及參數(shù)選擇

在仿真實驗中，自適應(yīng)遺傳算法的相關(guān)參數(shù)設(shè)置如表2所示。

現(xiàn)將自適應(yīng)遺傳算法應(yīng)用于國內(nèi)某機場的停機位分配，選取該機場某一天的航班和航班數(shù)據(jù)。待分配的航班數(shù)據(jù)如表3所示，該機場共有10個停機位，有40個航班需要?？俊C型的大小分別用L表示大機型，M表示中機型，S表示小機型。采用Matlab進行基于AGA的停機位分配實現(xiàn)，運行環(huán)境為一臺PC機，CPU為i5 7300，內(nèi)存8G，操作系統(tǒng)為Windows 10。

表2 自適應(yīng)遺傳算法的參數(shù)設(shè)置

表3 待分配的航班數(shù)據(jù)

3.2 實驗結(jié)果分析

運用自適應(yīng)遺傳算法對多目標停機位分配模型進行了停機位分配實驗，實驗一共進行了30次，對其中30次中最好的一組分配結(jié)果進行分析，得到的分配結(jié)果如表4所示，進一步生成的甘特圖如圖5所示。為了更直觀地展示停機位的占用情況，圖6給出了各停機位分配的航班數(shù)量。圖7為AGA得到的最大靠橋率的目標函數(shù)值曲線。圖8給出了AGA得到的最低油耗的目標函數(shù)值曲線。圖9為兩種算法在30次中運行中的平均目標函數(shù)值收斂曲線。

表4 停機位分配結(jié)果

圖5 基于AGA的停機位分配甘特圖

圖6 各停機位分配的航班數(shù)量

圖7 最大靠橋率的目標函數(shù)值曲線

圖8 最低油耗的目標函數(shù)值曲線

圖9 兩種算法收斂曲線

從以上的曲線中可以看出，在迭代次數(shù)達到163時，靠橋率達到85%，乘客出行方便。而在迭代次數(shù)為4時，飛機油耗達到最小，節(jié)約了航空公司成本。綜合靠橋率以及飛機油耗這兩個指標，在迭代次數(shù)達到111之后，最優(yōu)解趨于平穩(wěn)，也基本趨近收斂。與傳統(tǒng)的遺傳算法相比，最優(yōu)解優(yōu)化了3.47%。由此可見，AGA較好解決了停機位分配問題。

4 結(jié)論

本文針對民航運輸機場中的停機位分配問題進行了研究，結(jié)合停機位分配中實際的約束限制條件建立基于AGA的多目標停機位分配模型，優(yōu)化靠橋率及油耗，最后用Matlab進行仿真模擬實驗，仿真實驗結(jié)果表明了該方法的有效性。停機位分配問題是一個復(fù)雜的多目標多約束問題，綜合考慮一些其他目標或更多的約束條件，用智能優(yōu)化算法進一步優(yōu)化，并且在航班發(fā)生延誤時，或者由于機場、航空公司以及惡劣的天氣因素對停機位分配造成影響時，能夠動態(tài)地調(diào)整并確定更好的停機位分配方案是未來的研究方向。