劉興芬，王利平，李 強，鄧 衛(wèi)

(湖南大學(xué) a. 數(shù)學(xué)與計量經(jīng)濟學(xué)院， b. 化學(xué)化工學(xué)院， c. 機械與運載工程學(xué)院，中國 長沙 410081)

近年來，隨著社會經(jīng)濟的快速發(fā)展，國民收入水平不斷提高，旅游業(yè)已逐漸成為我國重要產(chǎn)業(yè)。旅客數(shù)量的迅速增長，使現(xiàn)有的民航資源正面臨著日益嚴峻的考驗。很多航空公司在機場的現(xiàn)有航站樓運載量已遠不能滿足旅客高效出行和航班轉(zhuǎn)場需求。為了緩解客流量快速增長和飛機轉(zhuǎn)場時登機口不足的壓力，新擴增衛(wèi)星廳是主要方法。從資源節(jié)約角度考慮，一般航站樓具有完整的國際機場航站功能，衛(wèi)星廳只作為航站樓的延伸，可以候機，卻沒有出入境手續(xù)辦理功能。隨之也將對中轉(zhuǎn)旅客的航班銜接帶來負面影響。新增的衛(wèi)星廳造成機場管理的復(fù)雜性明顯增加，部分中轉(zhuǎn)旅客的航班銜接時間被擴大，導(dǎo)致旅客中轉(zhuǎn)失敗的可能性增加。如果管理不當(dāng)，可能會發(fā)生航班無法降落，導(dǎo)致飛機延誤，產(chǎn)生多米諾骨牌效應(yīng)等。因此，優(yōu)化分配登機口，減少中轉(zhuǎn)旅客的換乘時間，進一步提高機場的服務(wù)質(zhì)量具有重要的現(xiàn)實意義。

目前，國外很多學(xué)者對登機口分配問題進行了較深入的研究，其中解決的方法主要包括關(guān)鍵路徑法、分支定界法、整數(shù)規(guī)劃法、系統(tǒng)仿真、專家系統(tǒng)、啟發(fā)式算法、網(wǎng)絡(luò)流及多目標規(guī)劃等。最近幾年更傾向于用啟發(fā)式算法進行求解。2018年楊順秀[1]建立了面向航班延誤情景的登機口調(diào)度多目標模型，并設(shè)計了擴展的人工雨滴算法進行求解。2015年，陳驍睿[2]統(tǒng)籌了機場運行效率和乘客服務(wù)質(zhì)量，詳盡地研究了登機口調(diào)度問題的關(guān)鍵因素及約束條件。Yu和Lau[3]以最小化中轉(zhuǎn)乘客步行距離和最小化錯過并后續(xù)轉(zhuǎn)乘其他航班的乘客數(shù)量為目標，建立了側(cè)重于中轉(zhuǎn)旅客滿意度的登機口再分配模型，并提供了一種啟發(fā)式方法求解該模型。Marinelli等[4]研究了基于蜂群優(yōu)化(BCO)的元啟發(fā)式方法來求解登機口分配問題；2016年Dorndorf和Jaehn等[5]采用圖論中團劃分方法建立了登機口分配沖突最小化模型，并提出回收規(guī)劃程序進行求解。2017和2019年Stollenwerk等[6,7]采用D-Wave量子退火方法研究模型的可解性，在有一定限制的量子退火條件下使得登機口分配問題得到解決。2017年，Schaijk等[8]提出了一種將確定性登機口約束替換為隨機登機口約束的新方法來提高登機口分配模型(Fgap)解的魯棒性。Dell等[9]研究了基于模糊蜂群優(yōu)化(FBCO)的元啟發(fā)式方法來求解登機口分配問題。Zhang等[10]針對惡劣天氣、航班延誤和航班取消等情況，對純登機口再分配問題和帶連接乘客的登機口再分配問題建立了兩種多商品網(wǎng)絡(luò)流模型，并分別提出潛水啟發(fā)式算法和滾動層算法進行求解。2018年P(guān)ternea等[11]提出了帶有乘客航班連接的登機口改進多維度重新分配模型，并嵌入到基于數(shù)學(xué)規(guī)劃的啟發(fā)式算法中進行求解。Pineda等[12]研究了一種結(jié)合DEMATEL，DANP和VIKOR方法的混合模型，幫助航空公司管理人員在機隊調(diào)度干擾中對最合適的飛機類型進行排序和識別。

單純的航班—登機口的優(yōu)化分配問題已被很好地解決[13]，但在優(yōu)化分配登機口的同時考慮航站樓的類型并最小化旅客換乘時間，目前鮮有研究。假設(shè)航站樓和衛(wèi)星廳分別有m1和m2個登機口，其中登機口又分為窄體機和寬體機、國內(nèi)和國際、到達和出發(fā)等幾種基本屬性及類型，每個登機口的功能屬性事先給定，不能改變，航班只能分配到與之屬性相吻合的登機口，且每架飛機轉(zhuǎn)場的到達和出發(fā)兩個航班必須分配在同一登機口進行，其間不能挪移別處。本文主要考慮新增衛(wèi)星廳的前提下，加入中轉(zhuǎn)旅客換乘時間及其緊張度等因素對航班—登機口分配問題作進一步研究與優(yōu)化。

1 模型與方法

考慮一般航班—登機口分配，盡可能多地分配航班到合適的登機口并且在此基礎(chǔ)上最小化被使用登機口的數(shù)量：

且s(n)≤n，其中：

定義：

則有

每架飛機只能被被分配到一個登機口，即

對于被分配到同一個登機口的兩個相鄰航班應(yīng)該滿足后一個航班的到達時間與前一航班的出發(fā)時間相隔至少是45 min，即

并使得旅客的總體最短換乘時間盡量小

其中pk為需要從航班i中轉(zhuǎn)到航班j的人數(shù)。

假設(shè)某旅客中轉(zhuǎn)成功，則其最短流程時間tijkl，否則懲罰其最短流時間tijkl=360 min。加上換乘旅客自身因素，需要考慮換乘旅客總體緊張度盡量最小化，

則完整目標及約束可概括為以下線性多目標規(guī)劃模型

2 求解算法

2.1 航班—登機口分配規(guī)則

圖1 航班到達時間和出發(fā)時間分布圖Fig. 1 The distribution of flight arrival time and departure time

圖2 有向賦權(quán)圖Fig. 2 Directed weighting graph

其算法流程如下。

Step 3：重復(fù)step2直到找不到滿足條件的航班，則j=j+1，若j≤m，轉(zhuǎn)到2；否則，停止。

2.2 多目標處理

通過選取不同登機口的初始位置作為初值，利用以上算法可得到在目標函數(shù)(1)下基于不同初始位置的若干可行解，還應(yīng)使得旅客總體換乘時間緊張度以及被使用登機口的數(shù)量最小化。取可接受目標(1)，引入層次分析法進行綜合評價，選取最優(yōu)初始值及最優(yōu)方案。其一般步驟如下：

① 構(gòu)造兩兩比較的判斷矩陣；

本文基于目標(1)下旅客總體緊張度(N)、換乘時間(T)、被使用登機口的數(shù)量(Y)遞減的重要性構(gòu)造判斷矩陣如下表1下：

表1 判斷矩陣

② 由判斷矩陣計算各指標對于該準則的相對權(quán)重，并進行判斷矩陣的一致性檢驗；

③ 計算各層次對于系統(tǒng)的總排序權(quán)重。

一致性檢驗的步驟如下。

(1)計算一致性指標CI：

(2)查找相應(yīng)的平均隨機一致性指標RI，計算一致性比例CR：

當(dāng)CR<0.1時，認為判斷矩陣的一致性是可以接受的，否則應(yīng)對判斷矩陣作適當(dāng)修正。

其一致性比例為0.007 9，最大特征值為3.009 2，因此該判斷矩陣通過了一致性檢驗，且所計算的相對權(quán)重理論上正確。由此可得到旅客總體緊張度(N)、換乘時間(T)、被使用登機口的數(shù)量(Y)綜合權(quán)重(w1,w2,w3)=(0.539 6，0.297 0，0.163 4)：

min(w1N+w2T+w3Y)。

從而確定最優(yōu)登機口分配方案。

3 實證分析

3.1 數(shù)據(jù)選取

本文實例選取2018年“華為杯”研究生數(shù)學(xué)建模競賽F題，取材于中國東方航空公司和上海浦東國際機場，飛機轉(zhuǎn)場計劃和中轉(zhuǎn)旅客信息包含2018年1月19，20和21三天的數(shù)據(jù)。為了簡化問題，本文只對20日到達或20日出發(fā)的航班和旅客進行分析，得到303條有效的飛機轉(zhuǎn)場記錄和1 677條中轉(zhuǎn)旅客記錄，其中包含了597架次航班，包括國內(nèi)/國際、到達/出發(fā)、寬體機/窄體機等功能屬性及69個登機口的各屬性，其中航站樓和衛(wèi)星廳分別有m1=21,m2=48個登機口。

本題數(shù)據(jù)中使用到的寬窄飛機型號分別有：

寬體機(Wide-body)：332， 333， 33E， 33H， 33L， 773；

窄體機(Narrow-body)：319， 320， 321， 323， 325， 738， 73A， 73E， 73H， 73L。

3.2 結(jié)果分析

采用上述算法，取λ=μ=1，得到最優(yōu)分配方案有252架次飛機被成功分配到固定登機口，成功率為83%，還剩3個寬類型的登機口未使用。針對1 677條中轉(zhuǎn)旅客總體緊張度為421.56，總體換乘時間為78 195 min，約1 296.9 h，登機口的總體使用率為60.3%，其各登機口使用率如下表 2所示。

表2 登機口使用率

進一步分析可知：

(1)如表 3所示，寬體飛機和窄體飛機成功分配到固定登機口的成功率有顯著差異，通過對窄體機和寬體機登機口對比，發(fā)現(xiàn)窄體機登機口和相匹配的航班數(shù)比為11∶1。根據(jù)表3，寬體機僅為2.17∶1。由此可見窄體機飛機架次相對較多，可供分配的登機口資源匱乏導(dǎo)致成功分配到固定登機口的成功率較低，應(yīng)該適當(dāng)增加窄體機登機口。

表3 航班匹配情況

(2)如圖3所示，最大換乘時間為81 min，最小為25 min，相應(yīng)旅客兩次乘坐航班都是國內(nèi)，且不需要乘坐捷運辦理手續(xù)，換乘時間由15 min最小流程時間加10分鐘最小行走時間構(gòu)成。旅客換乘時間大部分集中在30～40 min，50～60 min，65～75 min。進一步分析發(fā)現(xiàn)，換乘65～75 min比例較多，這類旅客的情況是乘坐國際航班降落衛(wèi)星廳S并換乘在S起飛的國際航班，中間需要乘坐兩次捷運，表明衛(wèi)星廳S對國際航班旅客的影響更大，進一步驗證了算法的合理性。

(3)最大緊張度為0.859，如圖4可直觀地看出旅客緊張度總體偏小，從表4可看出95%的旅客緊張度都可以控制在0.6以內(nèi)，也從側(cè)面反映了模型和算法的可靠性。

圖3 旅客換乘時間比例分布Fig. 3 Proportional distribution of passenger transfer time

圖4 旅客緊張度比例分布Fig. 4 Proportional distribution of passenger tension

表4 旅客緊張度比例分布

4 結(jié)論

本文基于多目標規(guī)劃構(gòu)建了航班登機口分配優(yōu)化模型，通過將問題抽象化，賦予不同的航班到達時間權(quán)重λ與停留間隔時間權(quán)重μ為基準，模擬結(jié)果表明基于Dijkstra算法思想改進的啟發(fā)式貪心算法具有較高穩(wěn)定性，再結(jié)合層次分析法對其余目標進行綜合評價，通過一致性檢驗，使航站樓與新增衛(wèi)星廳的登機口分配問題得到有效解決。通過算例驗證了利用該模型和算法得到的結(jié)果與實際情況相符合，直接證明了其可靠性。