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

胡 杰, 鮑 帆, 石瀟竹

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

0 引 言

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

機場航班-登機口分配屬于運籌學多目標優化問題,其求解目標函數由機場決策者根據運營情況決定。國內外學者從乘客和機場運營兩個層面建立并求解了諸多登機口分配優化模型。

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

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

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

1 問題描述

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

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

表1 最短流程時間

2 航班-登機口分配模型

2.1 模型假設

為構建機場登機口多目標優化模型,航班-登機口的分配需要考慮如下規則。

(1) 機場臨時停機位數量滿足該時段內所有未分配到固定登機口的航班?？?且對停靠的飛機無約束。

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

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

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

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

2.2 模型建立

2.2.1 約束條件

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

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

(1)

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

(1) 唯一性約束為

(2)

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

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

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

(3)

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

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

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

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

(4)

式中:T3,i表示轉場航班i的出發航班類型;T4,j表示登機口j接受的出發航班類型。

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

(4) 機體類型約束為

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

(5)

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

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

(5) 間隔時間約束

(6)

2.2.2 目標函數

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

優化目標1為

(7)

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

優化目標2為

(8)

式中;J2為中轉旅客的總體最短流程時間;pl表示第l組中轉旅客隨行人數;τl表示第l組中轉旅客的最短流程時間,其數值如表1所示,該優化目標為最小化中轉旅客的總體最短流程時間。

優化目標3為

(9)

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

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

(10)

式中:J表示總體優化目標綜合效用函數;w1、w2和w3分別表示優化目標1～3的權重值,且w1+w2+w3=1,其權重具體分配一般通過多次實驗確定。

綜上分析,可以建立如下的多目標多約束機場登機口優化分配模型:

(11)

3 算法設計

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

3.1 初始種群獲取

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

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

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

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

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

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

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

圖2 貪婪算法流程圖

3.2 遺傳算法

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

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

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

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

(12)

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

(13)

(14)

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

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

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

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

(15)

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

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

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

和自適應交叉算子設置類似,本文提出的改進自適應變異算子計算公式為

(16)

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

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

遺傳迭代后期為提高個體間的競爭,本文通過擴大個體適應度值的差異程度提高算法最優解搜索能力,因此進化后期調整適應度函數為

(17)

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

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

4 實例驗證及分析

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

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

表2 飛機轉場信息

表3 旅客信息

表4 登機口信息

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

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

圖7 各登機口分配航班數量統計

圖8 中轉旅客最短流程時間占比統計

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

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

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

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

4.2 登機口指派結果比較分析

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

表5 中轉航班登機口分配結果對比

表6 航站樓T和衛星廳S的登機口使用情況

表7 中轉旅客總體最短流程時間統計

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

5 結 論

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

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

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