李恒,李茂軍

(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ā)展需求。因此,針對航班進(jìn)離港優(yōu)化調(diào)度問題,國內(nèi)外許多學(xué)者進(jìn)行了較為深入的研究,他們從航班調(diào)度模型、優(yōu)化目標(biāo)、求解算法等不同的方向優(yōu)化解決問題。

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

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

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

1.1 目標(biāo)函數(shù)

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

(1)

符號說明如下:

L為機(jī)場獨(dú)立平行跑道集合,L={1,2,…,l};

Ss為時(shí)隙集合,S={S1,S2,…,Ss};

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

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

AATmax為進(jìn)港航班的最大提前延誤時(shí)間;

ADTmax為進(jìn)港航班的最大滯后延誤時(shí)間;

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

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

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

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

1.2 約束條件

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

(2)

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

(3)

(4)

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

(5)

(6)

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

∑flti≤r

(7)

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

AATMAX≤STAi-ETAi≤ADTMAX

(8)

DATMAX≤STDi-ETDi≤DDTMAX

(9)

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

2.1 算法簡介

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

2.2 算法原理

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

X(k+1)=GX(k)

(10)

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

(11)

2.3 算法的操作步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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