基于狀態(tài)空間模型序號編碼進化算法的航班優(yōu)化調(diào)度

李恒,李茂軍

(1．長沙理工大學(xué),湖南 長沙 410114;2．長沙航空職業(yè)技術(shù)學(xué)院,湖南 長沙 410124)

隨著我國航空業(yè)的快速發(fā)展,原有的先到先服務(wù)(First Come First Service, FCFS)航班調(diào)度方法[1],已不能滿足現(xiàn)有航班調(diào)度要求和我國航空業(yè)的發(fā)展需求。因此,針對航班進離港優(yōu)化調(diào)度問題,國內(nèi)外許多學(xué)者進行了較為深入的研究,他們從航班調(diào)度模型、優(yōu)化目標、求解算法等不同的方向優(yōu)化解決問題。

Faye[2]采用多項式時間算法與模擬退火法相結(jié)合的方法,求解單跑道航班調(diào)度數(shù)學(xué)模型。Landry等[3]開發(fā)了基于獨立分布式網(wǎng)絡(luò)的航班調(diào)度系統(tǒng),以解決進離港航班調(diào)度問題。徐兆龍[4]等構(gòu)建了多跑道航班多優(yōu)化目標的協(xié)同調(diào)度模型,采用蟻群算法對模型進行求解,能有效緩解終端區(qū)的擁堵問題。王璐等[5]采用遺傳算法對航班著陸調(diào)度模型進行求解,為機場制定航班著陸方案提供依據(jù)。黃濤等[6]建立多跑道進離港航班調(diào)度模型,采用AATC-SR-SA的啟發(fā)式算法進行求解,并給出最優(yōu)的調(diào)度方案。潘賀[7]建立單跑道機場進離港航班調(diào)度模型,結(jié)合航班實際數(shù)據(jù),采用改進的基于免疫球蛋白的人工免疫系統(tǒng)算法進行求解,證明了模型和算法的可行性和魯棒性。雖然上述模型和算法各有所長,但是這些模型多以延誤時間和跑道的吞吐量為目標,對多跑道航班調(diào)度的總延誤損失和航班調(diào)度的公平性研究較少。

基于狀態(tài)空間模型的進化算法(Evolutionary Algorithm Based on State-space Model,SEA)[8]是李茂軍教授提出的一種新穎的進化算法。在電力市場競價[9]、城軌自動運行列車速度優(yōu)化[10]、軌道交通優(yōu)化調(diào)度[11]等實際應(yīng)用問題上取得了良好的效果。雖然SEA能有效解決上述問題,但都是采用實數(shù)編碼,對于采用序號編碼解決組合優(yōu)化問題(如航班優(yōu)化調(diào)度問題[4]、旅行商問題和Flow-shop問題[11]等)研究較少,因此本文提出一種基于狀態(tài)空間模型序號編碼進化算法(Order Coded Evolutionary Algorithm Based on State-space Model,OSEA),并研究其在航班進離港優(yōu)化調(diào)度中的應(yīng)用。仿真實驗表明:這種算法對于解決航班進離港優(yōu)化調(diào)度的航班排序問題是非常有效的。

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

1.1 目標函數(shù)

多跑道航班進離港優(yōu)化調(diào)度是將某一時間窗內(nèi)進離港航班看作一個整體,在確保飛機起降安全的前提下,以航班總延誤損失、跑道容量和飛機最小安全間隔等為約束條件,對進離港航班順序進行統(tǒng)一優(yōu)化排序,使得研究時段內(nèi)機場所有航班總延誤損失最少,機場航班吞吐量最大,屬于多目標的組合優(yōu)化問題[13]。其總延誤損失目標函數(shù)定義如下:

(1)

符號說明如下:

L為機場獨立平行跑道集合,L={1,2,…,l};

Ss為時隙集合,S={S1,S2,…,Ss};

flti為1表示跑道l上有航班降落或起飛;為0表示跑道l上沒有航班降落或起飛;

ssi為1表示時隙ss分配給航班;為0表示時隙ss不分配給航班;

AATmax為進港航班的最大提前延誤時間;

ADTmax為進港航班的最大滯后延誤時間;

DATmax為離港航班的最大提前延誤時間;

DDTmax為離港航班的最大滯后延誤時間;

CM為所有航班的總延誤損失;

δij為連續(xù)兩架進離場航班的最小安全飛行時間間隔;

1.2 約束條件

式(2)為相鄰兩架航班的最小安全飛行間隔約束。

(2)

式(3)、式(4)為進/離港航班起飛/降落時隙資源約束。每一個進/離港航班,只有分配到一個起飛/降落時隙,才允許進/離港降落。

(3)

(4)

式(5)、式(6)為跑道資源約束,表示一條跑道在同一時間內(nèi),最多只能有一架起降航班。

(5)

(6)

式(7)表示任意時刻內(nèi),所有跑道上起降航班數(shù)量小于或等于跑道數(shù)量。

∑flti≤r

(7)

式(8)、式(9)表示進/離港航班不能超過規(guī)定的最大延誤時間。

AATMAX≤STAi-ETAi≤ADTMAX

(8)

DATMAX≤STDi-ETDi≤DDTMAX

(9)

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

2.1 算法簡介

遺傳算法的編碼方式有二進制編碼、實數(shù)編碼和序號編碼等不同方式。但在求解組合優(yōu)化問題(如航班優(yōu)化調(diào)度問題、旅行商問題和Flow-shop問題等)時,采用序號編碼比其他幾種編碼方式更直接、更方便。序號編碼遺傳算法不能采用常規(guī)的交叉算子,因此有學(xué)者提出了針對序號編碼遺傳算法的POX、JOX、SPX[14]等特殊交叉算子,但這些交叉算子操作較難實現(xiàn),因此本文提出一種用于求解組合優(yōu)化問題的基于狀態(tài)空間模型序號編碼進化算法(Order Coded Evolutionary Algorithm Based on State-space Model,OSEA)。此算法采用序號編碼,不使用交叉算子,只使用變異算子,且通過構(gòu)造狀態(tài)進化矩陣等操作來實現(xiàn)變異算子的功能,簡化了遺傳操作,繼承了SEA算法[8]和單親遺傳算法[13]的優(yōu)點。OSEA算法將問題的解答過程表示為離散狀態(tài)空間模型的動力學(xué)過程,突破了遺傳算法的計算模式[15]。

2.2 算法原理

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

X(k+1)=GX(k)

(10)

其中X(k)表示第k代群體,G為狀態(tài)進化矩陣,X(k+1)表示第k+1代群體。X(k)是一個N×M的矩陣,此矩陣的各個行向量表示一個個體,即有N個個體,每一個個體包含M個變量。通過構(gòu)造狀態(tài)進化矩陣G來改變基因的排序,保持群體X(k)的多樣性并不斷地進化,它是一個N×N進化矩陣,矩陣的每一行有且只有一個元素為1,其余為零,其構(gòu)造方式如下:

(11)

2.3 算法的操作步驟

狀態(tài)空間進化算法的操作步驟如下:

Step1:使用序號編碼,隨機生成一組滿足約束條件的初始群體X(0),置k=0;

Step3:根據(jù)式(11)構(gòu)造狀態(tài)進化矩陣G;

Step4:按照式(10)進行迭代計算,生成下一代群體X(k+1),并計算下一代群體X(k+1)中個體的適應(yīng)度值;

Step5:將下一代群體X(k+1)不滿足約束條件的個體,其適應(yīng)度值賦值為零,再把X(k)和滿足約束條件的X(k+1)一起投入選種池;

Step6:根據(jù)適應(yīng)度值大小,按從大到小順序排列,選擇前N個適應(yīng)度值對應(yīng)的個體構(gòu)成下一代群體X(k+1),然后置k=k+1;

Step7:對計算結(jié)果進行判斷是否滿足結(jié)束條件,若滿足結(jié)束條件,則輸出計算結(jié)果;否則,跳轉(zhuǎn)到Step3繼續(xù)循環(huán)。

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

為了驗證OSEA算法的有效性,本文選取我國某大型機場節(jié)假日高峰時段內(nèi)的24架航班進行仿真實驗,并將實驗結(jié)果與FCFS算法進行對比。

在求解航班優(yōu)化調(diào)度數(shù)學(xué)模型的計算中,FCFS算法和OSEA算法種群規(guī)模N=200,最大迭代次數(shù)300次。為測試模型和算法的性能,在仿真實驗中隨機選取10次計算結(jié)果,如表1、表2所示。

表1 FCFS算法隨機計算10次的結(jié)果

表2 OSEA算法隨機計算10次的結(jié)果

從表1、表2可以得出:OSEA算法在65代左右可以得到最優(yōu)解,計算速度比較快,航班最低延誤損失為72774.1元,FCFS算法在170代左右才能得到最優(yōu)解,計算速度較慢,航班最低延誤損失為108427.5元,因此OSEA算法與FCFS算法相比能夠大幅度降低航班的延誤損失,效果更好,收斂速度更快。

用AC%、BC%、CC%分別表示平均值與最小值的誤差、平均值與最大值之間的誤差、最大值與最小值之間的誤差,求出各項誤差結(jié)果,如表3所示。

從表3可以看出,OSEA算法AC%的誤差BC%值很小,CC%的誤差值相對較小,而FCFS算法AC%、BC%、CC%的誤差值普遍較大,說明OSEA算法比FCFS算法的穩(wěn)定性和可靠性更好。因為是求航班總延誤損失最小值,由此可以判斷72774.1元為OSEA算法的最優(yōu)解,得出優(yōu)化后的航班時刻表,并與FCFS優(yōu)化后的航班序列進行比較,如表4所示。

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

表4 FCFS和OSEA算法結(jié)果對比

從表4可以看出,OSEA算法與FCFS算法對比:OSEA算法使得所有航班總延誤損失為72774.1元,而FCFS算法的總延誤損失為108427.5元,優(yōu)化后的航班延誤總延誤損失降低了32.88%,且操作簡單、運算速度更快。

4 結(jié) 論

提出了一種OSEA算法,此算法采用序號編碼方式,不使用交叉算子,通過構(gòu)造狀態(tài)進化矩陣來實現(xiàn)基因換位等遺傳算子功能,簡化了遺傳操作,繼承了SEA算法和單親遺傳算法的優(yōu)點,并將這種算法應(yīng)用于航班進離港優(yōu)化調(diào)度。通過仿真實驗表明,本文所提出的方法在求解航班進離港優(yōu)化調(diào)度方面具有很好的實用性,能夠快速找到問題的最優(yōu)解,減少了算法的運算時間,并且更方便、直接。

本文只給出了一種構(gòu)造狀態(tài)進化矩陣的方法,如何通過構(gòu)造更好的狀態(tài)進化矩陣提高算法的全局收斂性,有待進一步研究。