基于魯棒性模擬的停機位分配問題的數值方法比較

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

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

關鍵詞：停機位分配；固定作業問題；機場；組合優化；大鄰域搜索；線性規劃

中圖分類號：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

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

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

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

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

1 數學模型

本研究首先對所研究的問題進行數學建模，隨后通過仿真方法對沖突時間的期望值進行分析。文章中所采用的符號注釋詳見表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]］表示區間內取整數。對于優化目標，本文聚焦最大限度提高飛機之間的空閑時間，以確保停機位分配方案的魯棒性。因此引入空閑時間的成本函數c。每次航班起飛前有一段空閑時間，同時每個停機位關閉前有額外的空閑時間，因此共有n+m個空閑時間。引入空閑時間變量Il，l∈［［1，n+m］[KG-2.8mm]］，則問題可以表述為：

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

1.1 目標函數

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

1.1.1 預期沖突時間的估計

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

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

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

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

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

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

算法1 模擬沖突時間

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

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

1.1.2 目標函數的選取

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

（1）平方函數

R+→R+，II2。（5）

（2）指數函數

（3）指示函數

其中，S和S′是超參數。

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

1.2 線性規劃模型

對該問題的求解可以用線性規劃來模擬，本節提出了兩種不同的數學模型。

1.2.1 基本ILP模型

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

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

1.2.2 多商品流模型

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

V=VF∪VsG∪VeG，（16）

E=EF∪EsG∪EeG。（17）

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

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

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

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

1.3 元啟發式算法

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

1.3.1 爬山算法

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

算法2 爬山算法

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

輸出：停機位分配問題的局部最優解s

1： s ← GenerateFeasibleSolution

2： WHILE 領域內存在更佳解s DO

3：? s ← BestLocalMove（s）

4： END WHILE

5： RETURN s

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

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

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

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

輸入：所有未分配到停機位的飛機集合s，最大迭代次數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 ???分配結束

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

1.3.2 大鄰域搜索

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

算法4 LNS算法

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

輸出：停機位分配問題優化重組后的解s

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

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

3：? IF 分配方案s′相較s更優 THEN

4：?? s ← s′

5：? END IF

6： END WHILE

7： RETURN s

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

2 數值結果

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

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

2.1 數據分析

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

2.2 目標函數比較

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

2.2.1 確定超參數

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

2.2.2 目標函數比較

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

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

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

2.3 方法比較

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

2.3.1 精確算法

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

2.3.2 元啟發式算法

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

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

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

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

2.3.3 模擬分數對最優值差距的敏感度

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

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

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

3 結論

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

參考文獻：

［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.