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

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

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

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

1 問題描述

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

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

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

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

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

2 問題描述

2.1 問題的條件假設

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

(1) 航班的到達、離開，飛機的?？俊㈦x開均按公布時間完成。

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

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

(4)飛機占用登機口，到起飛離開后，占用此登機口時間機型按標準時間執(zhí)行。

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

2.2 問題的分析和建模

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

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

(1)

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

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

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

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

(2)

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

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

(3)

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

(3)登機口使用數(shù)目標函數(shù)：

(4)

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

約束條件：

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

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

(5)

每架飛機至多安排一個登機口：

(6)

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

(7)

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

Pk=FAkFDk， ?k∈m

(8)

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

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

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

(9)

(10)

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

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

(11)

(12)

(13)

式(13)中：wf為航班因素權重；wg為登機口因素權重；wp為中轉旅客因素權重。

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

(14)

(15)

3 模型的求解算法

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

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

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

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

(3)計算種群中個體的適應度值并進行選擇操作。

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

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

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

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

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

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

(16)

4 實例計算與結果分析

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

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

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

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

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

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

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

(17)

4.2 計算結果分析

利用MATLAB程序對模型進行編程求解，模型求解部分結果如圖4所示。

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

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

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

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

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

5 結論

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