李 恒，王 嘉

（長沙航空職業(yè)技術(shù)學院，湖南 長沙 410124）

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

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

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

1 單跑道航班優(yōu)化調(diào)度模型

1.1 目標函數(shù)

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

1.2 符號說明

單跑道航班調(diào)度模型中會使用到大量符號、變量，相關(guān)符號定義如下：

：離港航班集合，

：進港航班集合，

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

STAi：航班的實際進港時刻

ETAi：航班的預計進港時刻

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

STDi：航班的實際離港時刻

ETDi：航班的預計離港時刻

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

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

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

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

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

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

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

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

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

1.3 約束條件

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

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

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

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

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

2 基于改進的狀態(tài)空間模型序號編碼進化算法

2.1 算法簡介

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

2.2 算法的原理

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

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

圖1 МOSEA 算法流程圖

3 單跑道航班進離港優(yōu)化調(diào)度計算步驟

3.1 編碼方式

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

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

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

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

表2 編碼后的航班序列

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

3.2 狀態(tài)進化矩陣的構(gòu)造

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

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

3.3 新種群的產(chǎn)生

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

3.4 適應度函數(shù)的選取

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

3.5 停機條件

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

4 仿真結(jié)果分析

4.1 實驗數(shù)據(jù)與基礎參數(shù)

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

表3 機場初始航班數(shù)據(jù)表

4.2 參數(shù)設置

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

4.3 仿真結(jié)果與分析

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

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

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

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

表4 隨機計算10 次的結(jié)果

4.4 多種算法的比較

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

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

表5 算法各項誤差結(jié)果

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

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

5 結(jié)論

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