基于沖突避免的離場調(diào)度優(yōu)化算法

徐 磊，胡明華,謝 華,王 也

(1.國家飛行流量管理技術(shù)重點(diǎn)實(shí)驗(yàn)室，南京 211106；2.南京航空航天大學(xué) 民航學(xué)院，南京 211106)

我國航空業(yè)持續(xù)蓬勃的發(fā)展使機(jī)場系統(tǒng)面臨運(yùn)行與管制的壓力.而離場航班調(diào)度優(yōu)化問題作為機(jī)場流量管理的重要組成部分，是近年來各國學(xué)者研究的熱點(diǎn).針對(duì)離場排序目前主流的算法包括先到先服務(wù)(FCFS)算法[1]、帶有位置約束轉(zhuǎn)移的算法[2]和動(dòng)態(tài)規(guī)劃法[3]等.

國內(nèi)外對(duì)于離場航班調(diào)度優(yōu)化展開了廣泛深入的研究，Montoya[4]等人以航班延誤最小和增加跑道容量作為多目標(biāo)優(yōu)化問題，使用多目標(biāo)動(dòng)態(tài)規(guī)劃方法進(jìn)行建模并設(shè)計(jì)算法求解了帕累托前沿解集，最后在達(dá)拉斯國際機(jī)場驗(yàn)證了模型效果.Sama M[5]等人將終端區(qū)進(jìn)場航班調(diào)度問題和航空器軌跡優(yōu)化問題結(jié)合在一起并采用字典式優(yōu)化框架，其中航班調(diào)度問題以總航班延誤最小為目標(biāo)而軌跡優(yōu)化以飛行時(shí)間和油耗最小為目標(biāo)函數(shù).2012年，張啟錢，胡明華[6]將航班總延誤最小設(shè)為目標(biāo)函數(shù)，以最大位置偏移為約束建立多跑道進(jìn)離場航班排序模型，并采取滾動(dòng)時(shí)域結(jié)合遺傳算法的方式對(duì)模型求解，最后以白云機(jī)場30條仿真數(shù)據(jù)作驗(yàn)證，結(jié)果相較于FCFS延誤大幅下降.周姝媛，羅軍[7]在機(jī)場約束條件的基礎(chǔ)上建立了航班協(xié)同模型，并以成都終端區(qū)為實(shí)例，結(jié)合具體的航班時(shí)刻表進(jìn)行預(yù)測，并將最后結(jié)果與FCFS作比較.在離場航班優(yōu)化調(diào)度中，目前對(duì)于多跑道機(jī)場的航空器離場問題方面的研究較為欠缺，在實(shí)際運(yùn)行中，管制員通常采用FCFS算法進(jìn)行調(diào)度.然而FCFS算法在很大程度上依賴管制員的經(jīng)驗(yàn)，導(dǎo)致平均延誤時(shí)間較長，降低了安全和效率.

該本文針對(duì)多跑道機(jī)場，結(jié)合跑道分配[8]和航班排序，建立了以航班總延誤最少為目標(biāo)函數(shù)的優(yōu)化模型.模型使用遺傳算法進(jìn)行求解，并將所得優(yōu)化結(jié)果與FCFS方式作對(duì)比，結(jié)果表明所用算法明顯優(yōu)于FCFS算法.

1 模型建立

1.1 機(jī)場節(jié)點(diǎn)-邊網(wǎng)絡(luò)模型

機(jī)場的場面結(jié)構(gòu)網(wǎng)絡(luò)可以表示為一個(gè)有向圖G=(V，E)[9]，其中V與E分別代表機(jī)場各路段節(jié)點(diǎn)與滑行路徑的集合.機(jī)場結(jié)構(gòu)示意圖見圖1.

圖1 機(jī)場結(jié)構(gòu)示意圖

1.2 參數(shù)和變量

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

本文以離場航班總延誤最小為目標(biāo)函數(shù)，航班總延誤可由所有離場航班的實(shí)際起飛時(shí)間與預(yù)計(jì)起飛時(shí)間的差值求和得到.

(1)

其中：k表示航空器號(hào)，r表示跑道號(hào)，AT表示離場航班實(shí)際起飛時(shí)間，ET表示預(yù)計(jì)起飛時(shí)間.

1.4 約束條件

(2)

(3)

tATk-tATj≥Sjkyjk,

(j,k=1,2,…,N,j=k-1)

(4)

tATk≥tETk,(k=1,2,…,N)

(5)

tATk-tETk≤Tdmax,(k=1,2,…,N)

(6)

式(2)表示任意一架航班k只能從一條跑道起飛；式(3)表示在跑道端排隊(duì)的航空器數(shù)量不能超過在該段時(shí)間的跑道容量；式(4)表示以航班的尾流間隔為約束，場面上連續(xù)兩架航班j、航班k在同一條跑道起飛的間隔應(yīng)不小于Sik.對(duì)于Sik，采用國際民航組織規(guī)定的最小尾流間隔標(biāo)準(zhǔn).式(5)表示任意一架航班k不能在規(guī)定的預(yù)計(jì)起飛時(shí)間前起飛.式(6)表示任意一架航班延誤時(shí)間不能超過極限值.

2 基于遺傳算法的算法設(shè)計(jì)

2.1 算法優(yōu)化步驟

由于上述模型是典型的NP-Hard[10]問題，伴隨著問題規(guī)模的增加，用一般線性整數(shù)規(guī)劃[11]進(jìn)行精確求解難度較大且速度較慢，為了在較短時(shí)間內(nèi)能得到一個(gè)實(shí)用性高的解，本文在這里選用遺傳算法[12](Genetic Algorithm, GA)進(jìn)行求解.遺傳算法雖然不一定能在最短時(shí)間內(nèi)求出一個(gè)全局最優(yōu)解，但是可以在較短時(shí)間內(nèi)獲得一個(gè)實(shí)用性較強(qiáng)的局部最優(yōu)解.

根據(jù)調(diào)度優(yōu)化模型的建立思路，設(shè)計(jì)如下推出時(shí)刻優(yōu)化步驟：

1)根據(jù)離場航班數(shù)據(jù)以及FCFS原則求出航班推出時(shí)刻參考值序列.根據(jù)離場航班的預(yù)計(jì)起飛時(shí)間與無沖突滑行時(shí)間，按照FCFS原則對(duì)離場航班進(jìn)行排序并計(jì)算出每架航班的推出時(shí)刻及航班總的延誤時(shí)間；

2)根據(jù)航班數(shù)據(jù)得出所有航班的最小安全時(shí)間間隔矩陣；

3)根據(jù)計(jì)算得出的最小時(shí)間間隔矩陣?yán)眠z傳算法求出離場航班最優(yōu)序列AR1；

4)依據(jù)每架航班的無沖突滑行時(shí)間，求得所有航班的滑行時(shí)間數(shù)組，以步驟3)得出的序列AR1為基礎(chǔ)，計(jì)算得到每架航班的推出時(shí)刻，如果發(fā)生多架離場航班推出時(shí)刻相同的情況時(shí)，則將優(yōu)先級(jí)較低的航班延誤到下一時(shí)刻，這時(shí)可得最優(yōu)的航班推出序列AR2.

2.2 遺傳算子與參數(shù)調(diào)整

1)由于算法既要對(duì)離場航班進(jìn)行排序又要對(duì)跑道進(jìn)行分配，因此在編碼方法上采取雙層編碼[13]的方式.上層采用實(shí)數(shù)編碼，表示航班的起飛順序；下層采用二進(jìn)制編碼，表示每架離場航班對(duì)應(yīng)的跑道.編碼示意圖如圖2所示

圖2 航班編碼示意圖

2)初始化：本文采取隨機(jī)生成一系列1～N的離場航班序列組成可行解，重復(fù)這一過程P次則生成數(shù)量為P的初始種群，本文將初始種群數(shù)量設(shè)為10.

3)選擇：對(duì)種群中的個(gè)體采取輪盤賭的方式進(jìn)行選擇，按這種方式進(jìn)行選擇時(shí)個(gè)體被選中的概率與其適應(yīng)度函數(shù)成比例.因此適應(yīng)度最高的個(gè)體最有可能被選中進(jìn)行重組.同時(shí)采取最優(yōu)保存策略，在每一代種群中，適應(yīng)度在前20%的個(gè)體會(huì)被保留而剩下則會(huì)被新一代個(gè)體取代.

4)交叉：本文采取單點(diǎn)交叉的方式，隨機(jī)選取截?cái)帱c(diǎn)切割再組合并且按照交叉概率Pc確定交叉位置，在本文中交叉概率設(shè)置為0.8.

5)變異：變異概率通常會(huì)被設(shè)置的較低，一般在0.005～0.1之間.變異概率不能設(shè)置的過高因?yàn)楹芨叩淖儺惛怕蔖m會(huì)導(dǎo)致算法擴(kuò)展搜索空間而使收斂時(shí)間變長.因此在本文中變異概率設(shè)置為0.1，且由于離場航班是用實(shí)數(shù)進(jìn)行編碼，因而在本文中采取實(shí)值變異的方式進(jìn)行.為了保證解的可行性，當(dāng)變異發(fā)生時(shí)將變異的兩個(gè)位置的基因進(jìn)行對(duì)調(diào).

6)適應(yīng)度函數(shù)：本文取目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，具體表示如下：

(7)

式(7)表明離場航班在地面的總延誤時(shí)間越短時(shí)適應(yīng)度值越高.在多次迭代期間適應(yīng)度值決定了種群可行解的性能.

3 算例仿真

本文選取南京路口機(jī)場的部分航班仿真數(shù)據(jù)在Matlab上進(jìn)行仿真以驗(yàn)證模型的正確性.祿口機(jī)場為雙跑道，因此將跑道的容量值設(shè)為13，選取4月份某日10∶00～10∶20共計(jì)20 min內(nèi)20架離場航班數(shù)據(jù)作為樣本仿真，主要包括每架航班的機(jī)型以及航班時(shí)刻信息包括預(yù)計(jì)起飛時(shí)間、無沖突滑行時(shí)間、航班號(hào)、跑道號(hào)等.依據(jù)ICAO規(guī)定可得知航空器按照不同的機(jī)型可以分為輕型(L)、中型(M)、重型三類(H)，任意兩種類型航空器的最小尾流間隔標(biāo)準(zhǔn)矩陣Sjk[14]可表示如下：

(8)

其中：前后機(jī)分別為j,k，單位為 min.

航班的無沖突滑行時(shí)間通過離場航班從停機(jī)位到跑道的距離與滑行速度計(jì)算獲得.按照相關(guān)管理[15]規(guī)定，航空器的滑行速度不得小于2.78 m·s-1，不得超過13.9 m·s-1.本文取其平均值，即8 m·s-1.

離場航班信息如表1所示.

表1 離場航班信息

根據(jù)FCFS法則，先到跑道端的航班優(yōu)先起飛，后續(xù)飛機(jī)按照優(yōu)先級(jí)原則依次排隊(duì)，如果后續(xù)航班預(yù)計(jì)起飛時(shí)間不滿足尾流間隔則對(duì)起飛時(shí)間進(jìn)行相應(yīng)延誤，最后再依據(jù)無沖突滑行時(shí)間計(jì)算出航班推出時(shí)刻.結(jié)果如表2所示.

表2結(jié)果表明利用FCFS方法對(duì)求各航班離場推出時(shí)刻，產(chǎn)生的航班延誤總時(shí)間為36 min.根據(jù)表中結(jié)果能夠看出當(dāng)離場航班以FCFS原則排序時(shí)，當(dāng)某一架航班出現(xiàn)延誤時(shí)，后續(xù)航班受前面航班的影響也會(huì)出現(xiàn)相應(yīng)延誤，延誤累計(jì)也會(huì)伴隨航班量增加而增加.與此相對(duì)的按照本文中的遺傳算法求解時(shí)，求得的仿真結(jié)果如表3所示.

表2 采用FCFS所得推出時(shí)刻表

表3結(jié)果表明利遺傳算法求出各航班離場推出時(shí)刻，產(chǎn)生的航班總延誤時(shí)間為23 min，相較于FCFS算法求得的總延誤時(shí)間少13 min，同比減少了約36%，且并不會(huì)產(chǎn)生延誤累積的情況.此外，由于算法在對(duì)推出時(shí)刻優(yōu)化的同時(shí)對(duì)跑道也做出了分配，航班的滑行路徑會(huì)有所不同，航班的無沖突滑行時(shí)間也會(huì)隨之變化.針對(duì)本問題利用啟發(fā)式算法很好的優(yōu)化了航班推出時(shí)刻，提高了離場航班的準(zhǔn)點(diǎn)率，為推出航班排序提供了更加可靠的依據(jù).

表3 采用遺傳算法所得推出時(shí)刻表

采用FCFS排序與遺傳算法排序時(shí)結(jié)果對(duì)比圖如圖3所示.

圖3 FCFS與遺傳算法對(duì)比圖

由圖3結(jié)果可以得知遺傳算法相對(duì)于FCFS算法不僅在推出時(shí)刻上進(jìn)行了優(yōu)化，同時(shí)對(duì)起飛跑道也做出了合理的分配，在減少了航班延誤時(shí)間的同時(shí)增加了起飛跑道的利用率.

4 結(jié) 語

本文研究了多跑道機(jī)場的離場航班調(diào)度問題，在考慮離場航班排序和跑道分配的條件下建立了以航班總延誤時(shí)間最小為目標(biāo)的優(yōu)化模型，采用遺傳算法對(duì)模型進(jìn)行求解并將最終結(jié)果與FCFS算法作比較，發(fā)現(xiàn)了使用遺傳算法求解得到的航班總延誤明顯減少，且跑道分配更加合理，提高了場面運(yùn)行效率.