李龍海，姚金程

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

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

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

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

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

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

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

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

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

1.2 假設(shè)條件

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

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

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

V（i）表示在航班i 位于機(jī)場期間始終處于開啟狀態(tài)的停機(jī)位集合，V（i）={k|ok≤ai≤di≤ck，?k∈{1，2，…，m}；U（i）表示預(yù)計(jì)到達(dá)時間晚于航班i 的預(yù)計(jì)到達(dá)時間且與航班i 有時間沖突的航班集合，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 的空閑時間，其中?i∈{1，2，…，n-1，j∈{i+1，i+2，…，n}，即

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

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

2 雙層規(guī)劃模型

2.1 上層模型

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

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

2.2 下層模型

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

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

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

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

1）初始種群生成

采用整數(shù)編碼方式，將從機(jī)場采集的航班時刻等數(shù)據(jù)根據(jù)時間前后進(jìn)行排序，然后對其編碼，產(chǎn)生種群的個體染色體，如圖2 所示。其中，航班序號代表染色體中的基因序號，每個航班被安排的停機(jī)位編號代表基因的數(shù)值，染色體的個數(shù)為S。如第1 個基因序號為1，對應(yīng)的基因數(shù)值為k1，則表示序號為1 的航班被安排在停機(jī)位k1停靠。由于只對停機(jī)位分配問題進(jìn)行研究，所以上下層模型產(chǎn)生的個體染色體結(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)度值對每個個體進(jìn)行評估。

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

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

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

4）染色體交叉

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

5）染色體變異

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

4 實(shí)例分析

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

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

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

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

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

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

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

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

圖4 算法收斂曲線Fig.4 Curve of algorithm convergence

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

5 結(jié)語

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