基于雙層規(guī)劃模型的停機位沖突優(yōu)化研究

李龍海，姚金程

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

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

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

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

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

1 停機位分配模型

1.1 停機位分配沖突概述

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

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

1.2 假設(shè)條件

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

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

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

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

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

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

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

2 雙層規(guī)劃模型

2.1 上層模型

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

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

2.2 下層模型

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

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

3 算法實現(xiàn)

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

1）初始種群生成

采用整數(shù)編碼方式，將從機場采集的航班時刻等數(shù)據(jù)根據(jù)時間前后進(jìn)行排序，然后對其編碼，產(chǎn)生種群的個體染色體，如圖2 所示。其中，航班序號代表染色體中的基因序號，每個航班被安排的停機位編號代表基因的數(shù)值，染色體的個數(shù)為S。如第1 個基因序號為1，對應(yīng)的基因數(shù)值為k1，則表示序號為1 的航班被安排在停機位k1?？?。由于只對停機位分配問題進(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ù)適應(yīng)度值大小來計算選擇概率，即適應(yīng)度越大，選擇概率就越大，直接通過概率對個體進(jìn)行選擇。個體的選擇概率計算如下

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

4）染色體交叉

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

5）染色體變異

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

4 實例分析

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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