考慮換乘緊張度的登機口分配優(yōu)化建模

薛清文，郎 洪，王勇智，陸 鍵

（同濟大學(xué)a.道路與交通工程教育部重點實驗室；b.數(shù)學(xué)科學(xué)學(xué)院，上海 201804）

近年來，急劇增長的客、貨運輸量對民航運輸需求不斷增加。部分機場現(xiàn)有的航站樓旅客流量已達到飽和狀態(tài)，機場通過增建新的航站樓緩解原有航站樓登機口不足的問題。但對于部分中轉(zhuǎn)旅客而言，會增加其在轉(zhuǎn)場過程中的換乘時間，大大降低旅客對于航空公司和機場的服務(wù)滿意度。如何在實現(xiàn)登機口資源利用最大化的同時，提高中轉(zhuǎn)旅客效率已成為改善樞紐機場中轉(zhuǎn)運行效率的關(guān)鍵性問題。

針對登機口分配問題，國內(nèi)外部分研究學(xué)者分別進行如下研究：以登機口空閑時間最小[1]、分配到同一登機口的前后航班沖突概率最小[2]等為目標建立單目標多約束的登機口指派模型進行研究；從場面運行效率的角度出發(fā)，建立以航班延誤最小[3]、飛機滑行距離最小[4]，航班分配效率最高[5]等優(yōu)化模型；從旅客角度出發(fā)，以旅客步行距離最小[6]為目標進行優(yōu)化。部分研究中，旅客步行距離分別與遠機位使用數(shù)量[7-8]、航班分配效率[9]、登機口魯棒性[10]及登機口空閑時間[11]等目標相結(jié)合，實現(xiàn)多目標的優(yōu)化建模。

縱觀國內(nèi)外研究現(xiàn)狀不難看出，盡管已取得了較多研究成果，但大部分研究成果集中于登機口指派效率等方面，以航站樓內(nèi)始發(fā)旅客的步行距離為研究對象，并沒有充分考慮中轉(zhuǎn)旅客在不同登機口之間的中轉(zhuǎn)時間和換乘緊張度。目前，針對中轉(zhuǎn)旅客換乘問題的登機口優(yōu)化分配建模研究尚不多。針對旅客換乘的模型中主要以中轉(zhuǎn)旅客的換乘時間、換乘舒適度、跨機場換乘的旅客總?cè)藬?shù)最少等為目標進行優(yōu)化[12-13]。這些研究中，對于旅客換乘緊張度的研究較少。因此，分別以總換乘緊張度最小、航班分配失敗率最低及登機口使用數(shù)量最少為目標，建立中轉(zhuǎn)旅客登機口分配優(yōu)化模型，并利用生物地理學(xué)優(yōu)化（BBO，biogeographybased optimization）[14-16]算法對模型進行優(yōu)化求解，從而降低中轉(zhuǎn)旅客的換乘緊張度，提高多航站樓登機口指派效率。

1 模型建立

1.1 問題描述

針對多航站樓的機場運行導(dǎo)致中轉(zhuǎn)旅客換乘時間延長的現(xiàn)狀，研究以中轉(zhuǎn)旅客總換乘緊張度最小、航班分配失敗率最低及登機口使用數(shù)量最少為目標的航班-登機口分配問題。在提高場面登機口運行效率的同時，緩解中轉(zhuǎn)旅客的換乘緊張。

1.2 模型假設(shè)

針對模型進行如下假設(shè)：①航班時間均為國際標準時間；②以換乘旅客為研究對象，不考慮始發(fā)旅客和終到旅客；③航班的實際到達時間、實際出發(fā)時間與航班計劃一致，受天氣狀況、管制等其他突發(fā)因素干擾較小；④研究時段內(nèi)的所有航班信息和旅客中轉(zhuǎn)信息是已知的；⑤旅客中轉(zhuǎn)過程中的換乘時間與登機口位置有關(guān)，即流程、捷運及步行時間是相對固定的，不考慮人為隨機因素的影響；⑥登機口指派是一個連續(xù)過程，選擇一段時間內(nèi)的航班進行指派。

1.3 登機口分配優(yōu)化建模

建立了旅客換乘連接變量，引入“換乘緊張度”參量來評價登機口分配對旅客換乘時間的影響。模型首先最小化中轉(zhuǎn)旅客的總換乘緊張度，其次確定航班分配失敗率最低，盡可能多地將航班分配到合適的登機口；在此基礎(chǔ)上最小化登機口的使用數(shù)量。具體建模過程如下。

1.3.1 目標函數(shù)

中轉(zhuǎn)旅客在中轉(zhuǎn)過程中會受到換乘時間的限制。定義“換乘緊張度”為中轉(zhuǎn)旅客的換乘時間與航班連接時間的比值。總換乘緊張度即單個旅客的換乘緊張度乘以中轉(zhuǎn)旅客數(shù)量。在登機口分配的過程中，需最小化中轉(zhuǎn)旅客的總換乘緊張度。

假設(shè)gk、gm為中轉(zhuǎn)旅客到達登機口和出發(fā)登機口，gk，gm∈G，G為登機口集合。換乘旅客在中轉(zhuǎn)過程中需在登機口gk和gm之間經(jīng)過相關(guān)登機流程、捷運及步行。為登機口gk和gm間中轉(zhuǎn)旅客的最短流程時間，包括安全檢查、辦理中轉(zhuǎn)手續(xù)等為登機口gk和gm間中轉(zhuǎn)旅客的捷運時間，即當?shù)菣C口所在的航站樓不同時，需要搭乘捷運的時間為登機口gk和gm間中轉(zhuǎn)旅客的步行時間。流程時間、捷運時間和步行時間都與登機口gk、gm所在的航站樓及功能屬性有關(guān)。定義該旅客的換乘時間為。

假設(shè)fi為到達航班，fj為出發(fā)航班，fi，fj∈F，F(xiàn)為航班集合。afi為航班fi到達時刻，dfj為航班fj出發(fā)時刻，航班連接時間為dfj－afi。

換乘緊張度表示如下

式中

為使中轉(zhuǎn)旅客的總換乘緊張度最小，建立目標函數(shù)1，即

式中mgk，gm為登機口gk和gm間的中轉(zhuǎn)旅客數(shù)量。

根據(jù)式（1）和式（2）可知，首先確定每個航班分配到與其屬性相符的登機口，進而判斷到達航班fi與出發(fā)航班fj之間是否存在中轉(zhuǎn)旅客。如果存在中轉(zhuǎn)旅客，則進一步確定兩個航班所分配到的登機口位置，根據(jù)登機口所在的區(qū)域確定兩個登機口之間的最短流程時間、捷運時間和步行時間，即獲得中轉(zhuǎn)旅客的中轉(zhuǎn)時間；根據(jù)機票信息確定中轉(zhuǎn)旅客的航班連接時間及中轉(zhuǎn)旅客數(shù)量，進而得到中轉(zhuǎn)旅客的總換乘緊張度。標函數(shù)Z1使得中轉(zhuǎn)旅客的總換乘緊張度最小。

其次，在登機口指派的過程中，應(yīng)將盡可能多的航班分配到登機口，可建立目標函數(shù)2，即

式中：m為待分配航班的總數(shù)量；為出發(fā)航班fi成功分配到登機口gk的航班數(shù)量。目標函數(shù)Z2表示航班分配失敗率最低，即航班分配到合適登機口的數(shù)量最大。

最后，最小化登機口的使用數(shù)量，提高場面資源的運行效率，建立目標函數(shù)3，即

式中zgk為決策變量，用于判斷登機口gk是否被使用。在滿足航班與登機口功能屬性相符的基礎(chǔ)上，盡可能將航班分配到同一登機口，從而最小化登機口的使用數(shù)量。

1.3.2 約束條件

根據(jù)登機口分配規(guī)則，建立如下約束條件。

1）機體類型匹配約束

飛機的機體類型相匹配時，航班fi才能分配到登機口gk。航班機體型號Cfi和登機口機體型號Cgk分為

故有機體類型匹配約束為

2）到達航班類型匹配約束

故有約束為

3）出發(fā)航班類型匹配約束

4）飛機指派約束

轉(zhuǎn)場飛機的到達和出發(fā)兩個航班必須分配到同一登機口，即一個飛機（用其所承運的航班fi替代）只能分配到同一登機口，不能同時分配到多個登機口或轉(zhuǎn)移登機口，故有約束為

5）登機口指派約束

確保分配到同一登機口的兩個航班占用登機口的時間段無重合，afi、dfi為航班fi到達、出發(fā)時刻，afj、dfj為航班fj到達、出發(fā)時刻，故有約束為

6）空檔間隔約束

分配到同一登機口的兩個航班應(yīng)滿足一定的空檔間隔時間，T為同一登機口兩航班之間的空檔時間45 min，故有約束為

式中M為一個足夠大的值，保證式（10）成立。

7）飛機及機位編號正整數(shù)約束

i，j，k∈Z＋（11）

綜上所述，建立如下的多目標多約束登機口分配優(yōu)化模型為

2 模型求解

登機口分配是一個非線性動態(tài)規(guī)劃問題，含有多個約束條件，該問題的優(yōu)化常使用整數(shù)規(guī)劃算法求解[17-19]，部分研究采用啟發(fā)式算法[20-22]，包括蟻群算法、粒子群算法（PSO，particle swarm optimization）等，但這些算法存在運行時間長，且對初始種群依賴性較高的問題，因此，提出基于BBO 來求解該問題。BBO 是基于生物地理學(xué)理論的新型智能優(yōu)化算法，具有良好的收斂性和穩(wěn)定性[14-16]。該算法通常用適應(yīng)度指數(shù)（HSI，habitat suitability index）來描述一個棲息地的種群豐富度，一個棲息地所包含的種群數(shù)量與HSI 成正相關(guān)。該算法的流程圖如圖1所示。

圖1 BBO 算法流程圖Fig.1 The flow chart of the BBO algorithm

模型求解的流程如下：

步驟1將飛機的到達航班類型、出發(fā)航班類型、飛機機體類型等信息與登機口到達類型、出發(fā)類型、登機口機體類型一一對應(yīng)，為每架飛機篩選出屬性匹配的登機口；

步驟2隨機將飛機分配給屬性匹配的登機口，確定每個登機口的開放時間，即該登機口前序飛機的出發(fā)航班時刻，同時滿足45 min 的空檔間隔時間；與未分配登機口的飛機的到達航班時刻相比較，滿足要求即可分配給該登機口，否則拒絕分配，搜索其他可分配登機口；從而生成初始可行解，完成登機口初始分配；

步驟3根據(jù)旅客的到達航班和出發(fā)航班的飛機轉(zhuǎn)場記錄號，確定飛機分配到的登機口編號，進而判斷登機口所屬終端廳區(qū)域；計算每位中轉(zhuǎn)旅客的最短流程時間、捷運時間及步行時間，進而確定旅客的換乘時間；

步驟4根據(jù)旅客轉(zhuǎn)場記錄號、中轉(zhuǎn)旅客的航班連接時間和換乘時間，計算總換乘緊張度；

步驟5對步驟2 生成的初始可行解進行有效評估，將步驟3 和步驟4 計算結(jié)果代入目標函數(shù)Z1、Z2和Z3計算適應(yīng)度函數(shù)，并在定義的種群數(shù)量范圍內(nèi)進行登機口分配結(jié)果更新；

步驟6利用BBO 優(yōu)化種群所有解，在滿足約束條件的基礎(chǔ)上對登機口分配多次迭代，經(jīng)過多次遷移和突變操作，用上代最優(yōu)值替換本代最差值，與當前最優(yōu)解結(jié)果比較，判斷是否更優(yōu)；

步驟7判斷是否滿足迭代次數(shù)，輸出當前最優(yōu)解。

3 仿真驗證

以國內(nèi)某大型機場的航站樓（T）和衛(wèi)星廳（S）登機口結(jié)構(gòu)作為研究對象，T 和S 示意圖如圖2所示。T和S 統(tǒng)稱為終端廳，有捷運線相通，可以快速往來運送國內(nèi)、國際旅客。

圖2 國內(nèi)某大型機場的航站樓（T）和衛(wèi)星廳（S）的設(shè)計Fig.2 The design of the terminals T and S at one airport in China

航站樓有28 個登機口，衛(wèi)星廳有41 個登機口。部分登機口配置數(shù)據(jù)如表1所示。航站樓的登機口分布在North、Center 和South 共3 個區(qū)域，衛(wèi)星廳的登機口分布在North、Center、South 和East 共4 個區(qū)域；登機口的出發(fā)航班和到達航班類型分為國際航班（I）和國內(nèi)航班（D）；機體類型分為窄體機（N）和寬體機（W）。

表1 國內(nèi)某大型機場的航站樓登機口配置數(shù)據(jù)Tab.1 The configuration data of gates at one airport in China

選擇該機場在2018年1月19日的飛機轉(zhuǎn)場計劃和中轉(zhuǎn)旅客信息進行模型的仿真驗證。轉(zhuǎn)場飛機共606 架次，飛機轉(zhuǎn)場計劃部分如表2所示。中轉(zhuǎn)旅客共2 751 人，部分旅客中轉(zhuǎn)信息如表3所示。

表2 國內(nèi)某大型機場的飛機轉(zhuǎn)場計劃Tab.2 The transit record of aircrafts at one airport in China

表3 國內(nèi)某大型機場的旅客中轉(zhuǎn)信息Tab.3 The information of transit passengers at one airport in China

中轉(zhuǎn)旅客從前序航班的到達至后序航班的出發(fā)之間的流程，按D、I、T、S 組合成16 種不同的場景。這些場景的最短流程時間和乘坐捷運次數(shù)如表4所示。假定旅客無需等待，隨時可以發(fā)車，單程捷運時間為8 min。換乘旅客的步行時間與登機口所在區(qū)域有關(guān)，如表5所示。

表4 換乘旅客的中轉(zhuǎn)流程時間和捷運次數(shù)Tab.4 The process time and metro rides of transit passengers

表5 換乘旅客的步行時間Tab.5 The walking time of transit passengers min

3.1 適應(yīng)度函數(shù)收斂

運用C 語言編程求解多目標多約束的登機口分配優(yōu)化問題，在求解過程中分別以Z2+Z3及Z1+Z2+Z3為目標函數(shù)進行優(yōu)化，對比分析旅客換乘緊張度對于登機口分配的影響。其最優(yōu)解的迭代進化過程如圖3所示。

圖3 模型最優(yōu)解迭代進化過程Fig.3 The evolution of the optimal solution of the model iterative

在目標函數(shù)優(yōu)化的過程中，首先會根據(jù)登機口分配的約束條件隨機分配，然后通過BBO 的遷移和突變操作改變登機口分配的結(jié)果，并不斷優(yōu)化目標函數(shù)，使其函數(shù)值不斷減小。當?shù)螖?shù)達到85 次時，適應(yīng)度函數(shù)的收斂速度最快，在1 000 次附近，適應(yīng)度函數(shù)進一步收斂。

3.2 中轉(zhuǎn)旅客換乘緊張度分析

登機口分配優(yōu)化模型的仿真結(jié)果與采用相同數(shù)據(jù)的航班先到先服務(wù)（FCFS，first come first served）調(diào)度結(jié)果相比較。在FCFS、Z2+Z3及Z1+Z2+Z3的優(yōu)化結(jié)果中，中轉(zhuǎn)旅客的換乘時間分布和換乘緊張度分布如圖4 和圖5所示。

圖4 旅客換乘時間分布Fig.4 The distribution of transfer time for passengers

圖5 旅客換乘緊張度分布Fig.5 The distribution of transit tension for passengers

由圖4 和圖5 可知，換乘時間在80 min 以內(nèi)的旅客中，換乘時間在50 ～75 min 內(nèi)的人數(shù)相對較多。旅客的換乘緊張度在0.1 ～0.5 之間的比例較大，其他區(qū)間較小。在FCFS 的分配結(jié)果中，45 min 內(nèi)成功換乘的旅客比例為9%；54%的旅客換乘緊張度在1.0 之內(nèi)。在基于目標函數(shù)Z2+Z3的分配結(jié)果中，45 min 內(nèi)成功換乘的旅客比例為12%；58%的旅客換乘緊張度在1.0之內(nèi)，相比于FCFS 提高了4%。在基于目標函數(shù)Z1+Z2+Z3的分配結(jié)果中，45 min 內(nèi)成功換乘的旅客比例為15%，70%的旅客換乘緊張度在1.0 之內(nèi)，相比于FCFS提高了16%。在登機口分配優(yōu)化建模中，考慮中轉(zhuǎn)旅客的換乘緊張度，不僅降低了中轉(zhuǎn)旅客的換乘時間和換乘緊張度，而且增加了中轉(zhuǎn)旅客的換乘成功率，提高了中轉(zhuǎn)旅客的服務(wù)效率。

3.3 登機口分配結(jié)果對比分析

登機口分配優(yōu)化模型的仿真結(jié)果與采用相同數(shù)據(jù)的FCFS 調(diào)度結(jié)果相比較，對比分析如表6～表8所示。

表6～表8的數(shù)據(jù)結(jié)果顯示，在登機口分配過程中，基于FCFS 的航班分配成功數(shù)量為448 架次，登機口使用數(shù)量69 個，其中T 和S 的登機口平均使用率分別為73.46%和38.61%，成功換乘人數(shù)1 487 人，總換乘緊張度為3 474。基于目標函數(shù)Z2+Z3成功分配航班498 架次，提高了11%；登機口使用65 個，且登機口的平均使用率增加，說明提高了登機口的使用效率；成功換乘1 588 人，總換乘緊張度為3 288，相比于FCFS 降低了5%。基于目標函數(shù)Z1+Z2+Z3成功分配航班進一步增加至502 架次，相比于FCFS 分配結(jié)果提高了12%；寬體機分配成功率為100%；登機口使用66個，登機口的平均使用率較高；成功換乘人數(shù)1 936人，相比于FCFS 增加了30%，總換乘緊張度最低為2 622，相比于FCFS 降低了25%。相比于前兩種模型，第3 種模型能夠降低航班分配失敗率，顯著減少旅客的換乘時間和換乘緊張度，且登機口的使用效率較高，更加符合登機口分配的需求。

表6 中轉(zhuǎn)航班的分配結(jié)果Tab.6 The assignment results of transit flights

表7 航站樓T 和S 的登機口使用結(jié)果Tab.7 The assignment results of flights at terminal T and S

表8 中轉(zhuǎn)旅客的換乘情況Tab.8 The transfer results of transit passengers

4 結(jié)語

（1）考慮中轉(zhuǎn)旅客在換乘過程中的中轉(zhuǎn)時間建立了“換乘緊張度”的參量，評價登機口分配對于中轉(zhuǎn)旅客的影響程度。以中轉(zhuǎn)旅客總換乘緊張度最小、航班分配失敗率最低及登機口使用數(shù)量最少為目標，同時考慮航班分配的登機口類型約束、航班沖突約束等條件，建立多目標多約束的登機口分配優(yōu)化模型。

（2）采用BBO 對模型進行仿真驗證，計算效率較高。模型算法的求解速度和效率及收斂性受種群數(shù)量和變異概率影響較大，一般而言，種群數(shù)量越大，求解成功的概率也越大。但過高的種群數(shù)量會大大增加計算時間。

（3）模型可使更多的旅客在換乘成功的同時，換乘緊張度降低，在保證場面資源利用效率的同時，提高旅客的服務(wù)滿意度。

考慮中轉(zhuǎn)旅客的換乘緊張度在登機口分配優(yōu)化方面的研究目前非常少，下一步的研究工作是將該方法推廣到航空器場面運行和航站樓設(shè)計的聯(lián)合應(yīng)用中，探討不同智能算法求解的優(yōu)劣性。