基于貪婪-遺傳算法的機場登機口分配策略

胡 杰, 鮑 帆, 石瀟竹

(1. 中國電子科技集團公司第二十八研究所, 江蘇 南京 210007;2. 空中交通管理系統(tǒng)全國重點實驗室, 江蘇 南京 210007)

0 引 言

隨著航空運輸業(yè)的快速發(fā)展,航班量也隨之日益增長,使得部分機場登機口出現(xiàn)嚴(yán)重不足的情形,登機口資源沖突頻發(fā),影響機場運營效率與安全,同時也降低了旅客出行滿意度。為解決該問題,大型樞紐機場通過在現(xiàn)有航站樓T的基礎(chǔ)上新增衛(wèi)星廳S,以緩解機場登機口不足的壓力,提高過站飛機靠橋率。通常,航站樓T與衛(wèi)星廳S有一段間隔距離,這對過境旅客的航班銜接產(chǎn)生了一定的負面影響,增加了中轉(zhuǎn)旅客換乘失敗的機率。因此,如何解決具有衛(wèi)星廳的機場登機口分配問題,最大限度地優(yōu)化登機口配置,已成為當(dāng)前大型機場運營亟待解決的問題之一[1-2]。

機場航班-登機口分配屬于運籌學(xué)多目標(biāo)優(yōu)化問題,其求解目標(biāo)函數(shù)由機場決策者根據(jù)運營情況決定。國內(nèi)外學(xué)者從乘客和機場運營兩個層面建立并求解了諸多登機口分配優(yōu)化模型。

首先,從乘客角度考慮,Braaksma等[3]首次提出了航班-登機口分配優(yōu)化模型,并以最小化旅客航站樓內(nèi)行走距離為目標(biāo)函數(shù)實現(xiàn)登機口資源最優(yōu)化分配。隨后,Babic等[4]建立了機場登機口分配0-1整數(shù)規(guī)劃模型,該模型以最小化旅客航站樓內(nèi)的行走總距離為優(yōu)化目標(biāo),并基于分支定界算法求解優(yōu)化模型,但其未考慮中轉(zhuǎn)旅客航班銜接問題。Mangoubi等[5]在文獻[4]研究基礎(chǔ)上,將中轉(zhuǎn)旅客的步行距離作為優(yōu)化目標(biāo)建立了機場登機口分配模型,采用線性松弛法和啟發(fā)式算法求解該模型,結(jié)果表明,啟發(fā)式算法的性能接近最優(yōu)。馮程等[6]基于傳統(tǒng)滑行路徑理念,建立了降低旅客進出機場空側(cè)時間的登機口分配模型,采用啟發(fā)式算法求解模型,取得了較好的分配效果。Jiang等[7]從乘客服務(wù)質(zhì)量角度出發(fā),建立了以縮短乘客步行總距離和均衡各航空公司的旅客平均步行距離為目標(biāo)的登機口指派模型,采用Lingo軟件進行仿真驗證。上述研究表明,合理指派機場登機口位置可以有效降低乘客步行距離,提高機場服務(wù)滿意度。

然后,從機場運行角度出發(fā),Liu等[8]以最小化登機口空檔間隔時間方差為優(yōu)化目標(biāo)建立了具有運行安全約束的魯棒登機口分配模型,采用遺傳算法求解該問題。Kim等[9]通過分析主要機場航班延時數(shù)據(jù),建立了以最小化同一登機口的前后航班沖突率為目標(biāo)的登機口分配模型,采用啟發(fā)式貪婪算法求解模型。Yu等[10]在顧忌機場運營成本基礎(chǔ)上,提出了魯棒登機口分配模型,設(shè)計了一種自適應(yīng)大規(guī)模領(lǐng)域搜索算法求解該模型。王巖華等[11]在考慮航班屬性、機位尺寸等約束條件下,以航班靠橋率和廊橋周轉(zhuǎn)率為優(yōu)化目標(biāo)建立了繁忙機場登機口分配模型,并利用混合集合規(guī)劃方法求解算法模型,結(jié)果表明混合集合規(guī)劃方法有效提升了航班靠橋率。Tan等[12]針對非正常抵達航班導(dǎo)致的登機口分配不確定性問題,提出了一種基于航班到達時間分析的魯棒登機口分配方案,并利用遺傳算法實現(xiàn)模型求解,從而減小了航班計劃變化對初始分配結(jié)果的影響。劉君強[13]等對多航站樓機場登機口分配問題進行了研究,建立了基于協(xié)同決策并考慮航司時隙交換公平性的登機口實時分配模型,采用混合集合規(guī)劃進行模型求解。隨著機場登機口分配模型研究的不斷深入,基于多目標(biāo)優(yōu)化的登機口分配模型成為研究熱點,多目標(biāo)情況下的登機口分配模型求解較為困難[14-15]。Zhu等[16]建立了機場登機口分配多目標(biāo)0-1線性規(guī)劃模型,考慮了乘客航站樓內(nèi)行走總距離和航班延誤成本兩個優(yōu)化目標(biāo)。Deng等[17]建立了機場登機口多目標(biāo)優(yōu)化模型,該模型綜合考慮了旅客行走距離、登機口空擋間隔時間方差、分配在固定登機口航班數(shù)量和寬登機口使用率4個優(yōu)化目標(biāo),并采用線性加權(quán)法實現(xiàn)多目標(biāo)優(yōu)化向單目標(biāo)優(yōu)化的轉(zhuǎn)變,然后采用粒子群算法求解該模型。Zhang等[18]在考慮機型、相鄰登機口沖突等約束條件基礎(chǔ)上,以最小化航班延遲數(shù)、登機口變更比例和中轉(zhuǎn)失敗乘客數(shù)為優(yōu)化目標(biāo),建立了基于多商品流網(wǎng)絡(luò)模型的登機口重分配模型,利用兩種啟發(fā)式算法完成真實數(shù)據(jù)驗證。

由上述國內(nèi)外研究現(xiàn)狀可知,單純的機場登機口分配問題已經(jīng)得到了較好的解決,且有成熟的產(chǎn)品滿足航司和地勤服務(wù)公司的應(yīng)用需求,但是在實現(xiàn)登機口優(yōu)化分配的同時考慮中轉(zhuǎn)旅客行走時間和距離的研究有限[19]。針對大型樞紐機場新建衛(wèi)星廳,本文在考慮航班類型、機體類型和轉(zhuǎn)場時間間隔等約束條件基礎(chǔ)上,建立了以成功分配航班數(shù)至固定登機口最多、中轉(zhuǎn)旅客的總體最短流程時間最小以及固定登機口使用數(shù)量最少為優(yōu)化目標(biāo)的機場登機口分配模型,利用貪婪算法計算生成初始種群,并利用遺傳算法實現(xiàn)模型求解,最后用一組大型樞紐機場的實際運營數(shù)據(jù)對本文所提出的登機口優(yōu)化分配模型和算法進行驗證。

1 問題描述

由于城市建設(shè)規(guī)模的快速發(fā)展,該市機場現(xiàn)有航站樓T的旅客流量已經(jīng)達到飽和狀態(tài),為了應(yīng)對未來的發(fā)展,在航站樓T附近新建了衛(wèi)星廳S,航站樓T和衛(wèi)星廳S之間有捷運線相通,其布局設(shè)計如圖1所示。新建衛(wèi)星廳后原有航站樓的運營保障壓力得到了極大緩解,同時航班靠橋率也相應(yīng)得到了提升,但是新建衛(wèi)星廳對于部分中轉(zhuǎn)旅客的航班銜接產(chǎn)生了較大的負面影響[20]。將中轉(zhuǎn)旅客換乘因素作為登機口分配優(yōu)化目標(biāo)之一,實現(xiàn)機場登機口多目標(biāo)優(yōu)化是目前大型樞紐機場亟待解決的問題之一。本文研究以中轉(zhuǎn)旅客的總體最短流程時間最小、分配至固定登機口的航班數(shù)量最多以及登機口使用數(shù)量最少為目標(biāo)的航班-登機口分配問題,在有效提高機場登機口資源使用率的同時,提升中轉(zhuǎn)旅客的出行滿意度。

航站樓T具備完整的國際機場航站樓功能,包括出發(fā)、到達、出入境和候機,而衛(wèi)星廳S僅可以提供出發(fā)、到達和候機功能,無出入境功能。對于中轉(zhuǎn)旅客來說,換乘航班時需要有一定的時間辦理相關(guān)手續(xù),定義該時間為中轉(zhuǎn)旅客最短流程時間。對于任一中轉(zhuǎn)旅客,其最短流程時間由到達航班類型、登機口區(qū)域以及出發(fā)航班類型決定,共有16種不同組合場景,表1給出了16種不同組合場景下的最短流程時間。

表1 最短流程時間

2 航班-登機口分配模型

2.1 模型假設(shè)

為構(gòu)建機場登機口多目標(biāo)優(yōu)化模型,航班-登機口的分配需要考慮如下規(guī)則。

(1) 機場臨時停機位數(shù)量滿足該時段內(nèi)所有未分配到固定登機口的航班?？?且對?？康娘w機無約束。

(2) 由同一架飛機執(zhí)行的到達和出發(fā)兩個航班只能分配在同一停機位,飛機?？科陂g不可挪移至其他位置。

(3) 飛機轉(zhuǎn)場信息、旅客信息和登機口信息等均已知,且不考慮當(dāng)天退票情況。

(4) 機場所有登機口的功能屬性不能改變,且轉(zhuǎn)場航班只能停靠在與之屬性相匹配的登機口。

(5) 分配在同一登機口的相鄰兩個航班之間的空檔間隔時間不小于45 min。

2.2 模型建立

2.2.1 約束條件

假設(shè)機場在某時間段內(nèi)需要安排的轉(zhuǎn)場航班數(shù)為M,機場固定登機口數(shù)為N,在該段時間內(nèi)有效的中轉(zhuǎn)旅客組數(shù)為P,令i、j、l分別表示第i個轉(zhuǎn)場航班、第j個登機口和第l組旅客(i=1,2,…,M;j=1,2,…,N;l=1,2,…,P)。

令xi,j為航班-登機口分配問題的決策變量,定義該變量取值為

(1)

根據(jù)機場實際運營情況,并考慮模型假設(shè),建立如下的決策變量約束條件。

(1) 唯一性約束為

(2)

式(2)保證一架飛機只能安排在一個固定登機口,且中途不會被挪移。

(2) 到達航班類型約束為

|(T1,i-T2,j)xi,j|≠1

(3)

式中:T1,i表示轉(zhuǎn)場航班i的到達航班類型;T2,j表示登機口j接受的到達航班類型。

T1,i=0表示轉(zhuǎn)場航班i來自國外,T1,i=1表示轉(zhuǎn)場航班i來自國內(nèi);T2,j=0表示登機口j接受來自國外的航班,T2,j=1表示登機口j接受來自國內(nèi)的航班,T2,j=3表示登機口j能接受來自國外和國內(nèi)的航班。式(3)保證航班的到達類型與登機口可接受的類型相匹配。

(3) 出發(fā)航班類型約束為

|(T3,i-T4,j)xi,j|≠1

(4)

式中:T3,i表示轉(zhuǎn)場航班i的出發(fā)航班類型;T4,j表示登機口j接受的出發(fā)航班類型。

T3,i=0表示轉(zhuǎn)場航班i目的地為國外,T3,i=1表示轉(zhuǎn)場航班i目的地為國內(nèi);T4,j=0表示登機口j接受發(fā)往國外的航班,T4,j=1表示登機口j接受發(fā)往國內(nèi)的航班,T4,j=3表示登機口j能接受發(fā)往國外和國內(nèi)的航班。式(4)保證航班的出發(fā)類型與登機口可接受的類型相匹配。

(4) 機體類型約束為

(T5,i-T6,j)xi,j≥0

(5)

式中:T5,i表示轉(zhuǎn)場航班i的機體類型;T6,j表示登機口j接受的機體類型。

T5,i=1表示轉(zhuǎn)場航班i為寬體機,T5,i=2表示轉(zhuǎn)場航班i為窄體機;T6,j=1表示登機口j可接受寬體機,T6,j=2表示登機口j可接受窄體機。式(5)保證航班的機體類型與登機口可接受的類型相匹配。

(5) 間隔時間約束

(6)

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

根據(jù)機場運營情況,航班-登機口分配問題在滿足上述約束條件下,需要盡可能地優(yōu)化如下3個目標(biāo),以高效利用機場資源,同時提高換乘旅客的舒適度。由上述定義可知,機場固定登機口數(shù)為N,同時根據(jù)模型假設(shè)可知,臨時停機位對?？康娘w機無約束,因此可以定義所有的臨時停機位為第N+1個登機口,應(yīng)用本文所定義的符號,可建立如下目標(biāo)函數(shù)。

優(yōu)化目標(biāo)1為

(7)

式中:xi,N+1表示航班i分配在臨時停機位的決策變量;J1表示被分配到臨時停機位的飛機數(shù)量,即沒有分配到固定登機口的飛機數(shù)量,該優(yōu)化目標(biāo)為盡可能多地將航班安排至固定登機口。

優(yōu)化目標(biāo)2為

(8)

式中;J2為中轉(zhuǎn)旅客的總體最短流程時間;pl表示第l組中轉(zhuǎn)旅客隨行人數(shù);τl表示第l組中轉(zhuǎn)旅客的最短流程時間,其數(shù)值如表1所示,該優(yōu)化目標(biāo)為最小化中轉(zhuǎn)旅客的總體最短流程時間。

優(yōu)化目標(biāo)3為

(9)

根據(jù)以上3個優(yōu)化目標(biāo)的定義可知,這3個目標(biāo)之間是互相拮抗的,無法同時滿足。目標(biāo)函數(shù)的優(yōu)先級為:盡可能多地將航班安排至固定登機口(minJ1)>最小化中轉(zhuǎn)旅客的總體最短流程時間(minJ2)>最小化被使用登機口的數(shù)量(minJ3),即首先滿足優(yōu)化目標(biāo)1,其次滿足優(yōu)化目標(biāo)2,最后滿足優(yōu)化目標(biāo)3。實現(xiàn)多目標(biāo)優(yōu)化問題求解的第一步是將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題,線性加權(quán)是多目標(biāo)優(yōu)化廣泛使用的一種模型,通過給不同的目標(biāo)函數(shù)制定相應(yīng)的權(quán)重,將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題[21-22]。因此,多目標(biāo)優(yōu)化模型可以寫成如下形式:

minJ=w1·J1+w2·J2+w3·J3

(10)

式中:J表示總體優(yōu)化目標(biāo)綜合效用函數(shù);w1、w2和w3分別表示優(yōu)化目標(biāo)1～3的權(quán)重值,且w1+w2+w3=1,其權(quán)重具體分配一般通過多次實驗確定。

綜上分析,可以建立如下的多目標(biāo)多約束機場登機口優(yōu)化分配模型:

(11)

3 算法設(shè)計

將航班抽象為物體,將航班在機場轉(zhuǎn)場的時間抽象為物體體積,則該問題就轉(zhuǎn)化為典型的背包問題,即如何使用最少的背包裝入最大的價值。求解背包問題有多種算法,比如遺傳算法、貪婪算法、粒子群算法和禁忌搜索算法等[23-25]。貪婪算法以自頂而下的方式進行搜索,在問題求解的每一個階段都做出一個在一定標(biāo)準(zhǔn)下看似最優(yōu)的決策,能快速求得可行解,但通常不是全局最優(yōu)解,是求解最優(yōu)化問題最簡便的方法之一。遺傳算法對登機口分配問題沒有太多的數(shù)學(xué)要求,搜索過程中不需要問題的內(nèi)在性質(zhì),其在犧牲一定時間代價的情形下可以獲得全局最優(yōu)解。傳統(tǒng)遺傳算法的初始種群設(shè)置具有較強的隨機性,其個體適應(yīng)度不高,降低了算法收斂速度。為此,本文借鑒貪婪算法局部尋優(yōu)的特點,設(shè)計貪婪策略,利用貪婪算法得到的航班-登機口分配方案賦值遺傳算法初始種群,并利用遺傳算法求解最優(yōu)航班-登機口分配方案。

3.1 初始種群獲取

貪婪算法的核心是選擇一種適合的貪婪策略[26-27],在航班-登機口優(yōu)化目標(biāo)中,最大化航班靠橋率,即將航班盡可能多地安排至廊橋登機口,符合貪婪算法的基本特性。因此,基于貪婪算法求解初始種群在一定程度上可以提高遺傳算法求解效率,本文選擇如下貪婪策略。

貪婪策略:轉(zhuǎn)場航班依次到達機場,按照“先到先分配”的原則對航班計劃進行排序。對于每個到達航班,優(yōu)先指派航班至空閑時間間隔最小的登機口,具體實現(xiàn)步驟如下。

步驟 1初始化參數(shù)。將航班按照到達時間進行排序,先到達的航班優(yōu)先分配登機口。設(shè)定登機口的空閑時間為上一架飛機的離港時間。

步驟 2求解局部最優(yōu)解。對于每個到達航班,尋找其與登機口空閑時間間隔最小的登機口作為局部最優(yōu)解,若轉(zhuǎn)場航班i占用登機口j,則xi,j=1,否則xi,j=0。

步驟 3若某一轉(zhuǎn)場航班經(jīng)過多次嘗試仍然無法分配到適合的登機口,則將該航班安排至臨時停機位。

步驟 4遍歷待分配航班,為所有計劃內(nèi)的航班分配適合的登機口。

用于生成初始種群的貪婪算法流程圖如圖2所示。

圖2 貪婪算法流程圖

3.2 遺傳算法

根據(jù)上述分析可知,航班-登機口分配問題屬于多目標(biāo)動態(tài)規(guī)劃問題,且含有多個約束條件,是一個典型的NP(nondeterministic polynomially)-hard問題。遺傳算法是一種典型的智能優(yōu)化算法,通過模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程實現(xiàn)模型求解,被廣泛應(yīng)用于求解NP-hard問題[28-29]。針對多目標(biāo)、多約束的航班-登機口分配優(yōu)化問題,本文利用帶精英策略的遺傳算法求解該問題。遺傳算法從一組隨機生成的初始解,也稱為“種群”開始搜索,由上文分析可知,本文利用貪婪算法得到的航班-登機口分配結(jié)果賦值遺傳算法初始種群。染色體是一串符號,這些染色體在后續(xù)迭代中進化就是遺傳,其后代根據(jù)前一代染色體的“交叉”和“變異”運算形成,并且在每一代進化中通過計算個體的適應(yīng)度來評價染色體的“好壞”,算法經(jīng)過若干次迭代后,將收斂于最優(yōu)染色體,即為問題的解。本文采用的遺傳算法中一條染色體表示一個航班-登機口分配方案,每條染色體中包含若干個基因(基因個數(shù)由需要轉(zhuǎn)場的航班對數(shù)量決定),第i個基因表示第i個轉(zhuǎn)場航班對,基因上的數(shù)字表示對應(yīng)航班?？康牡菣C口序號。在該染色體中,每個基因能選擇的登機口序號除簡易臨時機位外,必須滿足對應(yīng)飛機和登機口在機型(寬/窄)、航班到達或出發(fā)類型(國內(nèi)/國外)等約束條件上的完全匹配,染色體示意圖如圖3所示,本文使用帶精英策略的遺傳算法進行求解,算法流程如圖4所示,算法實現(xiàn)過程如算法1所示。

算法 1 遺傳算法(1) Begin(2) t=0;(3) Initialize P(t);(4) Evaluate P(t);(5) While not finished do(6) Begin(7) t←t+1;(8) Genetic operate P(t);(9) Evaluate P(t);(10) End(11) End

圖4 遺傳算法流程圖

算法1中P(t)表示遺傳算法更新第t代種群,結(jié)合圖4和算法1,帶精英策略的遺傳算法具體實施步驟可表述如下。

步驟 1初始化遺傳算法參數(shù)。設(shè)定種群大小為NP,染色體長度即需要轉(zhuǎn)場的航班對數(shù)量為M,最大遺傳代數(shù)為G。

步驟 2根據(jù)飛機轉(zhuǎn)場信息、旅客信息以及機場登機口信息,利用貪婪算法生成遺傳算法初始種群。

步驟 3根據(jù)第2節(jié)建立的登機口分配模型目標(biāo)函數(shù)計算個體適應(yīng)度,并對每代群體按照適應(yīng)度值降序排序,取適應(yīng)度值最大的個體染色體作為精英保留,適應(yīng)度函數(shù)表達式為

(12)

式中:w1取值為0.7;w2取值為0.2;w3取值為0.1;Fit表示登機口優(yōu)化分配適應(yīng)度函數(shù)變量;Fmax為極大的正數(shù)使得Fit恒大于零,并根據(jù)個體適應(yīng)度值分配計算個體被遺傳到下一代群體的概率及其累積概率:

(13)

(14)

式中:ii=1,2,…,NP,fii表示第ii個個體的適應(yīng)度值;pii和qii分別表示第ii個個體被遺傳到下一代群體的概率和累積概率。

步驟 4對染色體進行選擇操作,首先采用輪盤賭算法選擇染色體,若所有的染色體具有相等的適應(yīng)度值,則通過服從均勻分布的隨機數(shù)對染色體進行隨機性選擇。

步驟 5對染色體進行交叉操作,生成兩個隨機正數(shù)t1和t2,將其作為需要截取的染色體片段,并采用雙點雜交策略進行染色體交叉操作,染色體交叉操作過程示意圖如圖5所示。

為了提高遺傳算法收斂速度,在遺傳進化后期引入自適應(yīng)交叉算子,本文在Srinvias等[30]提出的自適應(yīng)遺傳算法基礎(chǔ)上對遺傳算子計算公式進行了改進,使得交叉算子恒大于零,減小遺傳進化走向局部最優(yōu)解的概率,本文提出的改進自適應(yīng)交叉算子計算公式為

(15)

式中:Pc表示交叉算子;fmax表示種群中個體最大適應(yīng)度值;favg表示每一代種群平均適應(yīng)度值;k1>k2,本文通過多次調(diào)整參數(shù)進行實驗,設(shè)置k1為0.7,k2為0.4。

而在遺傳進化初期,為提升種群的多樣性,依然采用較大的固定交叉概率進行算法迭代,因此,設(shè)置交叉算子Pc為常數(shù)0.7。

步驟 6對染色體進行變異操作,生成隨機正數(shù)作為需要變異染色體的基因位置,并將該位置登機口變異為1～N間隨機正整數(shù)。

和自適應(yīng)交叉算子設(shè)置類似,本文提出的改進自適應(yīng)變異算子計算公式為

(16)

式中:Pm表示變異算子;k3>k4,本文通過多次調(diào)整參數(shù)進行實驗,設(shè)置k3為0.1,k4為0.05。在遺傳進化初期,采用較大的固定變異概率進行算法迭代,設(shè)置變異算子Pm為常數(shù)0.1。

步驟 7計算經(jīng)選擇、交叉和變異后的種群個體適應(yīng)度,按照適應(yīng)度值進行降序排序,淘汰適應(yīng)度值最小的個體,并使用上一代精英補充,更新精英個體。

遺傳迭代后期為提高個體間的競爭,本文通過擴大個體適應(yīng)度值的差異程度提高算法最優(yōu)解搜索能力,因此進化后期調(diào)整適應(yīng)度函數(shù)為

(17)

式中:n為大于零的正整數(shù),本文根據(jù)實際數(shù)據(jù)驗證取值為2。

步驟 8重復(fù)執(zhí)行步驟4至步驟7共計G次,獲得最優(yōu)航班-登機口分配結(jié)果,停止演化,取演化最后適應(yīng)度值最高的個體作為最后遺傳算法求得的全局最優(yōu)解。

4 實例驗證及分析

4.1 基于貪婪-遺傳算法的登機口分配結(jié)果

實驗數(shù)據(jù)來源于國內(nèi)某大型樞紐機場,其中航站樓T有28個登機口,衛(wèi)星廳S有41個登機口。登機口的屬性包括:所在終端廳(T/S)、區(qū)域位置(North/Center/South/East)、能接受的航班到達類型(國際I/國內(nèi)D)、能接受的航班出發(fā)類型(國際I/國內(nèi)D)以及能?？匡w機的寬窄類型(寬W/窄N)。登機口屬性不可修改,且只能接受航班到達類型、出發(fā)類型、機體寬窄類型以及適合的轉(zhuǎn)場計劃。根據(jù)統(tǒng)計,當(dāng)天轉(zhuǎn)場航班架次為303次,在該機場共有1 649組中轉(zhuǎn)旅客,飛機轉(zhuǎn)場信息、旅客信息以及登機口信息示例如表2～表4所示。

表2 飛機轉(zhuǎn)場信息

表3 旅客信息

表4 登機口信息

根據(jù)待分配登機口的航班計劃初始化遺傳算法基本參數(shù),其中,種群數(shù)量NP為60,染色體長度M為303,最大遺傳代數(shù)G為600,當(dāng)遺傳代數(shù)大于480時表示遺傳進化進入后期。

編寫航班-登機口分配算法程序進行模型求解,登機口航班占用時間分配如圖6所示,圖7為航站樓T和衛(wèi)星廳S各登機口分配航班數(shù)量及其使用率統(tǒng)計,圖8為中轉(zhuǎn)旅客最短流程時間占比統(tǒng)計。

圖7 各登機口分配航班數(shù)量統(tǒng)計

圖8 中轉(zhuǎn)旅客最短流程時間占比統(tǒng)計

分析圖6～圖8,可以得到以下主要結(jié)論:

(1) 根據(jù)圖6統(tǒng)計可知,本文所提出的算法成功為524架次航班(262架飛機)分配了登機口,占航班總數(shù)的86.47%,共使用了67個登機口,成功分配寬體機航班架次為82,分配成功率為83.67%,成功分配窄體機航班架次為442,分配成功率為87.01%。

(2) 由圖7可以看出,航站樓T共有28個登機口被使用,其平均使用率為61.09%,衛(wèi)星廳S共有39個登機口被使用,其平均使用率為56.22%。由此可知,在20日一天時間內(nèi),航站樓T登機口的平均使用率略高于衛(wèi)星廳S,主要原因是衛(wèi)星廳在一定程度上會增加旅客的換乘時間,從而導(dǎo)致算法在優(yōu)化登機口分配方案時,更傾向于將飛機優(yōu)先安排至航站樓T的登機口。

(3) 由圖8可以看出,中轉(zhuǎn)旅客最短流程時間為20 min的旅客數(shù)占比最大,為20.07%,最短流程時間為45 min的旅客占比相對較小,為11.34%,這說明大部分旅客有充足的時間用來換乘,驗證了模型和方法的有效性。

4.2 登機口指派結(jié)果比較分析

為進一步說明本文基于貪婪-遺傳算法的機場登機口優(yōu)化模型求解方法的有效性,將本文登機口分配方案與采用相同數(shù)據(jù)的航班“先到先分配”隨機指派結(jié)果、基于貪婪算法的登機口指派結(jié)果以及基于禁忌搜索算法[31]的登機口指派結(jié)果進行比較,結(jié)果如表5～表7所示。

表5 中轉(zhuǎn)航班登機口分配結(jié)果對比

表6 航站樓T和衛(wèi)星廳S的登機口使用情況

表7 中轉(zhuǎn)旅客總體最短流程時間統(tǒng)計

由表5～表7可以看出,基于航班計劃,按“先到先分配”隨機指派策略的航班分配成功架次為478,登機口使用數(shù)量為69,其中航站樓T和衛(wèi)星廳S的登機口平均使用率分別為64.76%和46.72%,中轉(zhuǎn)旅客的總體最短流程時間為75 170 min。在貪婪算法實現(xiàn)登機口預(yù)分配結(jié)果基礎(chǔ)上,使用遺傳算法進行迭代優(yōu)化后,成功分配航班架次為524,航班-登機口成功分配率提高了9.62%,登機口使用數(shù)為67個,且登機口平均使用率得到提高,中轉(zhuǎn)旅客總體最短流程時間為63 156 min,相比“先到先分配”隨機指派分配結(jié)果降低了15.98%。進一步對比文獻[31]中基于禁忌搜索算法得到的登機口分配結(jié)果可以看出,本文所提出的登機口分配算法能夠?qū)⒏嗟闹修D(zhuǎn)航班分配至固定登機口,且旅客總體最短流程時間相比禁忌搜索算法降低了2.44%。由此可知,基于貪婪-遺傳算法的登機口優(yōu)化方法能夠有效提高航班-登機口分配成功率,顯著減小中轉(zhuǎn)旅客換乘時間,且登機口的使用效率得到提升,驗證了模型和算法的有效性。

5 結(jié) 論

(1) 本文對具有衛(wèi)星廳的樞紐機場登機口分配問題進行了研究,以提升中轉(zhuǎn)旅客換乘滿意度為優(yōu)化目標(biāo),提出在最大化分配航班至固定登機口的基礎(chǔ)上,最小化中轉(zhuǎn)旅客總體最短流程時間和固定登機口使用數(shù)量,建立了適用于具有衛(wèi)星廳的機場登機口分配優(yōu)化模型。

(2) 設(shè)計了遺傳算法染色體表現(xiàn)形式,給出了基于貪婪-遺傳算法的登機口分配模型求解流程和算法實現(xiàn)過程,并利用帶精英策略的遺傳算法實現(xiàn)登機口優(yōu)化模型求解。

(3) 利用一組實例數(shù)據(jù)對所提出的模型和算法進行了驗證,結(jié)果表明本文提出的航班-登機口分配模型和算法能夠有效為過站航班指派適合的登機口。