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

張晉武

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

1 引言

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

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

通過相關文獻查閱，國外研究人員［3］對民用航空機場中的進離場容量曲線開展優化研究，采用數據統計常用的R 軟件與分位回歸理論相結合的方式模擬進離場容量變化曲線，基于此，為機場進離場流量調度分配提供解決方案。

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

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

2 流量動態分配模型研究

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

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

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

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

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

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

決策變量如下所示：

約束條件為

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

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

步驟2：通過歷史數據統計，將目標機場對各航班進離場需求和總容量信息以情景樹形式篩選，選取運籌學理論算法將選擇不同的分支變量和不確定性因素進行分支，求解不同時間切片內在第ξ階段內的預計最優抵達目標機場的航班數量，同時預估對不同時間切片內在第ξ+1 階段內累計抵達機場航班數量。

步驟3：通過決策分析中的情景樹方法對不同航程班次以及目標機場進離場總容量的進行數據分析，計算在t 時間切片內的最優進離場流量動態分配策略，t=t+1。

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

步驟5：當目標機場進離場容量場景發生變化，定義ξ=ξ+1，并同步更新目標機場對各航班進離場需求和總容量情景樹信息，流程跳轉至步驟2；相反，各時間切片在t時間內，直至第ξ+1 階段記錄抵達目標機場航班數量保持不變，流程跳轉至步驟3。

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

3 基于遺傳算法的模型優化

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

3.1 初始編碼

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

3.2 遺傳算子

1）選擇

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

2）交叉

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

圖2 交叉過程示意圖

3）變異

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

圖3 變異過程示意圖

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

4 實例及分析

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

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

通過多次的仿真模擬發現，214 架航班調度，遺傳算法優化過程往往在120 代左右完成收斂過程，與傳統分配模型相比，提高了整體收斂速率。如圖4所示。

圖4 遺傳算法進化過程

經優化求解得到各容量場景下對給定機場流量變化網絡的進離場流量調配改進組合方案，最小預計總延誤成本為1260.9 個單位成本。從圖5、圖6 中可以看出分別為目標機場ZSSS 在九點整陰雨轉晴容量場景1與十一點整陰雨轉晴容量場景2下的進離場流量動態分配策略。

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

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

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

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

5 結語

面向民航空中交通流量科學管制技術發展，本文通過研究進離場流量與機場容量的協調匹配機制，提出了一種基于遺傳算法的進離場流量動態分配研究方法。

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