李龍海，姚金程

（中國(guó)民航大學(xué)機(jī)場(chǎng)學(xué)院，天津 300300）

隨著國(guó)內(nèi)民用航空業(yè)的迅猛發(fā)展，航班密度也在逐年增加，航班流量不斷增加給機(jī)場(chǎng)的運(yùn)行管理帶來(lái)了極大挑戰(zhàn)。停機(jī)位是機(jī)場(chǎng)運(yùn)行的重要資源，是飛機(jī)在地面的主要保障區(qū)域。停機(jī)位分配是機(jī)場(chǎng)資源配置的重要部分，合理的停機(jī)位分配可以有效提高停機(jī)位利用率和機(jī)場(chǎng)的運(yùn)行效率，降低航班延誤率和停機(jī)位運(yùn)行風(fēng)險(xiǎn)。如何安全高效地分配停機(jī)位資源成為了現(xiàn)階段停機(jī)位分配問(wèn)題的重要研究方向。

近些年，國(guó)內(nèi)外針對(duì)停機(jī)位分配問(wèn)題的研究較多：馬思思等[1]將航空器地面滑行距離最小作為優(yōu)化目標(biāo)建立停機(jī)坪分配模型，并通過(guò)實(shí)驗(yàn)仿真驗(yàn)證了模型的有效性；楊新湦等[2]結(jié)合進(jìn)離場(chǎng)航班的運(yùn)行特點(diǎn)，建立了停機(jī)位和機(jī)場(chǎng)滑行路徑的臨時(shí)改派雙層規(guī)劃模型，以此來(lái)解決停機(jī)位和滑行路徑的臨時(shí)改派對(duì)于整個(gè)機(jī)場(chǎng)運(yùn)行造成的擾動(dòng)問(wèn)題；馮霞等[3]以緩沖時(shí)間成本最小為目標(biāo)確立了停機(jī)位分配魯棒性的評(píng)價(jià)函數(shù)，建立停機(jī)位分配魯棒性模型以實(shí)現(xiàn)緩沖時(shí)間成本最小、停機(jī)位-航班匹配度最高和遠(yuǎn)機(jī)位使用率最低等優(yōu)化目標(biāo)，并使用禁忌搜索算法進(jìn)行求解；Kim 等[4]以預(yù)期停機(jī)位沖突時(shí)間總和最小為目標(biāo)，建立了一種停機(jī)位空閑時(shí)間與預(yù)期停機(jī)位沖突的指數(shù)關(guān)系模型并進(jìn)行停機(jī)位魯棒性指派。

現(xiàn)階段的國(guó)內(nèi)外研究成果中，針對(duì)停機(jī)位分配的研究主要是從提高機(jī)場(chǎng)運(yùn)行效率[5-8]和降低延誤成本角度考慮[9-10]，對(duì)由空域和放行原因?qū)桨嗤瞥鰶_突可能導(dǎo)致的安全風(fēng)險(xiǎn)考慮較少，部分研究以機(jī)場(chǎng)運(yùn)行效率最大化為前提條件，進(jìn)一步加入了安全約束，得到的方案提高了安全性[11]，但這種方法更適用于流量不大、停機(jī)位資源較充足的中小型機(jī)場(chǎng)。相比于中小型機(jī)場(chǎng)，繁忙的大型機(jī)場(chǎng)可能很難找到完全滿(mǎn)足最小安全間隔時(shí)間的最優(yōu)解，因此，設(shè)置一個(gè)航班沖突時(shí)間最少的目標(biāo)函數(shù)是必要的。

本文以遠(yuǎn)機(jī)位使用率和停機(jī)位分配魯棒性作為上層模型的優(yōu)化目標(biāo)，以相同停機(jī)位、相鄰航班推出沖突時(shí)間作為下層模型的優(yōu)化目標(biāo)，建立雙層規(guī)劃模型[12-13]。在提高機(jī)場(chǎng)運(yùn)行效率的同時(shí)降低相同停機(jī)位、相鄰航班的運(yùn)行風(fēng)險(xiǎn)，兼顧了停機(jī)位分配的效率和運(yùn)行安全，最后使用Matlab 對(duì)雙層規(guī)劃模型進(jìn)行驗(yàn)證。

1 停機(jī)位分配模型

1.1 停機(jī)位分配沖突概述

由于航班沖突的情況較為復(fù)雜，選擇機(jī)場(chǎng)繁忙情況較為普遍且可研究性較高的相同停機(jī)位、相鄰航班沖突問(wèn)題進(jìn)行深入分析[14]。假設(shè)繁忙大型機(jī)場(chǎng)某一天的高峰時(shí)段航班流量超過(guò)了機(jī)場(chǎng)自身的容量限制，在進(jìn)行停機(jī)位預(yù)分配階段無(wú)法找到讓所有航班都滿(mǎn)足最小安全間隔時(shí)間的分配方案。例如將航班A 和B都分配到停機(jī)位h 停靠，航班A 預(yù)計(jì)到達(dá)時(shí)間為a1，預(yù)計(jì)起飛時(shí)間為d1，航班B 預(yù)計(jì)到達(dá)時(shí)間為a2，預(yù)計(jì)起飛時(shí)間為d2。很明顯，當(dāng)航班A 的起飛時(shí)間加上最小安全間隔時(shí)間大于航班B 的預(yù)計(jì)到達(dá)時(shí)間時(shí)，兩個(gè)航班的實(shí)際間隔時(shí)間小于最小安全間隔時(shí)間，會(huì)出現(xiàn)停機(jī)位沖突。沖突時(shí)間[15]設(shè)定為航班B 實(shí)際進(jìn)入和預(yù)計(jì)進(jìn)入停機(jī)位h 的時(shí)間差。圖1 所示為相同停機(jī)位、相鄰航班沖突可能出現(xiàn)的時(shí)間分布圖。

圖1 相同停機(jī)位、相鄰航班沖突分布圖Fig.1 Diagram of conflict distribution of the adjacent flights at the same gate

1.2 假設(shè)條件

為了便于問(wèn)題的研究和解決，做出以下假設(shè)：①選取繁忙機(jī)場(chǎng)某一天的高峰時(shí)段來(lái)進(jìn)行研究。高峰時(shí)段的航班流量在機(jī)場(chǎng)容量可接受的范圍內(nèi)，即每個(gè)航班都可以被分配到停機(jī)位，但相同停機(jī)位、相鄰航班的間隔時(shí)間可能會(huì)小于最小安全間隔時(shí)間；②在停機(jī)位分配時(shí)，所有需要的相關(guān)信息均已知；③停機(jī)位的分配遵循先到先服務(wù)的原則。

1.3 相關(guān)參數(shù)

假定：航班集合為N，停機(jī)位集合為M；航班數(shù)量為n，停機(jī)位數(shù)量為m；ai、di表示航班i 的預(yù)計(jì)到達(dá)時(shí)間和預(yù)計(jì)起飛時(shí)間；ok、ck是停機(jī)位k 的計(jì)劃開(kāi)始使用時(shí)間和計(jì)劃停止使用時(shí)間；Ri表示航班i 的機(jī)型；Gk表示停機(jī)位k 允許?？康臋C(jī)型集合；Q 表示遠(yuǎn)機(jī)位的集合。

V（i）表示在航班i 位于機(jī)場(chǎng)期間始終處于開(kāi)啟狀態(tài)的停機(jī)位集合，V（i）={k|ok≤ai≤di≤ck，?k∈{1，2，…，m}；U（i）表示預(yù)計(jì)到達(dá)時(shí)間晚于航班i 的預(yù)計(jì)到達(dá)時(shí)間且與航班i 有時(shí)間沖突的航班集合，U（i）= { j|ai≤aj≤di，?j∈{i+1，i+2，…，n}；F（i）表示航班i 可?？康耐C(jī)位集合，F(xiàn)（i）={k|Ri∈Gk，?k∈V（i）}；E（i）表示航班i 不能?？康耐C(jī)位集合，E（i）={k|?k?F（i）}。

si，j，k表示停機(jī)位k 的空閑時(shí)間，其中?i∈{1，2，…，n-1，j∈{i+1，i+2，…，n}，即

航班i 和j 連續(xù)分配到停機(jī)位k 上時(shí)，?i ∈{1，2，…，n-1}，j∈{i+1，i+2，…，n}，假定δ 表示最小安全間隔時(shí)間，航班i 從停機(jī)位k 推出時(shí)與航班j 發(fā)生沖突的時(shí)間長(zhǎng)度可表示為

xi，k為決策變量，當(dāng)航班i 被分配到停機(jī)位k 時(shí)，xi，k=1，否則設(shè)為0。yi，j，k也為決策變量，表示相同停機(jī)位k 上航班i 和j 的變量聯(lián)系，當(dāng)出現(xiàn)航班i 和j 接連被分配到停機(jī)位k 上，同時(shí)航班i 的到達(dá)時(shí)刻早于航班j 的情況時(shí)，yi，j，k=1，否則設(shè)為0。

2 雙層規(guī)劃模型

2.1 上層模型

上層模型是以機(jī)場(chǎng)運(yùn)行效率最大為目標(biāo)的停機(jī)位分配模型，其目標(biāo)函數(shù)的最優(yōu)解影響下層模型的求解。遠(yuǎn)機(jī)位使用率是指航班被分配到遠(yuǎn)機(jī)位的數(shù)量占比，機(jī)位空閑時(shí)間[16]是指前一個(gè)航班預(yù)計(jì)起飛時(shí)間與后一個(gè)航班預(yù)計(jì)到達(dá)時(shí)間的時(shí)間差。在機(jī)場(chǎng)運(yùn)行中，降低遠(yuǎn)機(jī)位使用率[17]有利于減少旅客的步行距離，既提高了旅客的服務(wù)質(zhì)量又在一定程度上增加了機(jī)場(chǎng)的運(yùn)行效率；保證機(jī)位分配時(shí)間的均衡可以提高停機(jī)位分配系統(tǒng)的魯棒性，考慮到相同停機(jī)位、相鄰航班發(fā)生沖突對(duì)停機(jī)位分配系統(tǒng)魯棒性的影響，將機(jī)位空閑時(shí)間平方和最小作為保證停機(jī)位分配魯棒性的決策目標(biāo)。經(jīng)過(guò)分析可知，降低遠(yuǎn)機(jī)位使用率在一定程度上會(huì)造成距離稍遠(yuǎn)的機(jī)位空閑時(shí)間過(guò)長(zhǎng)[18]，并進(jìn)一步影響到系統(tǒng)的魯棒性，兩個(gè)指標(biāo)相互之間存在一定的矛盾，需對(duì)兩個(gè)決策目標(biāo)設(shè)置相應(yīng)權(quán)重[19]。具體模型如下

式中：ω 是遠(yuǎn)機(jī)位使用率的權(quán)重，ω∈[0，1]；p1和p2分別表示遠(yuǎn)機(jī)位使用率和機(jī)位空閑時(shí)間平方和，p1=，采用min-max 標(biāo)準(zhǔn)化法對(duì)不同量綱的兩個(gè)決策目標(biāo)進(jìn)行歸一化處理。約束條件中：式（2）表示唯一性約束，即同一航班只能分配在同一停機(jī)位上；式（3）表示機(jī)型匹配約束，即不同機(jī)型的航班只能停靠在滿(mǎn)足機(jī)型許可范圍的停機(jī)位上；式（4）表示獨(dú)占性約束，即每個(gè)機(jī)位同一時(shí)間最多只能停放一個(gè)航班。

2.2 下層模型

以相同停機(jī)位、相鄰航班推出沖突總時(shí)間最小為目標(biāo)函數(shù)建立停機(jī)位分配下層模型，上層模型變量的變化會(huì)影響到下層模型的最優(yōu)解。當(dāng)后續(xù)航班j 的預(yù)計(jì)到達(dá)時(shí)間減前個(gè)航班i 的預(yù)計(jì)起飛時(shí)間小于規(guī)定的最小安全間隔時(shí)間時(shí)，則此相鄰的兩個(gè)航班發(fā)生了停機(jī)位沖突，設(shè)定所有發(fā)生沖突的后續(xù)航班實(shí)際進(jìn)入和預(yù)計(jì)進(jìn)入停機(jī)位的時(shí)間差為航班沖突總時(shí)間。具體模型如下

式中yi，j，k來(lái)自上層模型的求解結(jié)果，體現(xiàn)了上下層的數(shù)據(jù)傳輸。發(fā)生沖突時(shí)，沖突時(shí)間Ti，j，k增加會(huì)間接導(dǎo)致該停機(jī)位的空閑時(shí)間si，j，k增加，上、下層模型之間存在一定的變量聯(lián)系。約束條件中：式（6）和式（7）表示每個(gè)航班只能分配一個(gè)停機(jī)位且該航班的機(jī)型必須在停機(jī)位允許范圍內(nèi)；式（8）表示獨(dú)占性約束，即每個(gè)停機(jī)位同一時(shí)間最多只能停放一個(gè)航班；式（9）和式（10）代表決策變量之間的邏輯關(guān)系。

3 算法實(shí)現(xiàn)

遺傳算法具有流程簡(jiǎn)單、易計(jì)算等特點(diǎn)，非常適合用來(lái)解決組合優(yōu)化中的NP（non-deterministic polynomial）問(wèn)題[20]。本文使用遺傳算法對(duì)停機(jī)位雙層規(guī)劃模型進(jìn)行計(jì)算求解，詳細(xì)計(jì)算流程如下。

1）初始種群生成

采用整數(shù)編碼方式，將從機(jī)場(chǎng)采集的航班時(shí)刻等數(shù)據(jù)根據(jù)時(shí)間前后進(jìn)行排序，然后對(duì)其編碼，產(chǎn)生種群的個(gè)體染色體，如圖2 所示。其中，航班序號(hào)代表染色體中的基因序號(hào)，每個(gè)航班被安排的停機(jī)位編號(hào)代表基因的數(shù)值，染色體的個(gè)數(shù)為S。如第1 個(gè)基因序號(hào)為1，對(duì)應(yīng)的基因數(shù)值為k1，則表示序號(hào)為1 的航班被安排在停機(jī)位k1停靠。由于只對(duì)停機(jī)位分配問(wèn)題進(jìn)行研究，所以上下層模型產(chǎn)生的個(gè)體染色體結(jié)構(gòu)一致。

圖2 染色體結(jié)構(gòu)示意圖Fig.2 Diagram of chromosome structure

2）適應(yīng)度函數(shù)設(shè)置

按照上、下層模型的目標(biāo)函數(shù)設(shè)置適應(yīng)度函數(shù)，并根據(jù)適應(yīng)度值對(duì)每個(gè)個(gè)體進(jìn)行評(píng)估。

3）個(gè)體選擇概率計(jì)算

使用輪盤(pán)賭選擇法，根據(jù)適應(yīng)度值大小來(lái)計(jì)算選擇概率，即適應(yīng)度越大，選擇概率就越大，直接通過(guò)概率對(duì)個(gè)體進(jìn)行選擇。個(gè)體的選擇概率計(jì)算如下

式中：pg表示個(gè)體g 的選擇概率；Wg表示個(gè)體g 的適應(yīng)度值。

4）染色體交叉

采用單點(diǎn)交叉的方式，即在兩個(gè)不同染色體的隨機(jī)相同位置處設(shè)置一個(gè)交叉點(diǎn)并兩兩相交，子代染色體的左右兩側(cè)分別來(lái)自于父代染色體，選中的父代個(gè)體以交叉概率pc進(jìn)行交叉并產(chǎn)生子代。

5）染色體變異

在染色體交叉完成后即可獲得下一代染色體，對(duì)于其中不滿(mǎn)足要求的個(gè)體需要通過(guò)變異操作來(lái)進(jìn)行調(diào)整。在交叉過(guò)后形成的新個(gè)體，有一定的概率會(huì)發(fā)生基因變異，這個(gè)概率稱(chēng)為變異概率pm，為了保證好的解不會(huì)有過(guò)多變形，設(shè)pm≤0.05。

4 實(shí)例分析

現(xiàn)將上述模型和算法應(yīng)用于某實(shí)際運(yùn)行機(jī)場(chǎng)的停機(jī)位分配，該機(jī)場(chǎng)共有103 個(gè)停機(jī)位，統(tǒng)計(jì)到的機(jī)場(chǎng)高峰小時(shí)容量為39 架次。假設(shè)在早晚高峰時(shí)段開(kāi)始時(shí)均有63 個(gè)停機(jī)位處于占用狀態(tài)，只能利用剩余的40 個(gè)停機(jī)位進(jìn)行分配，其中，1～10 號(hào)停機(jī)位及21～40 號(hào)停機(jī)位為近機(jī)位，其余均為遠(yuǎn)機(jī)位。選取機(jī)場(chǎng)某天早晚高峰時(shí)段8：00—10：00 和19：00—21：00 的進(jìn)離港航班數(shù)據(jù)作為樣本，航班數(shù)量分別為82 架和85架，相比于機(jī)場(chǎng)的高峰小時(shí)容量，可以發(fā)現(xiàn)這兩個(gè)時(shí)段內(nèi)的航班流量均在一定程度上超出了機(jī)場(chǎng)自身的容量限制。

由于求解過(guò)程大致相同且篇幅有限，只列出早高峰時(shí)段的進(jìn)離港航班時(shí)刻信息如表1 所示。每個(gè)停機(jī)位的早晚高峰開(kāi)放時(shí)間分別為8：00 和19：00，停機(jī)位關(guān)閉時(shí)間分別為早晚高峰時(shí)段最后一個(gè)航班離開(kāi)停機(jī)位的時(shí)間。設(shè)定早晚高峰時(shí)段的開(kāi)始時(shí)間為00：00，Ai表示航班i 預(yù)計(jì)到達(dá)時(shí)間00：00 的分鐘數(shù)，Di表示航班i 預(yù)計(jì)起飛時(shí)間距離00：00 的分鐘數(shù)；I 表示航班編號(hào)；M 表示機(jī)型，1 表示小型航班，2 表示大型航班；1～28 號(hào)停機(jī)位為D 類(lèi)及以上停機(jī)位，可以?？克蓄?lèi)型的航班；29～40 號(hào)停機(jī)位為C 類(lèi)及以下停機(jī)位，僅能?？啃⌒秃桨唷ＴO(shè)最小安全間隔時(shí)間為8 min，遠(yuǎn)機(jī)位使用率的權(quán)重ω=0.5。

表1 早高峰時(shí)段進(jìn)離港航班時(shí)刻信息Tab.1 Flight info for arrivals and departures at morning rush hour

利用Matlab 軟件中的遺傳算法工具箱進(jìn)行計(jì)算，設(shè)置種群數(shù)量為50，最大進(jìn)化代數(shù)為100，選擇方式為輪盤(pán)賭選擇法，交叉方式為單點(diǎn)交叉，交叉概率pc=0.9，變異概率pm=0.04。

根據(jù)原計(jì)劃和基于雙層規(guī)劃模型所得到的早高峰時(shí)段停機(jī)位分配甘特圖如圖3（a）和圖3（b）所示。

圖3 停機(jī)位分配甘特圖Fig.3 Gantt chart of gate assignment information

按照同樣的步驟對(duì)晚高峰時(shí)段的航班數(shù)據(jù)進(jìn)行仿真計(jì)算，得到的早晚高峰時(shí)段遠(yuǎn)機(jī)位使用情況和航班沖突時(shí)間如表2 所示。

從表2 中可看出，利用雙層規(guī)劃模型優(yōu)化后的遠(yuǎn)機(jī)位使用情況和航班沖突時(shí)間均有所減少。早高峰時(shí)段遠(yuǎn)機(jī)位的使用降低了31.25%，原計(jì)劃下的沖突航班包括航班34 和60、航班22 和36、航班50 和68 等共11 對(duì)，優(yōu)化后的沖突航班有6 對(duì)，沖突時(shí)間減少16 min。晚高峰時(shí)段遠(yuǎn)機(jī)位的使用降低了23.53%，原計(jì)劃下的沖突航班包括航班39 和67、航班43 和78、航班47和80 等共11 對(duì)，優(yōu)化后的沖突航班有7 對(duì)，沖突時(shí)間減少了24 min。在提高機(jī)場(chǎng)運(yùn)行效率的同時(shí)有效降低了停機(jī)位運(yùn)行風(fēng)險(xiǎn)，保障了停機(jī)位運(yùn)行安全，適用于實(shí)際運(yùn)行中高峰時(shí)段較為繁忙的大型機(jī)場(chǎng)。圖4 所示為算法收斂曲線(xiàn)，可以看出，隨著迭代次數(shù)的增加，目標(biāo)函數(shù)值也在不斷被優(yōu)化，算法在30 代左右收斂。

圖4 算法收斂曲線(xiàn)Fig.4 Curve of algorithm convergence

表2 早晚高峰時(shí)段停機(jī)位分配結(jié)果對(duì)比Tab.2 Comparison of gate assignment results in morning and evening peak hours

5 結(jié)語(yǔ)

在總結(jié)國(guó)內(nèi)外停機(jī)位分配研究的基礎(chǔ)上，以遠(yuǎn)機(jī)位使用率和停機(jī)位分配魯棒性作為上層模型的優(yōu)化目標(biāo)，以相同停機(jī)位、相鄰航班推出沖突時(shí)間作為下層模型的優(yōu)化目標(biāo)，建立了雙層規(guī)劃模型并運(yùn)用遺傳算法進(jìn)行求解。通過(guò)實(shí)際算例分析發(fā)現(xiàn)，優(yōu)化后的早晚高峰時(shí)段遠(yuǎn)機(jī)位使用分別降低了31.25%和23.53%，停機(jī)位沖突時(shí)間分別減少了16 min 和24 min，在提高機(jī)場(chǎng)運(yùn)行效率的同時(shí)減少了相同停機(jī)位、相鄰航班間的運(yùn)行沖突，驗(yàn)證了雙層規(guī)劃模型的有效性。停機(jī)位分配問(wèn)題一直是一個(gè)復(fù)雜的NP 問(wèn)題，該優(yōu)化方法可以為大型繁忙機(jī)場(chǎng)運(yùn)行效率提升、停機(jī)位運(yùn)行風(fēng)險(xiǎn)降低提供解決方案和技術(shù)支持。