劉海濱 王炬博 巴博圣 王瑞昕

摘要：為了提升機場停機坪分配的魯棒性，針對大型國際機場航班延誤常態(tài)化對機場運行穩(wěn)定性的影響，構(gòu)建了兩種整數(shù)線性規(guī)劃模型，并引入爬山算法與大鄰域搜索（LNS）元啟發(fā)式算法進行效能比較。同時，采用Monte Carlo方法對不同目標函數(shù)在處理航班沖突時的效果進行評估。測試結(jié)果表明LNS算法在提升大型機場停機位分配方案的魯棒性方面表現(xiàn)卓越，在求解速度和方案質(zhì)量上均有顯著提升。特別是，當以空閑時間的平方作為目標函數(shù)時，其效果尤為突出。

關(guān)鍵詞：停機位分配；固定作業(yè)問題；機場；組合優(yōu)化；大鄰域搜索；線性規(guī)劃

中圖分類號：U-9；V2?? 文獻標志碼：A?? 文章編號：1002-4026（2024）02-0104-13

A numerical comparison of methods for solving the gate allocation

problem based on robustness simulation

Abstract∶Frequent delays of flights at large international airports can affect their smooth operation， hence， the airport apron allocation problem needs to be robustly optimized. In this study， we proposed two integer linear-programing models for solving this problem and used two algorithms for performance comparison： the hill-climbing and large-neighborhood search （LNS） metaheuristic algorithms. In addition， we used the Monte Carlo method to evaluate the effectiveness of different objective functions in dealing with flight conflicts. The final test results show that the LNS algorithm not only improves the robustness of the gate allocation scheme for large airports but also excels in speed and quality， especially， when the square of idle time is used as the objective function.

Key words∶gate allocation； fixed job problem； airport；combinatorial optimization；large-neighborhood search； linear programing

隨著民用航空運輸業(yè)的蓬勃發(fā)展，高效合理地將有限的停機位分配給日益增加的航班成為大型機場資源調(diào)度的核心問題?？紤]到天氣變化及其他多種因素，航班延誤成為常見現(xiàn)象。特別是，前序航班的延誤可能導(dǎo)致后續(xù)分配至同一停機位的航班產(chǎn)生沖突，從而影響機場整體運營的平穩(wěn)性?；诖?，本研究專注于大型機場停機位分配方案的魯棒性，旨在最小化航班延誤對于停機位資源調(diào)度的負面影響。

在本研究中，我們將停機位分配問題（gate allocation problem， GAP）界定為一種固定作業(yè)調(diào)度問題（fixed job scheduling， FJS），其中，每架飛機均被視作一個具有確定到達及離開時間的作業(yè)。在理想情況下，若每個停機位能夠適配任何飛機型號，那么FJS問題可以轉(zhuǎn)化為最小化顏色數(shù)的區(qū)間圖著色問題，并可在多項式時間內(nèi)解決[1]。但實際情況是，由于停機位的大小不同，不是所有型號的飛機都能適配，因此大型機場的停機位分配問題實際上是一個NP（non-deterministic polynomial，非確定多項式）完全問題，即列表著色問題[2]。鑒于此，本文的研究重點是探索大型機場停機位的高效分配方案。

鑒于停機位分配問題在機場運營中的重要地位，國內(nèi)外學(xué)者對該問題進行了深入研究。Bolat[3]在1999年借助整數(shù)線性規(guī)劃（ILP）對該問題進行建模，由于當時缺乏解決ILP所需的計算能力，作者采用了分支定界法和啟發(fā)式算法的混合方法。2001年，Bolat[4]運用遺傳算法處理了更大規(guī)模的實例。隨后的研究進一步改進了Bolat的整數(shù)線性規(guī)劃模型[5-6]，通過減少約束條件的數(shù)量來實現(xiàn)求解速度的提升，另有研究應(yīng)用動態(tài)規(guī)劃、分支界限算法以及多目標遺傳算法對停機位偏好設(shè)置[7] 、停機坪利用率[8]、航空公司間的公平性[9]和乘客步行距離等[10-11]進行了優(yōu)化。

然而，考慮到機場日間不斷變化的運營需求，停機位分配算法需要實時響應(yīng)。目前最優(yōu)的精確算法尚不能對較大停機位分配問題實例進行快速求解。因此，本研究提出針對性的爬山算法和大鄰域搜索元啟發(fā)式算法，力求顯著提升停機位分配問題的求解效率和分配質(zhì)量，實現(xiàn)停機位分配方案的實時響應(yīng)。

1 數(shù)學(xué)模型

本研究首先對所研究的問題進行數(shù)學(xué)建模，隨后通過仿真方法對沖突時間的期望值進行分析。文章中所采用的符號注釋詳見表1。

將n個航班的集合定義為F，m個停機位的集合定義為G。為每個航班fi∈F分配一個停機位gk∈GiG，其中Gi是可以接受航班fi的停機位的集合。決策變量為xi∈［［1，m］[KG-2.8mm]］，i∈［［1，n］[KG-2.8mm]］。

其中，［［·］[KG-2.4mm]］表示區(qū)間內(nèi)取整數(shù)。對于優(yōu)化目標，本文聚焦最大限度提高飛機之間的空閑時間，以確保停機位分配方案的魯棒性。因此引入空閑時間的成本函數(shù)c。每次航班起飛前有一段空閑時間，同時每個停機位關(guān)閉前有額外的空閑時間，因此共有n+m個空閑時間。引入空閑時間變量Il，l∈［［1，n+m］[KG-2.8mm]］，則問題可以表述為：

文中的約束條件 （2） 旨在確保同一停機位上的飛機之間不會發(fā)生時間上的重疊，而約束條件 （3） 則限定每架航班必須被分配到與之兼容的停機位。正如前文所述，本研究提出了若干關(guān)于空閑時間的目標函數(shù)，并對這些函數(shù)對平均沖突時間的影響進行了比較分析。

1.1 目標函數(shù)

本研究采用Monte Carlo分析方法對給定航班時刻表的預(yù)期沖突時間進行模擬，并基于此比較了不同目標函數(shù)選擇對停機位分配方案魯棒性的實際影響。

1.1.1 預(yù)期沖突時間的估計

本研究的目標函數(shù)著眼于最大化停機位分配（gate allocation problem，GAP）方案的魯棒性，同時力求最小化預(yù)期沖突時間，即在同一時段內(nèi)兩架航班共享同一停機位的總時長。這種沖突通常發(fā)生在兩架分配至同一停機位的航班間存在較短空閑時間的情況下，其中一架航班的延誤可能導(dǎo)致兩架航班的停機時間發(fā)生重疊。因此，本文試圖將最小化沖突時間問題轉(zhuǎn)化為避免在停機位分配時刻表中出現(xiàn)短暫空閑時間的問題。

Bolat等 [3]和 YU等[11]，分別給出了不同的目標函數(shù)，來提升停機位分配的魯棒性，如最小化空閑時間的平方和等。對于停機位分配問題來說，最小化平方和函數(shù)實際上等同于最小化空閑時間的方差，詳見方程 （4） 。實際上，所有停機位占用的空閑時間總和與停機位分配方案本身是無關(guān)的，因此成本函數(shù)c不受時刻表的影響。

V（X）=EX2－E（X）2=EX2－C2～EX2（4）

其中V（X）表示空閑時間的方差，EX2表示空閑時間平方的期望，E（X）2表示空閑時間期望的平方，C為常數(shù)。最小化方差是指若所有空閑時間長度一致，則無法進一步降低短空閑時間的出現(xiàn)頻率，這在航班延誤的情況下更容易引發(fā)沖突。因此，通過最小化所有空閑時間的方差，可以有效減少短暫和過長空閑時間的數(shù)量。

為了驗證選取哪種目標函數(shù)能最有效提高停機位分配方案魯棒性，本文還需在給定的航班時刻表下模擬飛機延誤情況。Castaing等[12]對4種不同的成本函數(shù)進行了比較，這些函數(shù)旨在最小化飛機間的沖突，包括沖突次數(shù)、沖突總時間、沖突的最長持續(xù)時間以及因停機位占用沖突導(dǎo)致乘客錯過轉(zhuǎn)機的航班數(shù)。結(jié)果表明，通過最小化沖突總時間可以有效改善其他三個成本函數(shù)的表現(xiàn)。Yu等[11]和Slveling等[13]指出，對數(shù)正態(tài)分布能更準確地預(yù)測飛機到達或起飛的延誤時間。其中，Yu等[11]采用指數(shù)成本函數(shù)來最小化設(shè)定間隔時間內(nèi)的停機位預(yù)期沖突時間。Pérez-rodríguez等[14]的統(tǒng)計分析顯示，約77%的航班到達時間與計劃時間相差不超過15 min。

基于上述研究成果，本文選用對數(shù)正態(tài)分布來模擬航班的到達和離開延誤，并據(jù)此計算預(yù)期沖突時間。本文提出的估算預(yù)期沖突時間的Monte Carlo算法如下：

算法1 模擬沖突時間

輸入：給定的航班時刻表s，迭代次數(shù)N

本模擬方法的優(yōu)勢在于，其輸出結(jié)果可以直接反映停機位分配方案的魯棒性，原因是本研究能夠估算出特定調(diào)度方案下的沖突時間。然而，缺點在于計算時間較長，導(dǎo)致不適合作為算法的目標函數(shù)使用。因此，本文利用這一函數(shù)來評估結(jié)果的質(zhì)量，并比較不同的目標函數(shù)，從而確定哪一個最能滿足需求。

1.1.2 目標函數(shù)的選取

停機位分配的魯棒性在于其方案能否有效應(yīng)對由航班延誤等因素引起的潛在停機位占用沖突。航班延誤引發(fā)的主要問題是飛機對停機位的實際占用時間發(fā)生變化。因此，相較于簡單地為飛機分配停機位，更關(guān)鍵的是為分配到相鄰?fù)C坪的飛機設(shè)定較長的空閑時間。鑒于所有飛機對停機位的總占用時間是固定的，所有空閑時間的總和也相應(yīng)固定，意味著無法通過增加所有飛機間的空閑時間來提升停機位的魯棒性。本研究探索了以下三種優(yōu)化目標函數(shù)，空閑時間的平方函數(shù)和兩個遞減函數(shù)，并在2.2.2節(jié)中討論了三種目標函數(shù)對停機位分配魯棒性的提升效果。

（1）平方函數(shù)

R+→R+，II2。（5）

（2）指數(shù)函數(shù)

（3）指示函數(shù)

其中，S和S′是超參數(shù)。

在處理給定的空閑時間時，本文采用Yu等[11]中關(guān)于最小化預(yù)期沖突時間的指數(shù)函數(shù)，用以計算兩架航班發(fā)生沖突的概率。此外，指示函數(shù)作為約束短空閑時間的基本函數(shù)也被考慮在內(nèi)。若指示函數(shù)與指數(shù)函數(shù)在效果上相似，則優(yōu)先選擇簡單的指示函數(shù)。如圖1所示，展示了三種目標函數(shù)的結(jié)果，其中平方函數(shù)指的是空閑時間的平方與平均空閑時間平方之差，間接表示了以空閑時間平方為目標的函數(shù)。

1.2 線性規(guī)劃模型

對該問題的求解可以用線性規(guī)劃來模擬，本節(jié)提出了兩種不同的數(shù)學(xué)模型。

1.2.1 基本ILP模型

基于線性規(guī)劃的算法以及文獻[4]，本節(jié)首先提出一個基本ILP（integer linear programming，整數(shù)線性規(guī)劃）模型。在該模型中，使用二元決策變量xi，j，k，當飛機fj緊隨飛機fi分配在停機位gk時，xi，j，k=1，i =0和j=n+1表示停機位的第一個和最后一個虛擬飛機（x0，i，k表示飛機fi是?？吭谕C位gk的第一個飛機）。設(shè)所有二元決策變量xi，j，k所組成的集合為X，由于航班按起飛時間遞增排序，因此只考慮i

式（9）表明存在n+m個空閑時間。式（10）～（12）確保每架飛機都被分配了一個停機位；每架飛機都有一個前置飛機，即該停機位上的第一個虛擬飛機；每架飛機也有一個后置飛機，即該停機位上的最后一個虛擬飛機。式（13）～（15）則規(guī)定任意一架飛機只能被分配到同一個停機位上，避免出現(xiàn)多個停機位之間的分配重疊，并確保飛機類型與停機位的兼容性。然而，式（13）產(chǎn)生了O（n2m）個約束條件，這使得模型變得龐大并且求解時間較長。鑒于此，本文將介紹一種約束條件數(shù)量較少的模型。

1.2.2 多商品流模型

停機位分配問題可以看作有向無環(huán)圖G=（V，E）的多商品流問題

V=VF∪VsG∪VeG，（16）

E=EF∪EsG∪EeG。（17）

本文將停機位的開啟節(jié)點視為源節(jié)點，將停機位的關(guān)閉節(jié)點視為匯節(jié)點，式（16）中VF代表飛機節(jié)點，VsG代表停機位開啟節(jié)點，VeG代表停機位關(guān)閉節(jié)點。兩個節(jié)點vi和vj之間的邊e（vi，vk，k）表示飛機fj可以直接跟隨飛機fi并分配到停機位gk。式（17）中EF代表飛機之間的邊的集合，EsG代表停機位開啟與第一個飛機之間的邊的集合，EeG代表停機位最后一個飛機與停機位關(guān)閉節(jié)點之間的邊的集合，每個邊集的容量為{0，1}。

如圖2所示為一個停機位分配問題的實例圖。在該實例中，停機位g1可以停放飛機f1和f2，但不能停放飛機f3，而停機位g2可以接受所有飛機機型。飛機f1和f3是重疊的，因此這兩個飛機之間沒有相連的邊。本文將每個源節(jié)點k與其匯節(jié)點連接起來，使其流經(jīng)一組飛機。使用流量函數(shù)Φ：E→{0，1}來表示每條邊的取舍，并為每條邊設(shè)定空閑時間Ii，j，k的成本函數(shù)c（e）=c（vi，vj，k）。

故此，成本函數(shù)如式（18）所示，針對節(jié)點v，定義其進入邊和離開邊的集合分別對應(yīng)式（19）和式（20）。同時，式（21）～（23）描述了本模型的約束條件，確保每個停機位和飛機都被納入考慮范圍內(nèi)，并要求每架飛機被分配到唯一的停機位。此外，模型還要求任意一架飛機的前后飛機必須?？吭谕粋€停機位上。因此，如果流的源節(jié)點是停機位k，則存在一條離開邊連接到停機位k。

該模型的線性規(guī)劃模型表示如下，此模型使用與基本ILP模型相同的二元決策變量xi，j，k，式（24）所定義的目標函數(shù)保持不變。式（25）～（28）分別規(guī)定了每個源節(jié)點的流出量之和為1，這表示每個非空置的停機位都有第一個虛擬飛機；對于每個匯節(jié)點，流入量總和為1，確保每個非空置的停機位都有最后一個虛擬飛機；所有代表飛機的節(jié)點的流出量總和為1，表示該飛機之后只有一個飛機與之相連，或者該飛機指向一個匯節(jié)點；對于每個代表飛機的節(jié)點，其流入量總和必須等于通往相應(yīng)停機位的流出量總和，此約束條件由式（23）來表述。式（29）～（30）規(guī)定了分配至同一停機位的飛機之間的停機時間不得重疊，并且飛機機型必須與停機位兼容。式（28）是影響模型復(fù)雜度的關(guān)鍵因素，它使模型具有O（nm）個約束條件，這遠少于基本整數(shù)線性規(guī)劃（ILP）模型的約束條件數(shù)量。

1.3 元啟發(fā)式算法

鑒于大型機場在實際運行中需要迅速做出決策，能夠在極短時間內(nèi)（＜10 s）提供高質(zhì)量解決方案的需求至關(guān)重要。因此，本文將著重介紹兩種元啟發(fā)式算法，旨在快速尋找停機位分配問題的近似最優(yōu)解。

1.3.1 爬山算法

爬山算法是一種在鄰域內(nèi)尋找更優(yōu)解的優(yōu)化算法，直至無法進一步獲得更佳解時才停止，見算法2。

算法2 爬山算法

輸入：停機位分配問題的可行解s

輸出：停機位分配問題的局部最優(yōu)解s

1： s ← GenerateFeasibleSolution

2： WHILE 領(lǐng)域內(nèi)存在更佳解s DO

3：? s ← BestLocalMove（s）

4： END WHILE

5： RETURN s

本文提出將固定鄰域搜索（或稱局部移動）與爬山算法結(jié)合應(yīng)用于解決停機位分配問題。這種方法對于各類成本函數(shù)均具有較高的實用性（并不局限于特定類型的成本函數(shù)），能夠迅速找到局部最優(yōu)解。

在鄰域搜索（local move）中，針對當前的停機位分配方案s，選擇以下兩種優(yōu)化策略中的一種：交換兩架飛機的停機位（稱為交換移動）；或?qū)⒁患茱w機從當前停機位調(diào)整到另一停機位（稱為移位移動）。本文將對每一種可能的移動（包括交換移動和移位移動）進行評估，以確定最優(yōu)的局部移動（best local move）。為了提高求解效率，本文采用記錄上一次迭代評估結(jié)果的方法，僅對因上一次移動而變化的移動進行重新評估。

生成可行分配方案（generate feasible solution）的函數(shù)，本文實施了修復(fù)啟發(fā)式算法。當前飛機無法分配停機位時，該算法將對每架飛機進行強制分配。這一方法參考文獻[15]中介紹的突破性局部搜索（breakout local search）算法。修復(fù)啟發(fā)式算法的具體描述見算法3：

算法3 初始化迭代得到可行解

輸入：所有未分配到停機位的飛機集合s，最大迭代次數(shù)K

輸出：未分配停機位飛機的集合s

1：Q ← ALLFlights（s）

2：flightAfterProblem ← -1 ???-1 表示當前無飛機待分配

3：counter ← 0

4：WHILE Q≠ DO

5：? i ← FirstElementFromList（Q）

6：? Q ← Q＼＼{i}

7：? IF flightAfterProblem=i THEN

8：?? flightAfterProblem ← -1 ???分配結(jié)束

9：?? counter ← 0

10：? END IF

11：? g ← ChooseRandomValidGate（i，s）

12：? IF g ≠ -1 THEN

13：?? s ← Allocate（s，i，g）

14：? ELSE

15：?? counter ← counter + 1

16：?? IF counter < K THEN

17：??? IF flightAfterProblem=-1 THEN

18：???? flightAfterProblem ← FirstElementFromList（Q）

19：??? END IF

20：??? Q，s ← ForceAttribution（Q，s，i）

21：?? ELSE?? 無法找到可行解

22：??? EXIT

23：?? END IF

24：? END IF

25： END WHILE

26： RETURN s

該算法首先將s初始化為所有未分配到停機位的飛機集合，并設(shè)置flightAfterProblem為變量，用于判斷是否還有飛機需要分配。如果當前無飛機待分配，則返回-1；若有，則選擇一個飛機進行停機位分配（如第17行所示）。ChooseRandomValidGate函數(shù)用于在s中隨機選擇一架可分配的飛機i，若無法找到合適的飛機，則返回-1。第12行指代將飛機i分配至s中的停機位g。此外，第16行中的K代表求解的最大迭代次數(shù)，一旦計數(shù)器超過K，啟發(fā)式算法便會停止，并報告未找到可行解。算法第20行定義了強制分配停機位的函數(shù)，即將當前航班i強制分配至一個隨機停機位，同時將與飛機i分配至該停機位相沖突的其他飛機移出，并將這些未分配的飛機重新加入到列表Q的開頭。因此，當飛機列表中的每一架未分配飛機都被重新分配后，算法結(jié)束。

1.3.2 大鄰域搜索

此外，本文還提出了基于整數(shù)線性規(guī)劃的大鄰域搜索（ilp based large neighborhood search，LNS）元啟發(fā)式算法。LNS的原理如算法4所示：

算法4 LNS算法

輸入：停機位分配問題的可行解s

輸出：停機位分配問題優(yōu)化重組后的解s

1： WHILE 不滿足停止迭代條件 DO

2：? s′ ← repair（destroy（s））

3：? IF 分配方案s′相較s更優(yōu) THEN

4：?? s ← s′

5：? END IF

6： END WHILE

7： RETURN s

為了適應(yīng)停機位分配問題的求解需求，本文在LNS算法中定義了Destroy和Repair兩種方法。在Repair方法中，采用了精確算法，具體為第1.2.2節(jié)所介紹的整數(shù)線性規(guī)劃（ILP）多商品流模型。而Destroy方法則通過隨機選擇固定數(shù)量的停機位，并對這些停機位上已分配的飛機進行釋放。因此，Destroy和Repair方法的具體操作為：首先隨機選擇nd個停機位；然后利用ILP多商品流模型對所選停機位的航班進行優(yōu)化重組。其中主循環(huán)的迭代總次數(shù)和每次循環(huán)迭代重組停機位的數(shù)量的選取，對LNS元啟發(fā)式算法的求解效率較為重要。

2 數(shù)值結(jié)果

本研究的數(shù)據(jù)來源于巴黎戴高樂國際機場的真實運行數(shù)據(jù)，該數(shù)據(jù)集已上傳至http：//recherche.enac.fr/～wangrx/gap。該數(shù)據(jù)集包含了巴黎戴高樂機場歷史中最繁忙的30天的運行數(shù)據(jù)。所有結(jié)果均在配置了

120 GB內(nèi)存及兩個Intel（R） Xeon（R） CPU E5-2650 v3 @ 2.30GHz的Ubuntu 18.04.3 LTS系統(tǒng)的工作站上計算得出。

2.1 數(shù)據(jù)分析

本研究的每個實例包含了當天的每個航班及其分配的停機位。表2展示了在所有實例中航站樓及停機位的平均使用情況。其中，占用率定義為航班在停機位上停留時間與總時間的比例。高占用率意味著航站樓的空閑時間最少，即其運營最為繁忙。由于航班在不同航站樓的分布存在不均勻性，因此解決停機位分配問題的復(fù)雜度高度依賴于航站樓的選擇。在這些航站樓中，2F航站樓的占用率最高且航班數(shù)量最多，因此本文將重點研究該航站樓。需要說明一點，為了確保航空公司運營的高效性、地勤服務(wù)的便捷和旅客轉(zhuǎn)機的便利性，巴黎戴高樂機場的停機位分配問題通常不會跨越不同航站樓進行。

2.2 目標函數(shù)比較

在本節(jié)內(nèi)容中，我們專注于確定能夠使指數(shù)函數(shù)和指示函數(shù)達到最佳表現(xiàn)的超參數(shù)，隨后將三種目標函數(shù)應(yīng)用于航班延誤的模擬測試中，并通過計算模擬分數(shù)（simulation score）來進行比較分析。

2.2.1 確定超參數(shù)

首先根據(jù)算法1的結(jié)果確定指數(shù)函數(shù)和指示函數(shù)超參數(shù)的初始值，并進一步優(yōu)化指數(shù)函數(shù)和指示函數(shù)超參數(shù)的選取，將航站樓2F的每個實例分別用最終確定的超參數(shù)和LNS方法進行求解。圖3中的結(jié)果顯示了航站樓2F實例的平均求解時間和模擬分數(shù)。實驗表明，就模擬分數(shù)和求解時間而言，指數(shù)函數(shù)的S=20和指示函數(shù)的S′=50是最合適的超參數(shù)。

2.2.2 目標函數(shù)比較

在本研究中，我們對三種目標函數(shù)進行了比較，主要依據(jù)是模擬分數(shù)和求解時間。

圖4（a）分別顯示了指示函數(shù)與指數(shù)函數(shù)相對于平方函數(shù)的相對模擬分數(shù)，能看出指示函數(shù)在最小化模擬分數(shù)方面的效率較低，經(jīng)計算其模擬分數(shù)的平均值為95.78，是其他函數(shù)的兩倍之多。相比之下，指數(shù)函數(shù)和平方函數(shù)的表現(xiàn)更為接近：在所有航站樓2F的實例中，指數(shù)函數(shù)的平均分數(shù)為54.09，而空閑時間的平方函數(shù)的平均分數(shù)為54.84。圖4（b）為求解時間的結(jié)果，可以看到指示函數(shù)和指數(shù)函數(shù)的求解速度大致相當，而平方函數(shù)的求解速度更快，大約比其他函數(shù)快25%。

綜合分析，指示函數(shù)在三種目標函數(shù)中的表現(xiàn)最為遜色，其模擬分數(shù)與其他兩個函數(shù)相比有明顯差距，而在運行速度方面雖然慢于平方函數(shù)，但與指數(shù)函數(shù)相近。在選擇最佳目標函數(shù)時，雖然平方函數(shù)和指數(shù)函數(shù)的模擬分數(shù)相近，但平方函數(shù)在求解時間上具有明顯的優(yōu)勢。因此，本研究認為平方函數(shù)是優(yōu)化預(yù)期沖突時間的最佳目標函數(shù)選擇。

2.3 方法比較

為了比較不同方法的結(jié)果，本文選擇僅采用平方函數(shù)c（I）=I2 作為目標函數(shù)，旨在在最短的時間內(nèi)最大程度地優(yōu)化停機位分配方案的魯棒性。

2.3.1 精確算法

首先，本文對比了1.2.1節(jié)和1.2.2節(jié)中介紹的基本整數(shù)線性規(guī)劃（ILP）模型和多商品流模型的求解結(jié)果。這兩個模型均通過Gurobi 10.1進行了優(yōu)化求解，同時給出了這兩種模型在處理全部30天航站樓2F實例的最優(yōu)解時的求解時間（詳見OSID科學(xué)數(shù)據(jù)與內(nèi)容）。采用基本ILP模型的平均求解時間為4 414 s，而多商品流模型的平均求解時間僅為121 s。顯然，多商品流模型更為高效，其約束條件數(shù)量的減少顯著加快了求解速度。

2.3.2 元啟發(fā)式算法

在對比兩種元啟發(fā)式算法之前，本文首先著手確定了LNS算法中的最佳參數(shù)。為了實現(xiàn)這一目標，本研究在每個航站樓2F實例上對LNS算法進行了20次運行，并記錄了每次運行的求解結(jié)果。圖5展示了在不同的迭代重組停機位數(shù)（nd值）下，所得結(jié)果與最優(yōu)解之間的平均差距。

設(shè)置迭代重組停機位數(shù)（nd值）為5或7時，可以最終獲得近似最優(yōu)解。當nd= 7時的迭代收斂速度與nd=5相近，但單次迭代所需時間較長。因此，在綜合考慮求解時間與求解質(zhì)量的基礎(chǔ)上，選擇使用nd=5進行100次迭代。

在確定了上述參數(shù)之后，本文比較了爬山算法和LNS算法的結(jié)果。與之前的實驗設(shè)置相同，兩種算法分別在航站樓2F的30天實例上進行了20次測試。圖6展示了所有實例的平均結(jié)果概覽，詳細信息請參見OSID科學(xué)數(shù)據(jù)與內(nèi)容。

研究結(jié)果顯示，這兩種啟發(fā)式方法都能在幾秒鐘內(nèi)找到與最優(yōu)解相差不到1%的結(jié)果。在求解時間方面，這兩種啟發(fā)式算法的表現(xiàn)更為卓越，尋找高質(zhì)量解的速度是多商品流模型的20倍以上（平均找到最優(yōu)解的時間超過了多商品流模型總求解時間的95%）。

2.3.3 模擬分數(shù)對最優(yōu)值差距的敏感度

本節(jié)對使用優(yōu)化分數(shù)（基于空閑時間平方和計算得出）和模擬分數(shù)時，與最優(yōu)解的差異進行了分析。圖7展示了利用LNS算法和爬山算法對所有航站樓2F實例進行超過20次運行后得到的平均值。圖中的虛線表示LNS算法和爬山算法的最優(yōu)得分與航站樓2F實例最優(yōu)得分的對數(shù)比，實線表示爬山算法、LNS算法的模擬分數(shù)與精確解的對數(shù)比。結(jié)果顯示，從優(yōu)化分數(shù)轉(zhuǎn)換到模擬分數(shù)時，與最優(yōu)值的差距有顯著增加：LNS算法的模擬分數(shù)與最優(yōu)值的差距為0.27%，但比精確解的模擬分數(shù)高出6%；爬山算法與最優(yōu)值的差距為1.2%，比精確解的模擬分數(shù)高出36%。

結(jié)果表明，預(yù)期沖突時間只對真正的短空閑時間有意義，而求解質(zhì)量的微小下降會大大增加短空閑時間的數(shù)量。

圖8展示了爬山算法、LNS和多商品流模型這三種算法對2F航站樓的所有實例20次求解后所得到的空閑時間分布的直方圖的對比。三種優(yōu)化結(jié)果中空閑時間主要出現(xiàn)在100～200 min范圍內(nèi)，其中對于小于20 min的空閑時間（機場仿真運行過程中容易出現(xiàn)由于飛機的延誤等原因造成對停機位的占用沖突的空閑時間范圍），尤其是對于短空閑時間（0～4 min），在LNS算法和多商品流模型優(yōu)化結(jié)果中的出現(xiàn)頻次顯著低于在爬山算法結(jié)果中的出現(xiàn)頻次，LNS算法和多商品流模型優(yōu)化效果更佳。

3 結(jié)論

本文的主要目標是為大型機場尋找魯棒性強的停機位分配方案。為此，提出了兩種整數(shù)線性規(guī)劃模型和兩種元啟發(fā)式算法，即大鄰域搜索算法和爬山算法。研究結(jié)果顯示，這兩種元啟發(fā)式算法在求解速度上較精確算法有顯著提升，尤其是大鄰域搜索算法，其求解結(jié)果與最優(yōu)解的平均偏差小于0.3%。同時，本文還對比了三種目標函數(shù)的效果，發(fā)現(xiàn)平方函數(shù)在優(yōu)化停機位分配方案的魯棒性方面表現(xiàn)最佳。對于平方函數(shù)，預(yù)期沖突時間相對于空閑時間平方和的最優(yōu)值非常敏感。這一發(fā)現(xiàn)表明，盡管精確算法的運算時間遠超非精確算法，其在魯棒性方面仍具有一定優(yōu)勢。所提出算法的高效實時響應(yīng)能力，可有效運用在機場日常停機位分配中，并可應(yīng)對增強緊急情況下機場的韌性，保障機場運行的高效性和安全性。未來的研究將致力于將停機位分配、機場跑道調(diào)度以及場面飛行器的滑行路徑優(yōu)化等問題進行深度融合，全面優(yōu)化大型機場場面的整體資源調(diào)度。

參考文獻：

［1］GUPTA U I， LEE D T， LEUNG J Y T. Efficient algorithms for interval graphs and circular-arc graphs[J]. Networks， 1982， 12（4）： 459-467. DOI： 10.1002/net.3230120410.

[2]HUJTER M， TUZA Z. Precoloring extension. IV. general bounds and list colorings[EB/OL]. ［2023-11-01］. http：//arxiv.org/abs/2104.01007.pdf.

[3]BOLAT A. Assigning arriving flights at an airport to the available gates[J]. Journal of the Operational Research Society， 1999， 50（1）： 23-34. DOI： 10.1057/palgrave.jors.2600655.

[4]BOLAT A. Models and a genetic algorithm for static aircraft-gate assignment problem[J]. Journal of the Operational Research Society， 2001， 52（10）： 1107-1120. DOI： 10.1057/palgrave.jors.2601190.

[5]WANG R X， ALLIGNOL C， BARNIER N， et al. Departure management with robust gate allocation[C]//ATM 2019， 13th USA/Europe Air Traffic Management Research and Development Seminar. Vienna，Austra：ATM， 2019： hal-02090426.

[6]WANG R X， ALLIGNOL C， BARNIER N， et al. A new multi-commodity flow model to optimize the robustness of the gate allocation problem[J]. Transportation Research Part C： Emerging Technologies， 2022， 136： 103491. DOI： 10.1016/j.trc.2021.103491.

[7]JAEHN F. Solving the flight gate assignment problem using dynamic programming[J]. Zeitschrift Für Betriebswirtschaft， 2010， 80（10）： 1027-1039. DOI： 10.1007/s11573-010-0396-9.

[8]BI J， WANG F J， DING C， et al. The airport gate assignment problem： a branch-and-price approach for improving utilization of jetways[J]. Computers & Industrial Engineering， 2022， 164： 107878. DOI： 10.1016/j.cie.2021.107878.

[9]JIANG Y， HU Z T， LIU Z Y， et al. Optimization of multi-objective airport gate assignment problem： considering fairness between airlines[J]. Transportmetrica B： Transport Dynamics， 2023， 11（1）： 196-210. DOI： 10.1080/21680566.2022.2056542.

[10]DING H， LIM A， RODRIGUES B， et al. The over-constrained airport gate assignment problem[J]. Computers & Operations Research， 2005， 32（7）： 1867-1880. DOI： 10.1016/j.cor.2003.12.003.

[11]YU C H， ZHANG D， LAU H Y K. An adaptive large neighborhood search heuristic for solving a robust gate assignment problem[J]. Expert Systems with Applications， 2017， 84： 143-154. DOI： 10.1016/j.eswa.2017.04.050.

[12]CASTAING J， MUKHERJEE I， COHN A， et al. Reducing airport gate blockage in passenger aviation[J]. Computers and Operations Research， 2016， 65（C）： 189-199. DOI： 10.1016/j.cor.2014.02.011.

[13]SLVELING G. Stochastic programming methods for scheduling of airport runway operations under uncertainty[M]. Georgia Institute of Technology， 2012.

[14]PREZ-RODRGUEZ J V， PREZ-SNCHEZ J M， GMEZ-DNIZ E. Modelling the asymmetric probabilistic delay of aircraft arrival[J]. Journal of Air Transport Management， 2017， 62： 90-98. DOI： 10.1016/j.jairtraman.2017.03.001.

[15]BENLIC U， BURKE E K， WOODWARD J R. Breakout local search for the multi-objective gate allocation problem[J]. Computers & Operations Research， 2017， 78： 80-93. DOI： 10.1016/j.cor.2016.08.010.