考慮中轉旅客的登機口分配問題

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

0 引言

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

2 航班—登機口模型建立

2.1 模型參數

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

2.2 航班—登機口模型

決策變量：

TSi，表示轉場飛機i停靠的登機口編號。

目標函數：

約束條件：

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

屬性匹配限定：

出發類型：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

參數計算：

飛機i與登機口k的分配參數

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

表1 符號和參數

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

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

2.3 模型求解

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

2.3.1 算法分析

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

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

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

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

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

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

2.3.2 NSGA-II遺傳算法

A.染色體編碼和初始化

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

B.適應度函數

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

C.遺傳操作

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

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

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

3 算例分析

3.1 算例數據

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

3.2 結果分析

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

觀察圖3的餅狀圖發現1-1（國內到達—國內出發）的機型不再全部為窄體機，有一小部分為寬體機。

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

圖3 成功分配航班比例

航站樓（T）和衛星廳（S）登機口的最少使用數目，結果如圖4所示，發現至少使用64個登機口才可以最多的安排航班222架。

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

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

圖4 T和S登機口使用數目

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

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

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

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

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

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

4 結束語

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