王晨曦，黃 辰

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

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

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

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

1 多目標(biāo)停機(jī)位分配模型

1.1 問題假設(shè)

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

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

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

(3) 假設(shè)機(jī)場(chǎng)停機(jī)位容量夠用：在研究的航班數(shù)和時(shí)間范圍內(nèi)，機(jī)場(chǎng)機(jī)位足夠所有飛機(jī)?？?，即不會(huì)出現(xiàn)機(jī)場(chǎng)超負(fù)荷的狀況。

1.2 目標(biāo)函數(shù)

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

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

(5)

目標(biāo)函數(shù)中的第一項(xiàng)為飛機(jī)滑行的平均油耗，第二項(xiàng)為飛機(jī)的最大化靠橋率。

1.3 約束條件

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

(6)

(2)當(dāng)航班i停靠在停機(jī)位k上時(shí)，yik=1，否則yik=0。

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

(7)

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

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

(8)

(9)

(10)

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

(11)

(12)

(5)兩個(gè)進(jìn)港的航班不能同一時(shí)間都分配給同一個(gè)停機(jī)位。

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

(13)

(6)飛機(jī)的進(jìn)港時(shí)刻一定小于它的離港時(shí)刻。

(14)

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

2.1 機(jī)位分配編碼

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

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

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

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

(15)

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

(16)

(17)

2.3 選擇算子

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

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

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

(18)

(19)

其中:Fmax為進(jìn)化過程中個(gè)體適應(yīng)度函數(shù)最大值；Favg為進(jìn)化過程中個(gè)體適應(yīng)度平均值；F′為兩個(gè)個(gè)體中較大個(gè)體的適應(yīng)度函數(shù)值；F為待變異運(yùn)算的個(gè)體適應(yīng)度函數(shù)值；Pc1>Pc2>Pc3,Pm1>Pm2>Pm3且為區(qū)間(0,1)內(nèi)的某個(gè)值，在優(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 仿真模擬計(jì)算

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

圖5 基于AGA的停機(jī)位分配甘特圖

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

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

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

圖9 兩種算法收斂曲線

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

4 結(jié)論

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