考慮中轉(zhuǎn)旅客的登機(jī)口分配問(wèn)題

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

0 引言

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

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

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

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

1 問(wèn)題描述

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

（1）飛機(jī)進(jìn)港時(shí)間和回退時(shí)間：飛機(jī)進(jìn)港時(shí)間定義為飛機(jī)第一次到達(dá)登機(jī)口的時(shí)間，飛機(jī)回退時(shí)間定義為飛機(jī)從登機(jī)口后退的時(shí)間。圖1中的示例演示了飛機(jī)的登機(jī)口到達(dá)和回退時(shí)間；

圖1 飛機(jī)到達(dá)和起飛時(shí)間說(shuō)明

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

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

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

（5）轉(zhuǎn)場(chǎng)限定：每架飛機(jī)轉(zhuǎn)場(chǎng)的到達(dá)和出發(fā)兩個(gè)航班必須分配在同一登機(jī)口進(jìn)行，其間不能挪移別處。

（6）登機(jī)口限定：在每個(gè)時(shí)間點(diǎn)，登機(jī)口最多只能被一架飛機(jī)占用。

（7）屬性匹配限定：飛機(jī)轉(zhuǎn)場(chǎng)計(jì)劃里的航班只能分配到與之屬性相吻合的登機(jī)口。

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

（9）中轉(zhuǎn)乘客：中轉(zhuǎn)乘客的一次中轉(zhuǎn)被定義為一對(duì)到達(dá)和離開(kāi)航班。

2 航班—登機(jī)口模型建立

2.1 模型參數(shù)

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

2.2 航班—登機(jī)口模型

決策變量：

TSi，表示轉(zhuǎn)場(chǎng)飛機(jī)i?？康牡菣C(jī)口編號(hào)。

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

約束條件：

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

屬性匹配限定：

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

到達(dá)類(lèi)型：yki·PAi=yki·GAkoryki·GAk=3,k=1,…,K-1,i=1,…,I

服務(wù)機(jī)型：yki·Ei=yki·Bk,k=1,…,K-1,i=1,…,I

轉(zhuǎn)場(chǎng)限定

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

參數(shù)計(jì)算：

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

登機(jī)口k第j個(gè)轉(zhuǎn)機(jī)航班的到達(dá)時(shí)間：

表1 符號(hào)和參數(shù)

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

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

2.3 模型求解

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

2.3.1 算法分析

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

步驟1：所有的飛機(jī)都是按照初始登機(jī)口到達(dá)時(shí)間升序排列的。

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

步驟3：每架飛機(jī)都固定在一個(gè)登機(jī)口群上。

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

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

2.3.2 NSGA-II遺傳算法

A.染色體編碼和初始化

使用一個(gè)整數(shù)字符串來(lái)表示染色體是飛機(jī)與登機(jī)口的分配關(guān)系。

B.適應(yīng)度函數(shù)

將目標(biāo)表函數(shù)設(shè)置為適應(yīng)度函數(shù)，并以此來(lái)評(píng)價(jià)群體中個(gè)體好壞。其中，目標(biāo)最小化臨時(shí)機(jī)位飛機(jī)數(shù)與最小化登機(jī)口使用數(shù)的適應(yīng)度權(quán)重比，取500∶1。

C.遺傳操作

（a）選擇：采用游戲算法選擇算子，使適應(yīng)度好的染色體有更高的機(jī)會(huì)被選中。

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

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

3 算例分析

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

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

3.2 結(jié)果分析

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

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

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

圖3 成功分配航班比例

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

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

表2為航班—登機(jī)口分配結(jié)果匯總和有關(guān)屬性的標(biāo)注。成功分配飛機(jī)數(shù)為222架，停在臨時(shí)機(jī)場(chǎng)的飛機(jī)有40架，使用的登機(jī)口數(shù)量為64個(gè)。

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

圖5 T和S登機(jī)口的平均使用率

表2 航班—登機(jī)口分配結(jié)果匯總表

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

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

圖6 中轉(zhuǎn)旅客在各個(gè)時(shí)間段的比率

圖7 中轉(zhuǎn)旅客在各個(gè)時(shí)間段的比率

4 結(jié)束語(yǔ)

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