基于改進遺傳算法的離場航班時刻優(yōu)化

王大軍

(蘭州中川國際機場有限公司運行指揮中心, 蘭州 730000)

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

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

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

1 問題描述

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

2 模型建立

2.1 目標函數(shù)

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

(1)

(2)

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

2.2 約束條件

航班時刻受唯一性約束,每個航班有且僅有被分配的一個時刻。

(3)

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

(4)

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

(5)

(6)

(7)

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

3 算法實現(xiàn)

3.1 算法改進

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

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

(8)

(9)

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

3.2 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

父代染色體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)同一個個體出現(xiàn)重復(fù)數(shù)字現(xiàn)象,將導(dǎo)致出現(xiàn)無效解,對此,不重復(fù)數(shù)字將會被保留,沖突數(shù)字用*取代。

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

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

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

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

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

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

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

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

變異后的子代染色體為

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

3.3 算法流程

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

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

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

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

步驟2：初始化種群。

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

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

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

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

步驟7：輪盤賭選擇。

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

步驟9：按變異概率對染色體進行變異操作。

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

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

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

步驟13：按Current best member重新計算航班隊列的目標到達時間、目標過點時間、延誤等信息。

步驟14：輸出航班隊列及相應(yīng)的目標到達時間和目標過點時間。

4 實例與仿真驗證

選取蘭州中川國際機場某日455起降架次的歷史進離場航班時刻表進行優(yōu)化。其中進場航班230架次,離場航班225架次。

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

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

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

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

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

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

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

圖4 蘭州機場3D仿真場景

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

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

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

5 結(jié)論

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