任祎程，韓 印 （上海理工大學 管理學院，上海 200093）

0 引言

機場登機口分配是空中交通管理（ATM）中機場運行的一項關鍵活動和靜態(tài)預計劃策略[1]。作為一個典型的航空公司樞紐，每天通常要處理數(shù)百個國內(nèi)和國際航班，不合理的分配計劃可能導致航班延誤，客戶滿意度低，登機口飛機沖突擁堵和安全隱患，特別是機場容量現(xiàn)狀以接近飽和的樞紐[2]。

登機口的分配通?？紤]兩個主要目標：最小化總航班延誤和最小化登機口使用數(shù)量[3-4]。與登機口相關的約束條件，例如登機口只能容納特定類型的飛機、兩個大型飛機不能同時被分配到兩個登機口，這些條件在登機口分配過程中必須得到滿足[5-6]。當涉及的飛機數(shù)量較少時，登機口可以通過變換不同的目標條件，有效地生成登機口分配計劃。但隨著涉及的飛機數(shù)量的增加，可能的組合數(shù)量顯著增加，很難有效地生成登機口分配方案[7]。

在文獻中，登機口分配問題已被廣泛討論，并提出了相應的方法建議。這些方法可以分為兩組：（1）基于人工計算的方法；（2）基于數(shù)學程序設計的方法。在早期，優(yōu)化理論和計算硬件都非常有限，人工分配在解決登機口重分配問題被更廣泛的應用[8]。C Zhang,D Lau等人（1997）提出了處理登機口分配問題的專家系統(tǒng)[9]。李耐毅提出了一個基于知識的顧問來幫助登機口分配決策[10]。陳鵬超開發(fā)了一種遺傳算法來解決因航班延誤而導致的登機口分配問題[11]。

隨著優(yōu)化理論和計算機技術的發(fā)展，利用數(shù)學規(guī)劃技術優(yōu)化求解登機口分配問題是可行的。因此，近年來提出了幾種基于數(shù)學規(guī)劃的方法[10]。王志清等考慮了機場臨時關閉后的登機口分配問題，考慮分配飛機到一個備選的登機口，但是延誤被忽略了[12]。楊越等人考慮了航班延誤的選擇，并提出了另一種實用算法來解決登機口分配問題[13]。劉君強進一步擴展了前人的模型，提出了一種考慮隨機航班延誤的登機口分配模型[14]。高菁等人提出了一個更實用基于規(guī)則的分配模型，建立了分別處理確定性航班和隨機航班的模型[15]。薛清文等人在他們的登機口分配模型中考慮了中轉乘客[16]。然而，他們的研究有兩個局限性。首先，它只考慮最小化乘客的中轉距離；其次，提出了二次模型，但沒有給出求解該模型的算法。目前單純的航班—登機口的優(yōu)化分配問題已經(jīng)被很好的解決。因此，如何給出合理的學科評價體系或模型來優(yōu)化分配登機口，一直是機場建設研究的熱點問題[17]。

1 問題描述

在建立數(shù)學模型之前，本文首先分析了登機口分配問題的特征：

（1）飛機進港時間和回退時間：飛機進港時間定義為飛機第一次到達登機口的時間，飛機回退時間定義為飛機從登機口后退的時間。圖1中的示例演示了飛機的登機口到達和回退時間；

圖1 飛機到達和起飛時間說明

（2）功能屬性：每個登機口的國內(nèi)/國際、到達/出發(fā)、寬體機/窄體機等功能屬性事先給定，不能改變。

（3）臨時機位：臨時機位定義為位于停車區(qū)的虛擬登機口。

（4）中轉旅客：從到達航班換乘到由同一架或不同架飛機執(zhí)行的出發(fā)航班的旅客。

（5）轉場限定：每架飛機轉場的到達和出發(fā)兩個航班必須分配在同一登機口進行，其間不能挪移別處。

（6）登機口限定：在每個時間點，登機口最多只能被一架飛機占用。

（7）屬性匹配限定：飛機轉場計劃里的航班只能分配到與之屬性相吻合的登機口。

（8）空擋間隔限定：分配在同一登機口的兩飛機之間的空擋間隔必須大于最小空檔時間。

（9）中轉乘客：中轉乘客的一次中轉被定義為一對到達和離開航班。

2 航班—登機口模型建立

2.1 模型參數(shù)

為了便于介紹模型，后文要使用的主要模型參數(shù)符號如表1所示。

2.2 航班—登機口模型

決策變量：

TSi，表示轉場飛機i?？康牡菣C口編號。

目標函數(shù)：

約束條件：

空擋間隔限定：GTAk,j+1-GTSk,j+1≥45min,k=1,…,K-1,j=1,…,J-1

屬性匹配限定：

出發(fā)類型：yki·PSi=yki·GSkoryki·GSk=3,k=1,…,K-1,i=1,…,I

到達類型：yki·PAi=yki·GAkoryki·GAk=3,k=1,…,K-1,i=1,…,I

服務機型：yki·Ei=yki·Bk,k=1,…,K-1,i=1,…,I

轉場限定

由于受實際情況限定：1≤TSi≤K,i=1,…,I

參數(shù)計算：

飛機i與登機口k的分配參數(shù)

登機口k第j個轉機航班的到達時間：

表1 符號和參數(shù)

登機口k第j個轉機航班的出發(fā)時間：GTSkj=custom［yik,TSi］,k=1,…,K-1

此處，custom［］為自定義運算符，表示去除數(shù)組中的0值，其他值順序不變。

2.3 模型求解

從參考文獻中可以看出，路徑分配問題通常采用精確算法[18]和啟發(fā)式算法[19]來尋找最優(yōu)的解決方案。由于之前的大部分研究使用元啟發(fā)式方法解決航班—登機口分配問題[20-21]。我們使用NSGA-II遺傳算法來解決這個問題，并將空檔時間約束添加到登機口的分配問題。

2.3.1 算法分析

為改善遺傳算法在局部搜索能力方面的不足，提出將分支定界法與遺傳算法相結合，構造了一種內(nèi)嵌分支定界尋優(yōu)搜索的遺傳算法，在保證算法全局搜索能力的前提下提升局部精確搜索能力。對于遺傳算法，為了適應算法結構提出了一種基于任務絕對順序的編碼策略：

步驟1：所有的飛機都是按照初始登機口到達時間升序排列的。

步驟2：求解航班—登機口模型的約束。最優(yōu)解為每一個個體適應度函數(shù)的分數(shù)值。

步驟3：每架飛機都固定在一個登機口群上。

步驟4：在每次迭代中，會有數(shù)量有限的飛機固定在臨時機位上。

步驟5：在前面步驟中違反臨時機位的飛機數(shù)量的飛機—登機口組合被刪除。

2.3.2 NSGA-II遺傳算法

A.染色體編碼和初始化

使用一個整數(shù)字符串來表示染色體是飛機與登機口的分配關系。

B.適應度函數(shù)

將目標表函數(shù)設置為適應度函數(shù)，并以此來評價群體中個體好壞。其中，目標最小化臨時機位飛機數(shù)與最小化登機口使用數(shù)的適應度權重比，取500∶1。

C.遺傳操作

（a）選擇：采用游戲算法選擇算子，使適應度好的染色體有更高的機會被選中。

（b）交叉：交叉是作用于兩條染色體上，在一段時間內(nèi)通過將兩者結合起來產(chǎn)生后代染色體的功能。多數(shù)采用單點法交叉。

（c）突變：隨機選擇兩個基因從染色體上，它們的值被交換并獲得一個等級較弱的染色體。

3 算例分析

3.1 算例數(shù)據(jù)

由于旅行業(yè)的快速發(fā)展，航空公司機場現(xiàn)有的航站樓T的旅客流量已達飽和狀態(tài)，為了應對未來的發(fā)展，現(xiàn)正增設衛(wèi)星廳S。該機場航站樓T有28個登機口，衛(wèi)星廳S有41個登機口。T和S之間有捷運線相通，假定旅客無需等待，隨時可以發(fā)車，捷運單程一次需要8分鐘。分配在同一登機口的兩飛機之間的空擋間隔必須大于等于45分鐘。待分配的飛機數(shù)為262架。

3.2 結果分析

通過優(yōu)化處理計算得到最多可安排的航班數(shù)為222架，其中寬體機有42架，窄體機有180架，成功分配到登機口的寬體機和窄體機的航班數(shù)量對比如圖2所示。

觀察圖3的餅狀圖發(fā)現(xiàn)1-1（國內(nèi)到達—國內(nèi)出發(fā)）的機型不再全部為窄體機，有一小部分為寬體機。

圖2 成功分配航班數(shù)量（寬體機和窄體機）

圖3 成功分配航班比例

航站樓（T）和衛(wèi)星廳（S）登機口的最少使用數(shù)目，結果如圖4所示，發(fā)現(xiàn)至少使用64個登機口才可以最多的安排航班222架。

圖5給出了航站樓（T）和衛(wèi)星廳（S）的被使用登機口的平均使用率（定義“平均使用率”為登機口的占用時間比率），發(fā)現(xiàn)大多數(shù)的登機口的平均使用率都遠遠大于50%，其中使用率在70%～100%間的登機口占大多數(shù)，即登機口的使用率符合實際情況。

表2為航班—登機口分配結果匯總和有關屬性的標注。成功分配飛機數(shù)為222架，停在臨時機場的飛機有40架，使用的登機口數(shù)量為64個。

圖4 T和S登機口使用數(shù)目

圖5 T和S登機口的平均使用率

表2 航班—登機口分配結果匯總表

如圖6所示，換乘時間在30～35分鐘以內(nèi)的中轉旅客比率最大為27%，在5分鐘以內(nèi)的中轉旅客最少為0。

如圖7所示，緊張度在0.1～0.2的中轉旅客比率最小為0，緊張度在0.6～0.7的中轉旅客比率最大為28%。

圖6 中轉旅客在各個時間段的比率

圖7 中轉旅客在各個時間段的比率

4 結束語

本文針對機場航班登機口分配問題，根據(jù)轉場限定、登機口限定、屬性匹配限定、空擋間隔限定，建立飛機—登機口分配的一個二次0～1整數(shù)規(guī)劃模型。采用改進的NSGA-II遺傳算法，并利用MATLAB對模型進行了求解。通過對一個算例分析，驗證了本文方法的可行性和有效性，為管理者更好地進行航班登機口的分配提供了指導意見。