胡 杰, 鮑 帆, 石瀟竹

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

0 引 言

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

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

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

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

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

1 問題描述

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

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

表1 最短流程時(shí)間

2 航班-登機(jī)口分配模型

2.1 模型假設(shè)

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

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

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

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

(4) 機(jī)場所有登機(jī)口的功能屬性不能改變,且轉(zhuǎn)場航班只能?？吭谂c之屬性相匹配的登機(jī)口。

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

2.2 模型建立

2.2.1 約束條件

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

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

(1)

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

(1) 唯一性約束為

(2)

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

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

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

(3)

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

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

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

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

(4)

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

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

(4) 機(jī)體類型約束為

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

(5)

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

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

(5) 間隔時(shí)間約束

(6)

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

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

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

(7)

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

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

(8)

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

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

(9)

根據(jù)以上3個(gè)優(yōu)化目標(biāo)的定義可知,這3個(gè)目標(biāo)之間是互相拮抗的,無法同時(shí)滿足。目標(biāo)函數(shù)的優(yōu)先級為:盡可能多地將航班安排至固定登機(jī)口(minJ1)>最小化中轉(zhuǎn)旅客的總體最短流程時(shí)間(minJ2)>最小化被使用登機(jī)口的數(shù)量(minJ3),即首先滿足優(yōu)化目標(biāo)1,其次滿足優(yōu)化目標(biāo)2,最后滿足優(yōu)化目標(biāo)3。實(shí)現(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)重具體分配一般通過多次實(shí)驗(yàn)確定。

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

(11)

3 算法設(shè)計(jì)

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

3.1 初始種群獲取

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

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

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

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

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

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

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

圖2 貪婪算法流程圖

3.2 遺傳算法

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

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

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

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

(12)

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

(13)

(14)

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

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

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

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

(15)

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

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

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

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

(16)

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

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

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

(17)

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

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

4 實(shí)例驗(yàn)證及分析

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

實(shí)驗(yàn)數(shù)據(jù)來源于國內(nèi)某大型樞紐機(jī)場,其中航站樓T有28個(gè)登機(jī)口,衛(wèi)星廳S有41個(gè)登機(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ì)劃。根據(jù)統(tǒng)計(jì),當(dāng)天轉(zhuǎn)場航班架次為303次,在該機(jī)場共有1 649組中轉(zhuǎn)旅客,飛機(jī)轉(zhuǎn)場信息、旅客信息以及登機(jī)口信息示例如表2～表4所示。

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

表3 旅客信息

表4 登機(jī)口信息

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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

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