基于遺傳算法的進離場流量動態(tài)分配方法研究*

張晉武

（中國人民解放軍91977部隊 北京 100036）

1 引言

近年來，我國經(jīng)濟由高速增長階段轉(zhuǎn)向高質(zhì)量發(fā)展階段，航空運輸業(yè)持續(xù)快速增長，有限的飛行空域內(nèi)流量壓力逐漸增大。直到2020年受到新冠疫情的影響，國內(nèi)外航空運輸市場遭受打擊，總周轉(zhuǎn)量同比下降39.5%，其中中部地區(qū)2020年1月-12月中部地區(qū)民航貨郵吞吐量達到137.18 萬噸，仍保持10.0%的正增長［1］；主要航空公司共執(zhí)行航班241.92萬班次，而由于流量控制造成的航班延誤比例達到11.21%，在造成經(jīng)濟損失的同時，也帶來了一定的安全隱患。

在民航空中交通管制領(lǐng)域，科學(xué)合理的規(guī)劃機場進離場流量分配［2］是眾多國內(nèi)外學(xué)者關(guān)注的研究方向，進離場流量動態(tài)分配作為流量管理的有效手段之一，通過研究進場與離場流量之間的相關(guān)性，在不超出機場容量最大限制的前提下，實現(xiàn)航班進離場需求的二次分配，從而促使機場容量與進離場流量間的協(xié)調(diào)均衡，提高機場資源利用率。

通過相關(guān)文獻查閱，國外研究人員［3］對民用航空機場中的進離場容量曲線開展優(yōu)化研究，采用數(shù)據(jù)統(tǒng)計常用的R 軟件與分位回歸理論相結(jié)合的方式模擬進離場容量變化曲線，基于此，為機場進離場流量調(diào)度分配提供解決方案。

國內(nèi)學(xué)者何沛南［4］針對成都機場容量資源評估需要及流量分配中的問題，進行了機場容量與流量分配協(xié)同優(yōu)化的供需平衡策略研究；楊尚文［5］等針對現(xiàn)有的民航機場容量仿真模擬模型中不確定性強、魯棒性差的問題，進一步優(yōu)化參數(shù)，降低不同仿真場景下延誤等特情事件對進離場流量造成的擾動影響。

總結(jié)分析國內(nèi)外現(xiàn)有的研究成果，針對民航機場進離場流量分配策略問題，僅僅考慮了進場流量與離場流量之間存在的相互影響關(guān)系，但并未將該相關(guān)性因子在模型中量化體現(xiàn)，對多仿真場景下的機場容量動態(tài)調(diào)配方法缺乏深入研究［6］，現(xiàn)行的流量分配策略難以達到相關(guān)管理部門對空中交通流量管制要求［7］。

2 流量動態(tài)分配模型研究

傳統(tǒng)流量分配模型采用RBS 算法與Compression 算法相結(jié)合，對進場、離場時間切片完成相關(guān)數(shù)據(jù)清洗、數(shù)據(jù)預(yù)處理等步驟，實現(xiàn)進離場流量的隊列排序［8］。但該傳統(tǒng)算法模型并未考慮機場容量不同場景以及特情事件造成的不確定性因素，因此提出的動態(tài)流量分配策略并未達到最優(yōu)。

為解決在機場容量不確定條件下，地面等待和空中等待之間的均衡性問題，本節(jié)通過構(gòu)建流量動態(tài)分配模型，將不確定性用容量情景樹模型［9］量化表示，計算以航班預(yù)計總延誤成本為目標函數(shù)的最小解。

將目標場景中進離場流量對應(yīng)的時間序列分割成τ個離散時間切片，并定義τ+1為單獨的時間切片，在τ+1 時間切片中定義機場容量無限大，并用Γ 定義同類相等的離散時間切片總集合。

在流量動態(tài)分配模型中，定義機場因流量分配不適造成的最小延誤成本為目標函數(shù)，其中延誤成本由地面等待成本與空中等待成本兩部分組成。

上式中：F定義為所研究的進離場時間段內(nèi)該航班f集合，f∈F；Fd定義為在目標機場離場的該航班f集合；Fa定義為在目標機場進

場的該航班f集合；S定義為目標機場容量情景s集合，ps定義為機場容量情景s發(fā)生的概率，s∈S；定義為該航班f在地面等待單位時間的延誤成本；定義為該航班f在空中等待單位時間的延誤成本；df定義為該航班f的預(yù)計離場時間；af定義為航班f的計劃進場時間。

決策變量如下所示：

約束條件為

本文中構(gòu)建目標機場進離場流量動態(tài)分配模型計算不同時間段、不同情景下的最優(yōu)抵達進場航班數(shù)量以及最優(yōu)目標機場進離場流量動態(tài)分配策略，步驟依次如下所示。

步驟1：選擇初始參數(shù)，預(yù)設(shè)初始時刻和階段，即t=1、ξ=1。

步驟2：通過歷史數(shù)據(jù)統(tǒng)計，將目標機場對各航班進離場需求和總?cè)萘啃畔⒁郧榫皹湫问胶Y選，選取運籌學(xué)理論算法將選擇不同的分支變量和不確定性因素進行分支，求解不同時間切片內(nèi)在第ξ階段內(nèi)的預(yù)計最優(yōu)抵達目標機場的航班數(shù)量，同時預(yù)估對不同時間切片內(nèi)在第ξ+1 階段內(nèi)累計抵達機場航班數(shù)量。

步驟3：通過決策分析中的情景樹方法對不同航程班次以及目標機場進離場總?cè)萘康倪M行數(shù)據(jù)分析，計算在t 時間切片內(nèi)的最優(yōu)進離場流量動態(tài)分配策略，t=t+1。

步驟4：當計算過程中t=τ時，算法流程跳轉(zhuǎn)至步驟6，否則流程轉(zhuǎn)至步驟5。

步驟5：當目標機場進離場容量場景發(fā)生變化，定義ξ=ξ+1，并同步更新目標機場對各航班進離場需求和總?cè)萘壳榫皹湫畔?，流程跳轉(zhuǎn)至步驟2；相反，各時間切片在t時間內(nèi)，直至第ξ+1 階段記錄抵達目標機場航班數(shù)量保持不變，流程跳轉(zhuǎn)至步驟3。

但流量動態(tài)分配模型需要耗費長時間來求解流量和容量匹配機制，實際運行決策中，更是涉及大規(guī)模的數(shù)據(jù)量，為保證模型求解的時效性，因此選用遺傳算法進行優(yōu)化。

3 基于遺傳算法的模型優(yōu)化

遺傳算法［10］是基于自然群體遺傳進化機制的啟發(fā)式算法，通過模擬生物進化論中自然選擇和自然遺傳過程中的選擇，交叉，突變的基因現(xiàn)象，提供了一種求解組合改進的基礎(chǔ)泛用模型方法［11］。本文充分利用遺傳算法GA在解決動態(tài)組合問題方面的優(yōu)勢［12］，調(diào)整流量動態(tài)分配模型中的決策變量，優(yōu)化實際場景中進離場流量與機場容量間的匹配機制，根據(jù)已有的機場容量情景模型與進離場空域信息，計算航班進場與離場時間片的最優(yōu)解，為機場管理提供動態(tài)分配方案。

3.1 初始編碼

在機場進離場流量的動態(tài)隨機調(diào)配決策方案中，定義決策變量為在不同機場容量場景下各航班的進離場時間序列，通過二進制編碼方法對時間切片進行預(yù)處理。染色體單體集合定義為o(s,f,t)，染色體單體編碼形式如圖1所示。其中q定義為機場在情景s下的總?cè)萘?，m為機場進離場網(wǎng)絡(luò)需求中進場與離場的航班總數(shù)f，n為整個過程所需時間量總和。集合o(s,f,t)定義為當機場容量處于情景s條件下航班總數(shù)f在時間切片t內(nèi)的進離場平衡狀態(tài)。而當o(s,f,t)=1 時，則說明在機場容量情景s條件下，當前航班在時間切片t內(nèi)進場或離場，當o(s,f,t)=0 時，則表示在機場容量情景s條件下，當前航班不在該時間切片t內(nèi)進場或離場。在分配策略中o(s,f,t)的值由系統(tǒng)隨機生成，同時滿足機場容量曲線、容量情景、連續(xù)航班三個必要約束條件。

3.2 遺傳算子

1）選擇

根據(jù)適應(yīng)度函數(shù)計算公式求解種群中各染色體單體的適應(yīng)度值，利用最優(yōu)適應(yīng)度選擇排序方法，將各染色單體按照適應(yīng)度評估結(jié)果依次進行排序；通過比對預(yù)設(shè)的種群淘汰率，篩選適應(yīng)度符合條件的染色單體，最后復(fù)制同比例適應(yīng)度高的染色單體替換淘汰個體，以保證整個迭代過程中種群大小不變。

2）交叉

根據(jù)交叉率將父代染色體中的部分染色單體按照一定概率隨機交換基因生成新的子染色體，本文采用單點交叉方法實現(xiàn)交叉操作。交叉過程示意圖如圖2所示，在規(guī)定時間切片t內(nèi)，隨機選擇某一行位置進行交叉（如圖中加粗黑線的位置所示），將交叉點前后的父染色體1上側(cè)部分與父染色體2上側(cè)部分o(s,f,t)進行交叉對調(diào)，生成兩個新的子染色單體。

圖2 交叉過程示意圖

3）變異

變異操作是通過遺傳算法中染色體單體交叉之后的子代個體，按照一定概率值不定性隨機改變某單體的基因值。在不同機場進離場流量動態(tài)隨機調(diào)配方案中，采用任意將其中兩行進行交換的形式，從而生成新的子代個體，變異的過程示意圖如圖3所示。變異產(chǎn)生的新子代個體校正處理方式與交叉過程保持一致。

圖3 變異過程示意圖

整個變異過程是針對單體中的基因序列上的某個或某類基因值。定義單體變異概率pm=B/(M2·λ1)，上式中參數(shù)B是變異過程中每代發(fā)生變異的基因數(shù)，M2是每代中整個群體的單體數(shù)目，·λ1是參與變異過程中的單體基因串長度。

4 實例及分析

選取國內(nèi)上海虹橋國際機場ZSSS 中八點整至十二點整時間段的目標機場進離場航班動態(tài)數(shù)據(jù)為實驗數(shù)據(jù)，進行仿真驗證。機場ZSSS 的航班需求初始值214架航班，包括進場飛機數(shù)量105架，離場飛機數(shù)量109架。

在開展仿真實驗前，預(yù)設(shè)相關(guān)模型參數(shù)，設(shè)置種群初始數(shù)量為120，最大迭代數(shù)量為240，變異因素為0.1，交叉因子為0.9，淘汰率為0.2；目標機場周轉(zhuǎn)時間每個時間片設(shè)置為15min。

通過多次的仿真模擬發(fā)現(xiàn)，214 架航班調(diào)度，遺傳算法優(yōu)化過程往往在120 代左右完成收斂過程，與傳統(tǒng)分配模型相比，提高了整體收斂速率。如圖4所示。

圖4 遺傳算法進化過程

經(jīng)優(yōu)化求解得到各容量場景下對給定機場流量變化網(wǎng)絡(luò)的進離場流量調(diào)配改進組合方案，最小預(yù)計總延誤成本為1260.9 個單位成本。從圖5、圖6 中可以看出分別為目標機場ZSSS 在九點整陰雨轉(zhuǎn)晴容量場景1與十一點整陰雨轉(zhuǎn)晴容量場景2下的進離場流量動態(tài)分配策略。

圖5 容量場景1下進離場流量分配方案

為驗證基于遺傳算法的進離場流量動態(tài)分配方案的均衡性，將八點至十二點分成四組，通過比對分配方案進離場航班數(shù)與該情景下的機場容量曲線關(guān)系，如下圖所示。可以看出在容量情景1 下的動態(tài)分配點均處于容量曲線區(qū)域內(nèi)部。

圖7 八點至九點進離場流量分配方案

圖8 九點至十點進離場流量分配方案

5 結(jié)語

面向民航空中交通流量科學(xué)管制技術(shù)發(fā)展，本文通過研究進離場流量與機場容量的協(xié)調(diào)匹配機制，提出了一種基于遺傳算法的進離場流量動態(tài)分配研究方法。

考慮不同情景下機場容量的不確定性，并以情景樹模型進行量化，通過計算地面等待成本與空中等待成本的最小值。得到進離場流量動態(tài)分配的最優(yōu)方案。通過上海虹橋機場的實例數(shù)據(jù)，驗證了方法在不同機場容量情景下仍能保持較好的均衡性，同時也可為空管部門今后的最佳優(yōu)化決策提供參考。