基于魯棒性模擬的停機(jī)位分配問(wèn)題的數(shù)值方法比較

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

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

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

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

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

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

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

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

本研究首先對(duì)所研究的問(wèn)題進(jìn)行數(shù)學(xué)建模，隨后通過(guò)仿真方法對(duì)沖突時(shí)間的期望值進(jìn)行分析。文章中所采用的符號(hào)注釋詳見(jià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ù)。對(duì)于優(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]］，則問(wèn)題可以表述為：

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

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

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

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

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

Bolat等 [3]和 YU等[11]，分別給出了不同的目標(biāo)函數(shù)，來(lái)提升停機(jī)位分配的魯棒性，如最小化空閑時(shí)間的平方和等。對(duì)于停機(jī)位分配問(wèn)題來(lái)說(shuō)，最小化平方和函數(shù)實(shí)際上等同于最小化空閑時(shí)間的方差，詳見(jiàn)方程 （4） 。實(shí)際上，所有停機(jī)位占用的空閑時(shí)間總和與停機(jī)位分配方案本身是無(wú)關(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í)間長(zhǎng)度一致，則無(wú)法進(jìn)一步降低短空閑時(shí)間的出現(xiàn)頻率，這在航班延誤的情況下更容易引發(fā)沖突。因此，通過(guò)最小化所有空閑時(shí)間的方差，可以有效減少短暫和過(guò)長(zhǎng)空閑時(shí)間的數(shù)量。

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

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

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

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

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

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

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

1.2 線性規(guī)劃模型

對(duì)該問(wèn)題的求解可以用線性規(guī)劃來(lái)模擬，本節(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í)間較長(zhǎng)。鑒于此，本文將介紹一種約束條件數(shù)量較少的模型。

1.2.2 多商品流模型

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

V=VF∪VsG∪VeG，（16）

E=EF∪EsG∪EeG。（17）

本文將停機(jī)位的開(kāi)啟節(jié)點(diǎn)視為源節(jié)點(diǎn)，將停機(jī)位的關(guān)閉節(jié)點(diǎn)視為匯節(jié)點(diǎn)，式（16）中VF代表飛機(jī)節(jié)點(diǎn)，VsG代表停機(jī)位開(kāi)啟節(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ī)位開(kāi)啟與第一個(gè)飛機(jī)之間的邊的集合，EeG代表停機(jī)位最后一個(gè)飛機(jī)與停機(jī)位關(guān)閉節(jié)點(diǎn)之間的邊的集合，每個(gè)邊集的容量為{0，1}。

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

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

該模型的線性規(guī)劃模型表示如下，此模型使用與基本ILP模型相同的二元決策變量xi，j，k，式（24）所定義的目標(biāo)函數(shù)保持不變。式（25）～（28）分別規(guī)定了每個(gè)源節(jié)點(diǎn)的流出量之和為1，這表示每個(gè)非空置的停機(jī)位都有第一個(gè)虛擬飛機(jī)；對(duì)于每個(gè)匯節(jié)點(diǎn)，流入量總和為1，確保每個(gè)非空置的停機(jī)位都有最后一個(gè)虛擬飛機(jī)；所有代表飛機(jī)的節(jié)點(diǎn)的流出量總和為1，表示該飛機(jī)之后只有一個(gè)飛機(jī)與之相連，或者該飛機(jī)指向一個(gè)匯節(jié)點(diǎn)；對(duì)于每個(gè)代表飛機(jī)的節(jié)點(diǎn)，其流入量總和必須等于通往相應(yīng)停機(jī)位的流出量總和，此約束條件由式（23）來(lái)表述。式（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ī)場(chǎng)在實(shí)際運(yùn)行中需要迅速做出決策，能夠在極短時(shí)間內(nèi)（＜10 s）提供高質(zhì)量解決方案的需求至關(guān)重要。因此，本文將著重介紹兩種元啟發(fā)式算法，旨在快速尋找停機(jī)位分配問(wèn)題的近似最優(yōu)解。

1.3.1 爬山算法

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

算法2 爬山算法

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

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

1： s ← GenerateFeasibleSolution

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

3：? s ← BestLocalMove（s）

4： END WHILE

5： RETURN s

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

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

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

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

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

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

1：Q ← ALLFlights（s）

2：flightAfterProblem ← -1 ???-1 表示當(dāng)前無(wú)飛機(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?? 無(wú)法找到可行解

22：??? EXIT

23：?? END IF

24：? END IF

25： END WHILE

26： RETURN s

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

1.3.2 大鄰域搜索

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

算法4 LNS算法

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

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

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

本研究的數(shù)據(jù)來(lái)源于巴黎戴高樂(lè)國(guó)際機(jī)場(chǎng)的真實(shí)運(yùn)行數(shù)據(jù)，該數(shù)據(jù)集已上傳至http：//recherche.enac.fr/～wangrx/gap。該數(shù)據(jù)集包含了巴黎戴高樂(lè)機(jī)場(chǎng)歷史中最繁忙的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)營(yíng)最為繁忙。由于航班在不同航站樓的分布存在不均勻性，因此解決停機(jī)位分配問(wèn)題的復(fù)雜度高度依賴于航站樓的選擇。在這些航站樓中，2F航站樓的占用率最高且航班數(shù)量最多，因此本文將重點(diǎn)研究該航站樓。需要說(shuō)明一點(diǎn)，為了確保航空公司運(yùn)營(yíng)的高效性、地勤服務(wù)的便捷和旅客轉(zhuǎn)機(jī)的便利性，巴黎戴高樂(lè)機(jī)場(chǎng)的停機(jī)位分配問(wèn)題通常不會(huì)跨越不同航站樓進(jìn)行。

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

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

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

圖4（a）分別顯示了指示函數(shù)與指數(shù)函數(shù)相對(duì)于平方函數(shù)的相對(duì)模擬分?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)勢(shì)。因此，本研究認(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 精確算法

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

2.3.2 元啟發(fā)式算法

在對(duì)比兩種元啟發(fā)式算法之前，本文首先著手確定了LNS算法中的最佳參數(shù)。為了實(shí)現(xiàn)這一目標(biāo)，本研究在每個(gè)航站樓2F實(shí)例上對(duì)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í)間較長(zhǎng)。因此，在綜合考慮求解時(shí)間與求解質(zhì)量的基礎(chǔ)上，選擇使用nd=5進(jìn)行100次迭代。

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

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

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

本節(jié)對(duì)使用優(yōu)化分?jǐn)?shù)（基于空閑時(shí)間平方和計(jì)算得出）和模擬分?jǐn)?shù)時(shí)，與最優(yōu)解的差異進(jìn)行了分析。圖7展示了利用LNS算法和爬山算法對(duì)所有航站樓2F實(shí)例進(jìn)行超過(guò)20次運(yùn)行后得到的平均值。圖中的虛線表示LNS算法和爬山算法的最優(yōu)得分與航站樓2F實(shí)例最優(yōu)得分的對(duì)數(shù)比，實(shí)線表示爬山算法、LNS算法的模擬分?jǐn)?shù)與精確解的對(duì)數(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í)間只對(duì)真正的短空閑時(shí)間有意義，而求解質(zhì)量的微小下降會(huì)大大增加短空閑時(shí)間的數(shù)量。

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

3 結(jié)論

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