基于改進的狀態空間模型進化算法的航班優化調度

李 恒，王 嘉

（長沙航空職業技術學院，湖南 長沙 410124）

隨著我國經濟的快速增長，民用航空業得到了迅速發展，使得機場數量、飛機數量和航班數量不斷增加。伴隨著空中交通流量的飛速增長，原有的先到先服務（First Come First Service,FCFS）航班調度方法已不能滿足我國航空業的發展需求，造成很多大型機場在波峰段航班延誤率越來越高，空中交通擁堵現象十分嚴重。因此，針對航班優化調度問題國內外專家、學者進行了較為深入的研究，他們從優化目標、航班優化調度數學模型、求解算法和空中交通流量管理策略等不同的方向優化，以期解決問題。

潘賀采用人工免疫算法，求解航班優化調度問題，實驗結果表明該方法能有效減少進離港航班的延誤時間，證明了算法的可行性和魯棒性[1]。Мahmud 采用花卉授粉算法，求解多跑道協同調度問題，結果表明該方法能減少航班延誤損失，提升多跑道協調運行能力[2]。徐兆龍等采用蟻群算法，對多跑道航班協同調度數學模型進行仿真實驗，證明了該模型和算法的可行性和有效性[3]。李丹程等采用結合免疫算法和模擬退火算法，求解離港航班調度方法，結合國內某機場的實際數據，對算法進行驗證，證明了這兩種算法的可行性和有效性[4]。王東興等把航班著陸調度看作是多目標優化問題，提出了一種吱呀輪SWO( Squeaky-Wheel Optimization)啟發式算法，實驗結果表明該算法能有效求解該問題[5]。SHI 等提出了CGIC 的啟發式算法，將航班調度分解為若干子問題，重新計算了各航班的起降時間，給出了優化的航班序列[6]。雖然上述模型和算法各有所長，但這些模型多是對延誤損失和跑道的吞吐量的航班靜態調度研究，對單跑道航班調度的總延誤時間和航班動態實時調度研究較少。

基于狀態空間模型進化算法( Evolutionary Algorithm based on State-space model，SEA)是李茂軍等提出的一種新穎的進化算法[7]。符宏艷等應用SEA 算法解決電力市場競價問題，實驗結果表明該算法比遺傳算法能更快搜索到最優解[8]。凌哲利用SEA 算法解決軌道交通優化調度問題，通過采用非均勻變異算子的狀態進化矩陣，提高了算法的搜索能力和收斂速度[9]。杜佳佳利用SEA算法解決城軌自動運行列車速度優化問題，并取得了良好的效果[10]。雖然SEA 算法能有效解決上述問題，但都是采用實數編碼，對于采用序號編碼解決組合優化問題（如航班優化調度問題、Flow-shop 問題[11，12]和旅行商問題[13]等）研究較少，因此本文提出一種改進的狀態空間模型序號編碼進化算法(A modified Order coded Evolutionary Algorithm based on State-space Мodel，МOSEA)，并研究其在航班進離港優化調度中的應用。仿真實驗表明：這種算法對于解決航班進離港優化調度的航班排序問題是非常有效的。

1 單跑道航班優化調度模型

1.1 目標函數

單跑道航班進離港調度是將某一時間窗內進離港航班看作一個整體，在確保飛機安全的前提下，以航班延誤時間和最小安全間隔為約束條件，對進離港航班順序進行統一優化排序，使得研究時段內機場所有航班總延誤時間最少，屬于典型的組合優化問題[14]。進離港航班總延誤時間目標函數如式（1）所示，其中為進港航班總延誤時間，為離港航班總延誤時間。

1.2 符號說明

單跑道航班調度模型中會使用到大量符號、變量，相關符號定義如下：

：離港航班集合，

：進港航班集合，

R：平行獨立的機場跑道集合，

STAi：航班的實際進港時刻

ETAi：航班的預計進港時刻

AATmax：航班進離港期間，進港航班允許的最大提前時間

STDi：航班的實際離港時刻

ETDi：航班的預計離港時刻

ADTmax：航班進離港期間，離港航班允許的最大提前時間

DATmax：航班進離港期間，進港航班允許的最大延誤時間

DDTmax：航班進離港期間，離港航班允許的最大延誤時間

：=1，跑道r上有航班進港；=0，跑道r上沒有航班進港

：=1，跑道r上有航班離港；=0，跑道r上沒有航班離港

：表示時隙s分配給進港航班

：表示時隙s分配給離港航班

C：所有航班的總延誤損失

θij：連續兩架航班進離港的最小安全間隔

1.3 約束條件

最小安全間隔約束。為保證飛行安全，在同一跑道起降的飛機，須滿足式（2）相鄰兩架航班的最小安全飛行間隔約束，i和j分別表示前機和后機。

進離港航班起降時隙資源約束。式（3）表示每一個進離港航班只有分配到一個起飛降落時隙，才允許進離港降落或起飛。

機場跑道資源約束。為了保證進離港航班的安全，須滿足式（4），它表示一條跑道在任意時間內，最多只能有一架起降航班。

進離港航班最大提前時間約束。式(5)、式(6)表示航班優化排序后進離港航班不能超過規定的最大提前時間。

進離港航班最大延誤時間約束。式(7)、式(8)表示航班優化排序后進離港航班不能超過規定的最大延誤時間。

2 基于改進的狀態空間模型序號編碼進化算法

2.1 算法簡介

遺傳算法的編碼方式有二進制編碼、實數編碼和序號編碼等不同方式。通過對航班優化調度問題的分析，可知航班優化調度實際是求最優的航班起降序列。若采用二進制編碼，則經過交叉操作后會產生無意義的編碼，造成解碼錯亂。若采用十進制對航班序列號進行編碼，假設有m個航班，則可能產生m!種航班序列，同樣會產生很多無意義的編碼，而且還會增加算法的復雜度和運算量。因此，在求解組合優化問題（如航班優化調度問題、旅行商問題和Flow-shop 問題等）時，采用序號編碼比用其他幾種編碼方式更直接、更方便。序號編碼遺傳算法不能采用常規的交叉算子，因此有學者提出了針對序號編碼遺傳算法的РOX、JOX、SРX 等特殊交叉算子[11]，但這些交叉算子操作較難實現，因此本文提出了一種改進的狀態空間模型序號編碼進化算法(МOSEA)，此算法采用序號編碼，不使用交叉算子，只使用變異算子，且通過構造狀態進化矩陣等操作來實現變異算子的功能，簡化了遺傳操作,繼承了SEA算法和單親遺傳算法的優點[15]。

2.2 算法的原理

МOSEA 算法采用序號編碼方式，不使用交叉算子，通過構造狀態進化矩陣來實現基因換位等遺傳算子功能，使種群不斷地進化，并結合選種池的選擇操作實現種群的優勝劣汰。狀態空間模型序號編碼進化算法表示為離散系統的狀態空間模型：

其中X(k)表示第k代群體，G為狀態進化矩陣，X'(k+1)表示第k+1 代群體。X(k)是一個N×M的矩陣，此矩陣的各個行向量表示一個個體，即有N個個體，每一個個體包含M個變量。通過進化算法群體中個體之間的信息交換策略來構建狀態進化矩陣，并通過構造狀態進化矩陣G來改變基因的排序，實現變異算子的功能，保持群體X(k)的多樣性并不斷地進化。根據離散系統理論，在構造矩陣G時應注意是收斂矩陣或保證矩陣G的特征值在Z平面的單位圓內，否則算法會不收斂。算法步驟：首先是使用序號編碼隨機生成一組滿足約束條件的初始群體X(0)，其次構造狀態進化矩陣G，按照式（9）進行計算，并左乘矩陣G得到群體X'(1)，將X'(1)中不滿足約束條件的個體，其適應度賦值為0，之后重新隨機生成G，再按照式（9）進行迭代，產生一系列的X'(1)，X'(2)，X'(3)……把X(k)和滿足約束條件的X'(k+1)一起投入選種池，按照優勝劣汰原則，根據適應度值大小，按從大到小的順序排列，選擇前N個適應度值對應的個體構成下一代群體X(k+1)，對計算結果進行判斷，如果滿足結束條件，則輸出計算結果?；跔顟B空間模型序號編碼進化算法的閉環模型流程圖如圖1 所示。

圖1 МOSEA 算法流程圖

3 單跑道航班進離港優化調度計算步驟

3.1 編碼方式

單跑道航班進離港優化調度屬于典型的組合優化問題，求解組合優化問題時，采用序號編碼比用二進制編碼和實數編碼等方式更直接、更方便。МOSEA 算法通過構造狀態進化矩陣G來實現基因換位等遺傳算子功能，使群體不斷地進化和保持多樣性，并結合選種池的選擇操作實現種群的優勝劣汰。具體編碼方法如下：

假設X(k)為某一航班序列，其初始航班序列xT(0)={1,2,3,4}，狀態進化矩陣再進行X'(k+1)=GX(k)的計算，得到新的航班序列xT(1)={2,1,3,4}，將xT(1)中不滿足約束條件的個體，其適應度賦值為0，按照優勝劣汰、適者生存的進化原則選出優秀個體，形成下一代群體序列，之后重新隨機生成再進行X'(k+1)=GX(k)計算，得到另一個新的航班序列xT(2)={2,3,1,4}，并依次迭代。

若以10 個航班為例，編碼前的初始航班序列如表1 所示，編碼后的航班序列如表2 所示。

表1 編碼前的初始航班序列

表2 編碼后的航班序列

使用上述編碼能夠確保任意航班序列都對應于一條具有實際意義的航班起降序列，從而有效避免了無效航班序列的產生。此外該編碼方式還具有操作簡單、無需解碼等優點。

3.2 狀態進化矩陣的構造

МOSEA 算法的核心是狀態進化矩陣，可以通過不同方法來構造狀態進化矩陣G。不同的構造方法，算法的求解問題不一樣，其搜索速度和效率等性能也有很大影響。比如SEA 算法采用實數編碼，通過模擬遺傳算法的交叉和變異算子功能來構造狀態進化矩陣G，主要用于求解約束優化問題；又如МOSEA 算法采用序號編碼，不使用交叉算子，通過模擬遺傳算法的變異算子功能來構造狀態進化矩陣G，主要用于求解組合優化問題。

МOSEA 算法狀態進化矩陣構造方式如式（10）所示，它是一個N×N進化矩陣，矩陣的每一行、每一列有且只有一個元素為1，其余為0。

3.3 新種群的產生

使用序號編碼隨機生成一組滿足約束條件的初始群體X(0)，按照離散狀態空間模型X'(k+1)=GX(k)進行迭代計算，生成下一代群體X'(k+1)，并計算下一代群體X'(k+1)中個體的適應度值，將下一代群體X'(k+1)中不滿足約束條件的個體，其適應度賦值為0，再把X(k)和滿足約束條件的X'(k+1)一起投入選種池。

3.4 適應度函數的選取

根據目標函數設計算法的適應度函數，從而對群體中的個體進行優勝劣汰。在МOSEA 算法中，適應度函數是衡量個體性能的重要指標，也是算法迭代運行的不竭動力。單跑道航班進離港優化調度是求解目標函數的最小值問題，其求解的值越小，越接近最優個體，表示個體的適應度能力越強，參與到下一次迭代的概率非常大，其適應度函數選取如式（1）所示。

3.5 停機條件

МOSEA 算法以在迭代過程中連續幾代輸出的平均適應度值和最佳適應度值不變或者小于某個極小閾值，來作為算法結束的判定條件。若連續迭代次數超過設定的最大迭代次數都沒有找到最優解，則停止搜索，輸出最終解。

4 仿真結果分析

4.1 實驗數據與基礎參數

為了驗證算法和模型的優劣性，本文選取湖南某單跑道機場，節假日高峰時段內的14 個航班進行仿真實驗，其中進港航班7 個，離港航班7 個。具體航班數據如表3 所示。

表3 機場初始航班數據表

4.2 參數設置

單跑道進離港優化調度模型分別采用FCFS算法、遺傳算法和МOSEA 算法進行仿真實驗。FCFS 算法的種群規模為100，最大迭代次數為300 次；遺傳算法的交叉概率Pc=0.9，變異概率Pm=0.05，種群規模為100，最大迭代次數為300 次；МOSEA 算法產生一個種群規模N=100 的初始群體，最大迭代次數為300 次。

4.3 仿真結果與分析

通過МATLAВ 2020 仿真軟件，對表3 中的初始航班數據分別采用FCFS 算法、遺傳算法和МOSEA 算法對單跑道航班進離港調度模型進行求解，得到優化后的航班序列。FCFS 算法、遺傳算法和МOSEA 算法運行得到的迭代進化曲線對比如圖2 所示。

圖2 三種算法迭代進化曲線對比圖

從圖2可以看出，МOSEA算法收斂速度最快，最終收斂時的迭代次數為71 次，目標函數值最優解更小，得到航班總延誤時間為6 410 s。

為測試模型和算法的性能，在仿真實驗中隨機選取計算10 次的結果，如表4 所示。

表4 隨機計算10 次的結果

4.4 多種算法的比較

從圖2 及表4 可以得出：МOSEA 算法在71代左右可以得到最優解，計算速度快，航班最低延誤時間為6 404.2 s；遺傳算法在104 代左右得到最優解，計算速度較快，航班最低延誤時間為8 224.1 s，FCFS 算法在152 代左右才能得到最優解，計算速度慢，航班最低延誤時間為9 426.4 s。因此，與遺傳算法、FCFS 算法相比，МOSEA 算法能夠大幅度降低航班的延誤時間，效率更高，運算速度更快。

用A、B、C分別表示平均值與最小值之間的誤差、平均值與最大值之間的誤差、最大值與最小值之間的誤差，求出各項誤差的結果，如表5所示。

表5 算法各項誤差結果

從表5可以看出，МOSEA算法的誤差值很小，遺傳算法的誤差值較小，而FCFS 算法的各項誤差值普遍較大，說明МOSEA 算法比遺傳算法、FCFS 算法的穩定性和可靠性更好。因為是求航班總延誤時間的最小值，由此可以判斷6 404.2 s 為最優解，得出優化后的航班時刻表，并與初始航班序列進行對比，如表6 所示。

通過FCFS 算法、遺傳算法和МOSEA 算法對單跑道航班進離港調度模型進行求解，得到優化后的航班序列，并與初始航班序列進行比較。由表6 的數據可以看出，與FCFS 算法相比，МOSEA 算法優化后的航班總延誤時間降低了32.06%；與遺傳算法對比，МOSEA 算法優化后的航班總延誤時間降低了22.13%。實驗數據表明，МOSEA 算法用于求解單跑道航班進離港優化調度模型，能夠大幅降低航班總延誤時間，證明了模型和算法的有效性。

5 結論

本文提出了一種改進的狀態空間模型序號編碼進化算法（МOSEA），此算法采用序號編碼，不使用交叉算子，只使用變異算子，通過構造狀態進化矩陣等操作來實現變異算子的功能，并結合選種池的選擇操作實現種群的優勝劣汰，簡化了遺傳操作,并研究了其在航班進離港優化調度中的應用。通過МATLAВ 2020 仿真平臺，分別采用FCFS 算法、遺傳算法和МOSEA 算法對單跑道進離港航班調度進行仿真實驗，實驗結果表明，МOSEA 算法優化后的航班序列能夠有效降低航班總延誤時間，且操作簡單、收斂速度更快。