王晨曦，黃 辰

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

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

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

綜上，國內(nèi)外學者運用多種方法對停機位分配問題進行研究，優(yōu)化的目標主要是旅客行走距離最短、機場資源利用最大化、延誤等待時間最小化等。上述研究的約束條件中，某些軟約束會被當作硬約束來進行建模，從而會存在飛機分配不到停機位的情況發(fā)生。同時，采用進化算法在求解停機位優(yōu)化問題時仍存在收斂速度慢、陷入局部最優(yōu)等問題。因此，本文首先將最小化油耗和最大化靠橋率作為優(yōu)化目標，建立停機位分配的多目標優(yōu)化數(shù)學模型，綜合兩個目標對停機位優(yōu)化分配產(chǎn)生的影響。其次，引入一種適合全局搜索的自適應遺傳算法，使用分段階梯函數(shù)來優(yōu)化交叉、變異算子，并且對適應度函數(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)，機場機位足夠所有飛機?？?，即不會出現(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 自適應遺傳算法

2.1 機位分配編碼

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

圖1 航班所?？康耐C位整數(shù)編碼形式

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

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

(15)

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

(16)

(17)

2.3 選擇算子

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

2.4 自適應交叉變異算子

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

(18)

(19)

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

圖2 自適應的Pc概率

圖3 自適應的Pm概率

自適應的遺傳算法流程圖如圖4所示。

圖4 算法流程圖

3 仿真模擬計算

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

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

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

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

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

3.2 實驗結(jié)果分析

運用自適應遺傳算法對多目標停機位分配模型進行了停機位分配實驗，實驗一共進行了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é)果表明了該方法的有效性。停機位分配問題是一個復雜的多目標多約束問題，綜合考慮一些其他目標或更多的約束條件，用智能優(yōu)化算法進一步優(yōu)化，并且在航班發(fā)生延誤時，或者由于機場、航空公司以及惡劣的天氣因素對停機位分配造成影響時，能夠動態(tài)地調(diào)整并確定更好的停機位分配方案是未來的研究方向。