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

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

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

中圖分類號：U-9；V2?? 文獻(xiàn)標(biāo)志碼：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ùn)輸業(yè)的蓬勃發(fā)展，高效合理地將有限的停機(jī)位分配給日益增加的航班成為大型機(jī)場資源調(diào)度的核心問題。考慮到天氣變化及其他多種因素，航班延誤成為常見現(xiàn)象。特別是，前序航班的延誤可能導(dǎo)致后續(xù)分配至同一停機(jī)位的航班產(chǎn)生沖突，從而影響機(jī)場整體運(yùn)營的平穩(wěn)性?；诖?，本研究專注于大型機(jī)場停機(jī)位分配方案的魯棒性，旨在最小化航班延誤對于停機(jī)位資源調(diào)度的負(fù)面影響。

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

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

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

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

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

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

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

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

1.1 目標(biāo)函數(shù)

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

1.1.1 預(yù)期沖突時(shí)間的估計(jì)

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

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

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

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

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

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

算法1 模擬沖突時(shí)間

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

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

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

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

（1）平方函數(shù)

R+→R+，II2。（5）

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

（3）指示函數(shù)

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

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

1.2 線性規(guī)劃模型

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

1.2.1 基本ILP模型

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

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

1.2.2 多商品流模型

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

V=VF∪VsG∪VeG，（16）

E=EF∪EsG∪EeG。（17）

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

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

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

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

1.3 元啟發(fā)式算法

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

1.3.1 爬山算法

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

算法2 爬山算法

輸入：停機(jī)位分配問題的可行解s

輸出：停機(jī)位分配問題的局部最優(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)用于解決停機(jī)位分配問題。這種方法對于各類成本函數(shù)均具有較高的實(shí)用性（并不局限于特定類型的成本函數(shù)），能夠迅速找到局部最優(yōu)解。

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

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

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

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

輸出：未分配停機(jī)位飛機(jī)的集合s

1：Q ← ALLFlights（s）

2：flightAfterProblem ← -1 ???-1 表示當(dāng)前無飛機(jī)待分配

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

1.3.2 大鄰域搜索

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

算法4 LNS算法

輸入：停機(jī)位分配問題的可行解s

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

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

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

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

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

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

2.2 目標(biāo)函數(shù)比較

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

2.2.1 確定超參數(shù)

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

2.2.2 目標(biāo)函數(shù)比較

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

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

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

2.3 方法比較

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

2.3.1 精確算法

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

2.3.2 元啟發(fā)式算法

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

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

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

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

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

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

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

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

3 結(jié)論

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

參考文獻(xiàn)：

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