董 兵, 吳鄭源, 賴桂瑾, 梁延安, 潘衛(wèi)軍

(中國民用航空飛行學(xué)院空中交通管理學(xué)院，廣漢 618307)

據(jù)統(tǒng)計，2018年北京首都國際機(jī)場年旅客吞吐量突破1億人次，而全國旅客突破千萬級的機(jī)場增至37家。各機(jī)場航班量快速增長，導(dǎo)致了機(jī)場登機(jī)口不足，不僅使作業(yè)秩序變差，效率下降，機(jī)場航班安排受限，也降低了旅客的服務(wù)質(zhì)量，制約了行業(yè)的健康發(fā)展。合理的登機(jī)口分配可以大大提高機(jī)場的運(yùn)行水平，減少旅客步行距離，并提升旅客的滿意度。為解決該問題，部分機(jī)場通過修建衛(wèi)星廳的方式來提升飛機(jī)的靠橋率。由于候機(jī)樓和衛(wèi)星廳通常會有一段距離，對本身已很復(fù)雜的登機(jī)口的分配問題，如何解決該類航站樓的登機(jī)口的分配問題已經(jīng)成為機(jī)場運(yùn)營亟待解決的關(guān)鍵問題。

登機(jī)口指派問題類似于停機(jī)位指派問題。當(dāng)飛機(jī)無法?？坷葮驎r，通常會被安排在遠(yuǎn)機(jī)位，通過擺渡車與候機(jī)樓建立聯(lián)系。登機(jī)口指派問題一個NP(non-polynomial)難問題，通常有多個目標(biāo)函數(shù)和約束條件，它的算法復(fù)雜程度隨航班的增加成指數(shù)增長，短時間很難得到最優(yōu)解。針對停機(jī)位指派問題，目前外國學(xué)者已提出多種分析方法。Jo等[1]、Brazile等[2]提出的專家系統(tǒng)方法通過將配置原則建立在知識庫系統(tǒng)上，考慮了較多的非量化準(zhǔn)則，但由于這類方法受搜索范圍的限制，易忽視關(guān)鍵因素而導(dǎo)致分配結(jié)果不理想。此外，一些基于數(shù)學(xué)模型的方法，如Yu[3]、Yan等[4]所建立的模型以減少旅客的步行距離，減少未被利用的停機(jī)位數(shù)量，減少使用停機(jī)位的時間段范圍為目標(biāo)[5]，這類數(shù)學(xué)模型通常使用分枝定界算法，0-1數(shù)學(xué)規(guī)劃、混合數(shù)學(xué)規(guī)劃或網(wǎng)絡(luò)流問題等數(shù)學(xué)方法對分配方案進(jìn)行搜索優(yōu)化，來給停機(jī)場機(jī)位分配提供方案，但在運(yùn)算時間上不能夠完全滿足需要。由于受到目標(biāo)函數(shù)的影響，會出現(xiàn)把較多的航班分配給較少的有吸引力的停機(jī)位，同時航班時刻的微小變化都會容易引起停機(jī)位分配的混亂和計算量的大增，降低了分配方案的魯棒性。Zhu等[6]建立了一個以乘客步行距離最小和飛機(jī)的延誤最小為目標(biāo)的模型；李軍會等[7]提出了基于貪婪算法的停機(jī)位分配方案；馮程等[8]提出了考慮滑行路徑的分配方案。禁忌搜索(tabu search，TS)算法最早由Glover于1986年提出[9]，它是對局部鄰域搜索的一種擴(kuò)展。遺傳算法(genetic algorithm, GA)是由美國Holland教授于1975 年首先提出的一種新的全局優(yōu)化搜索算法[10]。GA算法具有內(nèi)在的隱并行性，與其他優(yōu)化算法相比，具有更好的全局尋優(yōu)能力，但由于GA算法采用根據(jù)適應(yīng)度的大小來決定個體是否被復(fù)制的選擇機(jī)制，易出現(xiàn)來源于同一種群的個體被大量繁衍的情況，形成近親繁殖，造成算法的局部搜索和過早收斂，從而導(dǎo)致全局尋優(yōu)過程失敗[11]。為了克服GA算法和TS算法的缺點(diǎn)，發(fā)揮它們的優(yōu)勢，針對新增衛(wèi)星廳的機(jī)場，在參考已有文獻(xiàn)的基礎(chǔ)上，建立基于成功分配航班數(shù)最多、登機(jī)口使用數(shù)目最少以及中轉(zhuǎn)旅客花費(fèi)時間最短為目標(biāo)的登機(jī)口分配的數(shù)學(xué)模型，采用遺傳禁忌搜索(GA-TS)算法[12]，在解決航班能成功分配登機(jī)口數(shù)量最大的前提下，給出中轉(zhuǎn)旅客最短流程時間之和最小的方案，以期得到滿足機(jī)場實際運(yùn)行需求的分配方案。

1 問題描述

考慮某機(jī)場在已有航站樓T的基礎(chǔ)上，新增衛(wèi)星廳S。航站樓T具備完整的國際機(jī)場航站樓功能，包括出發(fā)、到達(dá)、出入境和候機(jī)，而衛(wèi)星廳S作為航站樓T的延伸，可以出發(fā)、到達(dá)、候機(jī)，沒有出入境功能，機(jī)場布局如圖1所示。

圖1 機(jī)場航站樓T與衛(wèi)星廳S的布局示意圖Fig.1 Schematic diagram of layout of airport terminal T and satellite hall S

新增引入衛(wèi)星廳后，緩解了原有航站樓登機(jī)口不足的壓力，但對中轉(zhuǎn)旅客的航班銜接具有負(fù)面影響?？紤]登機(jī)口數(shù)和航班到離場時刻等條件下，加入中轉(zhuǎn)旅客換乘因素，著手解決如何優(yōu)化分配登機(jī)口，使得航班盡量多的分配到登機(jī)口，降低中轉(zhuǎn)旅客的換乘緊張程度，并在此基礎(chǔ)上減少登機(jī)口的使用數(shù)量，從而提高方案的魯棒性。當(dāng)加入中轉(zhuǎn)旅客換乘因素，在換乘航班時需要有一定的時間來辦理相關(guān)手續(xù)，將其定義為最短流程時間。由于航站樓T和衛(wèi)星廳S不能直達(dá)，需通過捷運(yùn)線連接(電車軌道)。乘客在候機(jī)樓中從廊橋到候機(jī)樓中心步行的時間由表1給出，最短流程時間和捷運(yùn)乘坐次數(shù)如表2所示。

表1 旅客行走時間Table 1 Walking time of passengers

表2 最短流程時間及捷運(yùn)線乘坐次數(shù)Table 2 Minimum process time and number of MRT rides

2 問題描述

2.1 問題的條件假設(shè)

為了方便問題的處理，需要對問題進(jìn)行一些簡化處理，具體如下。

(1) 航班的到達(dá)、離開，飛機(jī)的停靠、離開均按公布時間完成。

(2)飛機(jī)到達(dá)后，如沒有分配登機(jī)口，則將該機(jī)?？吭谶h(yuǎn)機(jī)位，此時擺渡車送人到航站樓或者衛(wèi)星廳的時間可忽略不計，可認(rèn)為飛機(jī)?？吭诤秸緲腔蛘咝l(wèi)星廳。

(3)飛機(jī)一旦分配登機(jī)口，則一直占用登機(jī)口，不能移至其他登機(jī)口或臨時停機(jī)坪，直到該機(jī)起飛。

(4)飛機(jī)占用登機(jī)口，到起飛離開后，占用此登機(jī)口時間機(jī)型按標(biāo)準(zhǔn)時間執(zhí)行。

(5)有中轉(zhuǎn)旅客的捷運(yùn)時間和行走時間均以表1、表2為準(zhǔn)，忽略個體差異。

2.2 問題的分析和建模

首先考慮約束條件：①飛機(jī)類型，需與登機(jī)口相匹配，大中型飛機(jī)不能被分配至小型登機(jī)口；②每個飛機(jī)只能分配一個登機(jī)口，或者不分配登機(jī)口；③分配到同一登機(jī)口的相鄰飛機(jī)之間需要間隔45 min以上。

因此，模型具有三個目標(biāo)函數(shù)，優(yōu)先級從高到低。

(1)

式(1)中：Mij為航班-登機(jī)口匹配矩陣M的元素；ai為?？康菣C(jī)口飛機(jī)類型；n為需要安排登機(jī)口的飛機(jī)架次，為當(dāng)日的航班架次； 1≤i≤n；gj表示第登機(jī)口能夠停靠飛機(jī)的類型；m為所有登機(jī)口數(shù)量，1≤j≤m。

飛機(jī)的集合為F，登機(jī)口的集合為G，F(xiàn)和G的笛卡兒乘積記作F×G，即，F(xiàn)×G={〈fi,gj〉fi∈Fandgj∈G}為飛機(jī)對應(yīng)登機(jī)口有序?qū)Φ募?。對于航班序?f1,f2,…,fn)分配到對應(yīng)的登機(jī)口(g1,g2,…,gm)，其有序?qū)i=〈fi,gj〉構(gòu)成的序列x稱為航班序列的分配方案。

根據(jù)假設(shè)構(gòu)建登機(jī)口分配優(yōu)化問題的數(shù)學(xué)模型，目標(biāo)函數(shù)綜合如下。

(1)航班分配數(shù)目標(biāo)函數(shù)：

(2)

式(2)中:fi為0-1變量，表示第i架飛機(jī)是否分配登機(jī)口。

(2)最短流程時間和目標(biāo)函數(shù)：

(3)

式(3)中：l為有效中轉(zhuǎn)旅客組數(shù)；P為有效中轉(zhuǎn)旅客集合，P={P1,P2,…,Pl}；Pk為0-1變量，表示第k組中轉(zhuǎn)旅客是否成功轉(zhuǎn)機(jī)；Tk表示第k組中轉(zhuǎn)旅客最短流程時間。

(3)登機(jī)口使用數(shù)目標(biāo)函數(shù)：

(4)

式(4)中：Gj為0-1變量，表示第j號登機(jī)口是否使用。

約束條件：

(1)Ai,j為0-1變量，表示航班-登機(jī)口實際匹配矩陣。飛機(jī)登機(jī)口類型匹配表示為

Ai,j≤Mi,j, ?i∈n,?j∈m

(5)

每架飛機(jī)至多安排一個登機(jī)口：

(6)

(2)飛機(jī)時間不允許沖突，即

(7)

(3)只考慮出發(fā)到達(dá)航班分配了登機(jī)口的旅客，得：

Pk=FAkFDk， ?k∈m

(8)

式(8)中：下標(biāo)Ak表示第k組中轉(zhuǎn)旅客到達(dá)航班；下標(biāo)Dk表示第k組中轉(zhuǎn)旅客離開航班；引入其他變量的附加約束條件如下。

(4)飛機(jī)航班是否分配與實際分配間的約束表示為

max(Ai,j)≤Fi, ?i∈n,?j∈m

(9)

(10)

(5)航班-登機(jī)口實際分配與登機(jī)口的是否使用的約束表示為

max(Ai,j)≤Gj, ?i∈n,?j∈m

(11)

(12)

(13)

式(13)中：wf為航班因素權(quán)重；wg為登機(jī)口因素權(quán)重；wp為中轉(zhuǎn)旅客因素權(quán)重。

根據(jù)多目標(biāo)函數(shù)的處理方法，對不同優(yōu)先級設(shè)定不同的權(quán)重。

(14)

(15)

3 模型的求解算法

式(14)、式(15)具有三個不同優(yōu)先級的目標(biāo)函數(shù)，屬于多目標(biāo)規(guī)劃模型。由于數(shù)據(jù)量大，約束條件多，不易獲得精確解，采用遺傳禁忌搜索算法，以期求得較好結(jié)果。

使用GA算法和TS算法相結(jié)合組成GA-TS 混合算法，即以GA 算法為整個算法的框架，對GA 經(jīng)過遺傳操作運(yùn)算后產(chǎn)生的新種群的個體，用TS 算法進(jìn)行局部搜索，改善群體的質(zhì)量。GA-TS 算法可以有效結(jié)合GA算法并行的大范圍搜索能力和TS算法的局部搜索能力，其主要操作步驟如下。

(1)確定種群大小n，交叉概率pc，變異概率pm。

(2)通過先到先服務(wù)原則(first come first service,FCFS)，初始化種群：產(chǎn)生n組可行解組成初始種群p0。

(3)計算種群中個體的適應(yīng)度值并進(jìn)行選擇操作。

(4)按照交叉概率pc、變異概率pm進(jìn)行遺傳操作。

(5)對GA 產(chǎn)生的新種群進(jìn)行TS算法收索，改進(jìn)種群個體的質(zhì)量，產(chǎn)生新一代的個體。

(6)算法終止條件判斷，如果滿足終止條件，則輸出最優(yōu)解，算法結(jié)束，否則轉(zhuǎn)步驟(3)。具體流程如圖2、圖3所示。

圖2 基于遺傳算法的機(jī)位分配流程圖Fig.2 Flow chart of airport gate assignment based on GA

圖3 禁忌搜索算法流程圖Fig.3 Flow chart of TS algorithm

本文模型中，種群即為航班登機(jī)口分配方案，使用隨機(jī)化的FCFS算法生成初始種群，種群大小為100。遺傳運(yùn)算中，交叉概率pc取值0.95，變異概率pm取值0.05，在計算適應(yīng)度時，使用TS算法來改進(jìn)種群個體質(zhì)量，使得找到最優(yōu)解效率有所提升。適應(yīng)度函數(shù)fitness選?。?/p>

(16)

4 實例計算與結(jié)果分析

4.1 數(shù)據(jù)處理分析

數(shù)據(jù)來自某機(jī)場，其中航站樓T有28個登機(jī)口，衛(wèi)星廳S有41個登機(jī)口。登機(jī)口的屬性有：所在終端廳(T/S)、區(qū)域(North/Center/South/East)、能接受的航班到達(dá)類型(國際I/國內(nèi)D)、能接受的航班出發(fā)類型(國際I/國內(nèi)D)以及能?？匡w機(jī)的寬窄(寬W/窄N)類型。登機(jī)口屬性不可修改，且只能接受航班到達(dá)類型、出發(fā)類型、機(jī)體寬窄類型以及適合的轉(zhuǎn)場計劃。

根據(jù)統(tǒng)計，當(dāng)天的數(shù)據(jù)涉及303架飛機(jī)轉(zhuǎn)場，1 649組中轉(zhuǎn)乘客，69個登機(jī)口。表3僅列出了部分飛機(jī)轉(zhuǎn)場數(shù)據(jù)，飛機(jī)轉(zhuǎn)場數(shù)據(jù)包括：飛機(jī)轉(zhuǎn)場記錄號、到達(dá)日期、到達(dá)時刻、到達(dá)航班號、達(dá)到類型、飛機(jī)型號、出發(fā)日期、出發(fā)時刻、出發(fā)航班號、出發(fā)類型、上線機(jī)場及下線機(jī)場。限于中轉(zhuǎn)換乘旅客數(shù)據(jù)較多，僅列出了部分中轉(zhuǎn)數(shù)據(jù)。中轉(zhuǎn)數(shù)據(jù)包含：旅客記錄號、乘客數(shù)、到達(dá)航班、到達(dá)日期、出發(fā)航班、出發(fā)日期。飛機(jī)轉(zhuǎn)場、登機(jī)口、中轉(zhuǎn)乘客部分?jǐn)?shù)據(jù)如表3～表5所示。根據(jù)機(jī)場航班登機(jī)口分配的要求，僅考慮20號到達(dá)或者20號出發(fā)的航班，數(shù)據(jù)中給出的時間均為年、月、日、時、分，為方便后期處理，統(tǒng)一將所有的時間全部轉(zhuǎn)化為與2018年1月19日凌晨零時的時間之差。

表3 飛機(jī)轉(zhuǎn)場數(shù)據(jù)Table 3 Data of the transferring aircrafts

表4 登機(jī)口數(shù)據(jù)Table 4 Data of the gates

表5 中轉(zhuǎn)乘客數(shù)據(jù)Table 5 Data of the transferring passengers

根據(jù)假設(shè)，涉及的轉(zhuǎn)場飛機(jī)、登機(jī)口數(shù)、有效中轉(zhuǎn)旅客乘客組數(shù)分別為

(17)

4.2 計算結(jié)果分析

利用MATLAB程序?qū)δＰ瓦M(jìn)行編程求解，模型求解部分結(jié)果如圖4所示。

圖4 航班-登機(jī)口分配甘特圖Fig.4 Gantt chart of flight-gates allocation

(1)該模型能夠給510個航班(255架飛機(jī))成功分配登機(jī)口，占有效航班數(shù)的84.16%，其中使用了64個登機(jī)口，占可用登機(jī)口的92.75%；寬體機(jī)成功分配航班數(shù)為98個航班，分配成功率為100%，窄體機(jī)成功分配航班數(shù)為412，分配成功率約為81.10%。此時的有效中轉(zhuǎn)旅客的最短流程時間之和為64 735 min，約合1 078 h。圖4中為航班-登機(jī)口分配方案的甘特圖，以及航班的具體分配情況，僅包含20日00：00—24:00數(shù)據(jù)。

(2)航班?？苛?6個位于航站樓T的登機(jī)口，使用率為57.4%；航班?？?8個位于衛(wèi)星廳S的登機(jī)口，使用率為61%。

(3)圖5為以5 min為單位間隔的不同間隔時間段的中轉(zhuǎn)旅客的概率及概率累計圖。通過概率累計圖來反映旅客中轉(zhuǎn)的所花費(fèi)時間，從而為降低中轉(zhuǎn)時間提供了方向。

柱狀圖表示為每5 min為間隔的中轉(zhuǎn)旅客的概率；折線圖代表從0 min到當(dāng)前 min概率累計圖圖5 中轉(zhuǎn)旅客最短流程時間的所處時間段的概率及概率累計圖Fig.5 Probability cumulative diagram of the shortest process time for transit passengers

5 結(jié)論

建立基于航班成功分配登機(jī)口最多的規(guī)劃模型，客觀合理地抽象了航班-登機(jī)口分配問題。在考慮中轉(zhuǎn)旅客最短換乘時間的請款下，建立了在成功合理安排更多航班的前提下的中轉(zhuǎn)旅客最短流程時間總和最少的規(guī)劃模型。在求解過程中，采用了將遺傳算法和禁忌搜索算法相結(jié)合互補(bǔ)的遺傳禁忌搜索算法，得到了優(yōu)化后結(jié)果。提出的計算模型對于計算航班-登機(jī)口分配方案仍有一些不足，例如模型并沒有考慮旅客換乘航班為不同架次飛機(jī)的情況。在后期的研究中，應(yīng)更多考慮機(jī)場的實際運(yùn)營情況，還應(yīng)考慮航班的動態(tài)進(jìn)場和離場以及航班?？亢屯瞥龅菣C(jī)口時刻變動等因素。