王大軍

(蘭州中川國(guó)際機(jī)場(chǎng)有限公司運(yùn)行指揮中心, 蘭州 730000)

現(xiàn)有的航班時(shí)刻安排往往只考慮一個(gè)小時(shí)內(nèi)的航班量,而忽視了機(jī)場(chǎng)實(shí)際運(yùn)行能力的多樣性。因此現(xiàn)有的大多數(shù)航班時(shí)刻管理一般針對(duì)某一個(gè)整點(diǎn)小時(shí)內(nèi)的航班容量進(jìn)行約束,容易造成因航班時(shí)刻安排不均勻引起的某時(shí)間內(nèi)航班密集,增加管制員的壓力。例如,某機(jī)場(chǎng)在09:00—10:00的容量為28架次,但是在這個(gè)小時(shí)內(nèi),航班分布可能并不均勻?？赡芮鞍胄r(shí)只有2架次的航班,而后半小時(shí)有26架次的航班量。雖然總航班數(shù)沒(méi)有超過(guò)機(jī)場(chǎng)一個(gè)小時(shí)的運(yùn)行容量,但這種安排明顯不符合機(jī)場(chǎng)的實(shí)際運(yùn)行能力,可能導(dǎo)致?lián)矶潞托实拖?。因此航班時(shí)刻的合理安排對(duì)于提高機(jī)場(chǎng)運(yùn)行效率、降低空中和地面擁堵、保障航班安全具有重要意義。

從19世紀(jì)末開(kāi)始,國(guó)內(nèi)外學(xué)者就該問(wèn)題展開(kāi)研究。1993年,Abela等[1]引入人工智能算法,將航班排序與時(shí)刻問(wèn)題視為0～1混合整數(shù)規(guī)劃問(wèn)題,并通過(guò)對(duì)20個(gè)架次的航空器數(shù)據(jù)進(jìn)行驗(yàn)證。2006年,Aditya和Slater[2]提出了一種組合優(yōu)化方法,用于改善進(jìn)場(chǎng)航班時(shí)刻。2018年,Benlic[3]為了合理分配每個(gè)機(jī)場(chǎng)在機(jī)場(chǎng)網(wǎng)絡(luò)中的航班時(shí)刻,開(kāi)發(fā)了一種啟發(fā)式算法,并通過(guò)不斷迭代來(lái)優(yōu)化航班時(shí)刻的分配結(jié)果。同時(shí),國(guó)內(nèi)學(xué)者也進(jìn)行了相關(guān)研究,陳霞和陳浩文[4]基于單親遺傳算法(patheno-gentic algorithm,PGA)建立了以最小化航班延誤總時(shí)間為目標(biāo)的進(jìn)場(chǎng)航班時(shí)刻優(yōu)化模型,通過(guò)仿真計(jì)算驗(yàn)證其在延誤時(shí)間方面遠(yuǎn)優(yōu)于先到先服務(wù)。陳肯等[5]針對(duì)繁忙機(jī)場(chǎng)高峰時(shí)段的資源限制和不合理航班計(jì)劃,引入基尼系數(shù)定義公平性,建立了航班時(shí)刻調(diào)整總量最小和各航空公司公平性最優(yōu)的雙目標(biāo)優(yōu)化數(shù)學(xué)模型。左杰俊等[6]考慮實(shí)際放行能力和航班調(diào)度難度,利用遺傳算法建立了離場(chǎng)航班優(yōu)化調(diào)度模型,并在上海虹橋國(guó)際機(jī)場(chǎng)驗(yàn)證。曾偉華等[7]從機(jī)場(chǎng)實(shí)際運(yùn)行出發(fā),利用航班優(yōu)先級(jí),構(gòu)建航班時(shí)刻優(yōu)化模型,旨在最小化航班請(qǐng)求時(shí)刻和分配時(shí)刻偏移量,通過(guò)增加機(jī)場(chǎng)進(jìn)離港點(diǎn)容量約束,以上海浦東機(jī)場(chǎng)為案例驗(yàn)證。盧婷婷等[8]通過(guò)建立繁忙程度矩陣,并以最小化航班運(yùn)行延誤和減少目的地機(jī)場(chǎng)影響為總目標(biāo)的航班時(shí)刻優(yōu)化模型,結(jié)合粒子群算法,以武漢天河機(jī)場(chǎng)為例進(jìn)行優(yōu)化。方策[9]通過(guò)建立總延誤成本最小的時(shí)刻優(yōu)化模型,以京津冀機(jī)場(chǎng)群為例,通過(guò)改進(jìn)后的匈牙利算法進(jìn)行求解,運(yùn)用 SIMMOD軟件對(duì)優(yōu)化后航班時(shí)刻進(jìn)行仿真驗(yàn)證,通過(guò)對(duì)機(jī)場(chǎng)群航班時(shí)刻經(jīng)過(guò)資源優(yōu)化配置,減少了整體的航班延誤。林雍雅[10]根據(jù)實(shí)際運(yùn)行數(shù)據(jù)引入了進(jìn)離場(chǎng)航班自跑道至共用航路點(diǎn)的飛行時(shí)間,提出了分級(jí)優(yōu)化的求解方法為各方向航班分配優(yōu)先級(jí),并以京津冀機(jī)場(chǎng)群的日航班時(shí)刻為例,使用CPLEX軟件進(jìn)行算例研究,提出了以航班時(shí)刻序列為出發(fā)點(diǎn)建立機(jī)場(chǎng)群周航班時(shí)刻戰(zhàn)略層優(yōu)化模型。曾維理等[11]根據(jù)延誤傳播因果關(guān)系強(qiáng)弱來(lái)表征延誤傳播代價(jià),建立了以最小延誤傳播代價(jià)和最大公平性的雙目標(biāo)函數(shù),以上海浦東國(guó)際機(jī)場(chǎng)為例,從資源利用率和運(yùn)行效率兩方面進(jìn)行了試驗(yàn)驗(yàn)證,證明優(yōu)化后的航班時(shí)刻在時(shí)空分布上更加合理,能夠顯著提高資源利用率和航班正常率,降低航班延誤。呂晨輝[12]通過(guò)對(duì)機(jī)場(chǎng)航班波特性分析、航班時(shí)刻分配影響因素和航班時(shí)刻市場(chǎng)分配效益三個(gè)關(guān)鍵問(wèn)題展開(kāi)研究,建立以凈增效益最大為目標(biāo)函數(shù)的運(yùn)輸機(jī)場(chǎng)增量航班時(shí)刻分配模型,使用TAAM (total airspace and airport modeller) 仿真軟件進(jìn)行實(shí)例驗(yàn)證,驗(yàn)證運(yùn)輸機(jī)場(chǎng)增量航班時(shí)刻分配最佳方案。

本文從機(jī)坪管制和合理安排離場(chǎng)航班時(shí)刻、提高航班放行正常率角度出發(fā),在假設(shè)進(jìn)場(chǎng)航班時(shí)刻不變的情況下對(duì)離場(chǎng)航班時(shí)刻進(jìn)行優(yōu)化研究。設(shè)計(jì)具有自適應(yīng)交叉概率的遺傳算法,采用航班時(shí)刻字符型自然數(shù)編碼方法,對(duì)離場(chǎng)航班時(shí)刻數(shù)學(xué)模型進(jìn)行智能優(yōu)化,達(dá)到前后離場(chǎng)航班時(shí)刻調(diào)整時(shí)間偏差總量最小目標(biāo)。通過(guò)仿真手段,對(duì)所提算法在航班時(shí)刻優(yōu)化問(wèn)題中的有效性和優(yōu)越性進(jìn)行驗(yàn)證。

1 問(wèn)題描述

把時(shí)間分成5 min時(shí)間片段,并分別對(duì)連續(xù)15 min和60 min的機(jī)場(chǎng)容量進(jìn)行了限制。主要目標(biāo)是根據(jù)實(shí)際的運(yùn)行保障能力來(lái)調(diào)整航班時(shí)刻?？紤]了3個(gè)時(shí)間片的容量限制和調(diào)整量約束。在保持進(jìn)場(chǎng)航班時(shí)刻不變的情況下,安排離場(chǎng)航班時(shí)刻和時(shí)間片內(nèi)數(shù)量不會(huì)超過(guò)機(jī)場(chǎng)的實(shí)際運(yùn)行容量以及前后離場(chǎng)航班時(shí)刻調(diào)整時(shí)間偏差總量最小,避免離場(chǎng)航班擁堵或跑道頭等待,有效提高機(jī)場(chǎng)航班放行正常率。

2 模型建立

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

以最小化離場(chǎng)航班時(shí)刻調(diào)整時(shí)間偏差總量為主要目標(biāo),建立以下目標(biāo)函數(shù):

(1)

(2)

式中:aij為航班時(shí)刻調(diào)整量;xij為決策變量;m為待優(yōu)化的航班數(shù);n為可用的時(shí)刻數(shù);以5 min為一個(gè)單位時(shí)刻。

2.2 約束條件

航班時(shí)刻受唯一性約束,每個(gè)航班有且僅有被分配的一個(gè)時(shí)刻。

(3)

在實(shí)際運(yùn)用中,還應(yīng)當(dāng)考慮航空公司的經(jīng)濟(jì)利益,盡可能減少航班的時(shí)刻調(diào)整量。對(duì)航班時(shí)刻調(diào)整范圍約束。

(4)

為了使結(jié)果符合實(shí)際運(yùn)行情況,制定更加平滑和精細(xì)的航班計(jì)劃,將以5 min作為時(shí)間片段,對(duì)任意連續(xù)時(shí)間片長(zhǎng)度為5 min、15 min、60 min內(nèi)的離場(chǎng)航班時(shí)刻容量進(jìn)行限制。

(5)

(6)

(7)

式中:i=1,2,…m;j=1,2,…,n;C5 min、C15 min、C60 min分別為連續(xù)5 min、15 min、60 min的離場(chǎng)航班時(shí)刻容量值。

3 算法實(shí)現(xiàn)

3.1 算法改進(jìn)

交叉概率pc和變異概率pm能夠根據(jù)適應(yīng)度自動(dòng)調(diào)整。當(dāng)種群各個(gè)體適應(yīng)度趨于局部最優(yōu)或者趨于一致時(shí),使pc和pm增加; 而在種群適應(yīng)度分散較大時(shí),使pc和pm減小。同時(shí),對(duì)于適應(yīng)度高于群體平均適應(yīng)值的個(gè)體,保持其在下一代中的存在; 而低于平均適應(yīng)值的個(gè)體,對(duì)于較低的pc和pm,將其淘汰。

因此,自適應(yīng)的pc和pm能夠提供相對(duì)某個(gè)解的最佳pc和pm。自適應(yīng)遺傳算法在保持種群多樣性的同時(shí),保證遺傳算法的收斂性。自適應(yīng)遺傳算法中,pc和pm按如下公式進(jìn)行自適應(yīng)調(diào)整:

(8)

(9)

式中:f′為要交叉兩個(gè)個(gè)體中較大的那個(gè)的適應(yīng)度值;favg為每代群體的平均適應(yīng)度值;fmax為群體中最大的適應(yīng)度值;f為要變異個(gè)體的適應(yīng)度值。

3.2 算法設(shè)計(jì)

把問(wèn)題的特征進(jìn)行編碼是設(shè)計(jì)遺傳算法的首步,進(jìn)行的編碼方法需要能夠表達(dá)問(wèn)題的解。

在對(duì)本文問(wèn)題的求解當(dāng)中,為了降低算法數(shù)據(jù)操作維數(shù)和運(yùn)算量,將對(duì)航班時(shí)刻的編碼轉(zhuǎn)化為對(duì)航班序號(hào)的編碼操作。每個(gè)航班的允許調(diào)整時(shí)刻受可接受最大時(shí)刻調(diào)整量限制。取原有航班時(shí)刻為基準(zhǔn)0,對(duì)該最大時(shí)刻調(diào)整量限制范圍內(nèi)的有效航班時(shí)刻以5 min時(shí)間片段間隔進(jìn)行時(shí)刻偏移量的整數(shù)序列編碼,就產(chǎn)生一個(gè)具有正負(fù)符號(hào)的維數(shù)較小的時(shí)刻偏移量編碼序列。每個(gè)航班的航班時(shí)刻偏移量時(shí)間片段倍乘因子,從該時(shí)刻偏移量編碼序列中隨機(jī)選取,建立航班與時(shí)刻偏移量倍乘因子間的一一對(duì)應(yīng)關(guān)系。

一個(gè)染色體的基因位置順序號(hào)固定不變對(duì)應(yīng)原始時(shí)刻表中全體離場(chǎng)航班順序號(hào)?；蛭恢庙樞蛱?hào)對(duì)應(yīng)著原始航班時(shí)刻并作為基準(zhǔn)0時(shí)刻。該染色體的基因值也取為離場(chǎng)航班序號(hào)。對(duì)染色體基因值的遺傳編碼操作,映射為對(duì)時(shí)刻偏移量倍乘因子的操作。根據(jù)染色體基因位置順序號(hào)與其對(duì)應(yīng)的基因值間的關(guān)系,計(jì)算離場(chǎng)航班的變動(dòng)或優(yōu)化時(shí)刻。

這種確定航班時(shí)刻的方法,大大降低了遺傳編碼數(shù)據(jù)的操作量和運(yùn)算量。

(1)編碼設(shè)計(jì):采用隨機(jī)正整數(shù)編碼的方式對(duì)染色體進(jìn)行編碼。該編碼方式使每個(gè)航班號(hào)對(duì)應(yīng)一個(gè)染色體內(nèi)的一個(gè)唯一的隨機(jī)正整數(shù)。需要排序的航班數(shù)與編碼長(zhǎng)度一致。一條染色體剛好對(duì)應(yīng)一個(gè)全體離場(chǎng)航班排列,數(shù)字的大小代表著航班的次序先后。

若有10架次航班需要排序,命名而F1～F10,則該編碼方法在1～10隨機(jī)生成10個(gè)整數(shù)按大小映射到航班序列上,生成了1條染色體:

航班序列:F9 F5 F1 F3 F7 F4 F2 F10 F8 F6

染色體: 9 5 1 3 7 4 2 10 8 6

(2)交叉運(yùn)算:由于采用了正整數(shù)編碼,在交叉運(yùn)算當(dāng)中不可避免地會(huì)產(chǎn)生無(wú)效解,故采用部分映射雜交方法,選擇雙交叉點(diǎn)進(jìn)行染色體基因交換操作。下面將進(jìn)行舉例說(shuō)明。

首先對(duì)種群中的染色體進(jìn)行配對(duì),每組將會(huì)有兩個(gè)染色體進(jìn)行兩個(gè)交叉點(diǎn)的交換。如確定了以下父代染色體A和父代染色體B的兩個(gè)交叉點(diǎn)位置,對(duì)交叉點(diǎn)內(nèi)數(shù)據(jù)進(jìn)行交叉操作。

父代染色體A:9 5 1 3 7 4 2 10 8 6

父代染色體B:10 5 4 6 3 8 7 2 1 9

則得到子代染色體A1和子代染色體B1。

子代染色體A1:9 5 16 3 82 10 8 6

子代染色體B1:10 5 43 7 47 2 1 9

交叉后,發(fā)現(xiàn)同一個(gè)個(gè)體出現(xiàn)重復(fù)數(shù)字現(xiàn)象,將導(dǎo)致出現(xiàn)無(wú)效解,對(duì)此,不重復(fù)數(shù)字將會(huì)被保留,沖突數(shù)字用*取代。

子代染色體A1:9 5 16 3 82 10 * *

子代染色體B1:10 5 *3 7 4* 2 1 9

采用部分映射的方法消除出現(xiàn)的沖突數(shù)字,根據(jù)父代染色體A和B,利用中間段的對(duì)應(yīng)關(guān)系進(jìn)行映射,得到:

子代染色體A1:9 5 16 3 82 10 4 7

子代染色體B1:10 5 83 7 46 2 1 9

(3)變異運(yùn)算:采取隨機(jī)抽取2個(gè)位置的基因片段進(jìn)行互換操作。如隨機(jī)選擇父代染色體A的第4和第7個(gè)基因進(jìn)行互換,結(jié)果如下。

父代染色體A正常狀態(tài):

父代染色體A:9 5 137 4210 8 6

變異后的子代染色體為

父代染色體A1:9 5 127 4310 8 6

3.3 算法流程

航班時(shí)刻優(yōu)化的遺傳算法流程如圖1所示。

圖1 航班時(shí)刻優(yōu)化遺傳算法求解流程

實(shí)現(xiàn)遺傳算法的具體步驟如下。

步驟1：讀取需要排序的航班信息。

步驟2：初始化種群。

步驟3：計(jì)算染色體對(duì)應(yīng)航班隊(duì)列的目標(biāo)函數(shù)。根據(jù)染色體確定的航班序列,按間隔要求和約束條件計(jì)算計(jì)劃過(guò)點(diǎn)時(shí)間以及延誤值,將不滿足最大允許位置交換約束的航班加10 000 s,計(jì)算目標(biāo)函數(shù)值。直到計(jì)算出整體隊(duì)列。

步驟4：根據(jù)目標(biāo)函數(shù)計(jì)算適應(yīng)度函數(shù)。

步驟5：找到種群最優(yōu)和最差個(gè)體,最優(yōu)個(gè)體賦值給Current best member。

步驟6：判斷進(jìn)化代數(shù)是否滿足小于最大代數(shù)的條件。若滿足,代數(shù)加1并按順序執(zhí)行,否則轉(zhuǎn)到步驟13。

步驟7：輪盤(pán)賭選擇。

步驟8：按自適應(yīng)交叉概率對(duì)染色體進(jìn)行交叉操作。

步驟9：按變異概率對(duì)染色體進(jìn)行變異操作。

步驟10：依次執(zhí)行步驟3、步驟4和步驟5。

步驟11：評(píng)估遺傳效果,若當(dāng)前最優(yōu)個(gè)體優(yōu)于Current best member,將其賦給Current best member,反之則被Current best member取代。

步驟12：輸出這代種群平均和最優(yōu)函數(shù)值。

步驟13：按Current best member重新計(jì)算航班隊(duì)列的目標(biāo)到達(dá)時(shí)間、目標(biāo)過(guò)點(diǎn)時(shí)間、延誤等信息。

步驟14：輸出航班隊(duì)列及相應(yīng)的目標(biāo)到達(dá)時(shí)間和目標(biāo)過(guò)點(diǎn)時(shí)間。

4 實(shí)例與仿真驗(yàn)證

選取蘭州中川國(guó)際機(jī)場(chǎng)某日455起降架次的歷史進(jìn)離場(chǎng)航班時(shí)刻表進(jìn)行優(yōu)化。其中進(jìn)場(chǎng)航班230架次,離場(chǎng)航班225架次。

求解的遺傳算法采用MATLAB編程語(yǔ)言編寫(xiě)程序。程序參數(shù)設(shè)置如下:種群規(guī)模為160,最大進(jìn)化代數(shù)為200,變異概率為0.2,pc1=0.9,pc2=0.6,pm1=0.1,pm2=0.001。

根據(jù)蘭州中川機(jī)場(chǎng)實(shí)際運(yùn)行情況,機(jī)場(chǎng)離場(chǎng)小時(shí)容量為每小時(shí)21架次,15 min離場(chǎng)放行能力約8架次,5 min離場(chǎng)放行能力約4架次;C60 min=21,C15 min=8,C5 min=4。

同時(shí),為了使調(diào)整后的時(shí)間具有普適性和實(shí)用性,優(yōu)化的時(shí)間調(diào)整量范圍限制設(shè)置為前后不超過(guò)15 min,換言之,如果某航班調(diào)整前的起飛時(shí)間為08:15,那個(gè)該航班優(yōu)化后的時(shí)刻為08:00—08:30的一個(gè)合適的值。

對(duì)從歷史航班時(shí)刻表中提取的離場(chǎng)航班時(shí)刻表使用本文算法進(jìn)行優(yōu)化。相對(duì)起始,優(yōu)化后的離場(chǎng)航班時(shí)刻調(diào)整時(shí)間偏差總量共減少了268 min,減少了38.98%。優(yōu)化調(diào)整的離場(chǎng)航班41個(gè)。求解時(shí)間為111.8 s,目標(biāo)函數(shù)值從第32代收斂,歷代目標(biāo)函數(shù)值迭代曲線如圖2所示,可以判斷為得到本次運(yùn)算優(yōu)化解。算法收斂并有效。

圖2 歷代目標(biāo)函數(shù)值迭代曲線

依據(jù)優(yōu)化后的離場(chǎng)航班時(shí)刻,替換原始?xì)v史進(jìn)離場(chǎng)航班時(shí)刻表中離場(chǎng)航班時(shí)刻形成優(yōu)化的進(jìn)離場(chǎng)航班時(shí)刻表。將原始的和優(yōu)化后的進(jìn)離場(chǎng)航班時(shí)刻表分別導(dǎo)入已經(jīng)建立的蘭州中川機(jī)場(chǎng)的全空域和機(jī)場(chǎng)TAAM仿真模型,建立優(yōu)化前后的兩種仿真場(chǎng)景并分別進(jìn)行運(yùn)行仿真。蘭州管制區(qū)和蘭州機(jī)場(chǎng)仿真模型與仿真場(chǎng)景如圖3和圖4所示。

圖3 蘭州管制區(qū)3D仿真場(chǎng)景

圖4 蘭州機(jī)場(chǎng)3D仿真場(chǎng)景

仿真后分別獲取兩種場(chǎng)景的仿真數(shù)據(jù)庫(kù)中航班仿真運(yùn)行時(shí)間數(shù)據(jù),分別計(jì)算兩種場(chǎng)景下平均航班延誤時(shí)間和航班放行正常率。優(yōu)化前后兩種場(chǎng)景下的結(jié)果比較如下表1所示。

由表1可知,優(yōu)化離場(chǎng)航班時(shí)刻后,航班平均延誤時(shí)間降低了1.04 min,達(dá)12.8%;離場(chǎng)航班平均延誤時(shí)間降低了2.42 min,達(dá)22.3%;離場(chǎng)航班延誤架次減少了27架次,達(dá)42.8%;航班放行正常率從72%提高到了84%,提高了12%。主要原因是由于優(yōu)化了離場(chǎng)航班時(shí)刻,有效降低了跑道頭的航班擁堵,減少了跑道頭等待的離場(chǎng)航班架次和等待時(shí)間,從而提高了機(jī)場(chǎng)航班放行正常率。

表1 優(yōu)化前后仿真結(jié)果比較

5 結(jié)論

對(duì)機(jī)場(chǎng)離場(chǎng)航班時(shí)刻進(jìn)行重新排序與優(yōu)化,可以明顯減少離場(chǎng)航班跑道頭擁堵、等待離場(chǎng)航班數(shù)量和等待時(shí)間延誤,提高機(jī)場(chǎng)航班放行正常率。采用基于自適應(yīng)交叉概率的遺傳算法可以有效優(yōu)化離場(chǎng)航班時(shí)刻問(wèn)題,得到合理的可行解,降低航班延誤,提高航班放行正常率?；谧赃m應(yīng)交叉概率的改進(jìn)遺傳算法能夠?yàn)楹桨嗯判蚝蜁r(shí)刻優(yōu)化決策輔助系統(tǒng)開(kāi)發(fā)和應(yīng)用提供重要價(jià)值。未來(lái)的研究可以考慮擴(kuò)大研究范圍,涵蓋更多的航班數(shù),以更全面、準(zhǔn)確地評(píng)估遺傳算法在空中交通系統(tǒng)優(yōu)化中的應(yīng)用效果。