匯聚航路航班排序的遺傳算法研究

趙嶷飛 王惠斌

【摘 要】基于匯聚航路的特點(diǎn)，結(jié)合區(qū)域流量控制的實(shí)際情況，建立了匯聚航路航班排序模型，并設(shè)計(jì)了相應(yīng)的遺傳算法。在模型中提出了多路編碼算法，并對(duì)交叉算子和變異算子進(jìn)行了改進(jìn)，提高了算法的求解性能。解決了在流量控制情況下，匯聚航路上的航班排序問(wèn)題。最后對(duì)算法進(jìn)行了仿真驗(yàn)證。結(jié)果表明，該遺傳算法在較快求得全局最優(yōu)解的前提下，能有效減小匯聚航路航班的空中延誤。

【關(guān)鍵詞】航班排序 遺傳算法 流量控制

隨著民航運(yùn)輸量的迅速增長(zhǎng)，航班量的不斷增大，由于有限的空域資源而導(dǎo)致的流量控制次數(shù)和時(shí)長(zhǎng)也在不斷地增加。如何有效地解決由于流量控制原因而導(dǎo)致的空中航班延誤成為當(dāng)務(wù)之急。流量控制通常是由于某一區(qū)域，機(jī)場(chǎng)或航路點(diǎn)的容量下降而產(chǎn)生的。常見(jiàn)的控制形式有點(diǎn)控制和區(qū)域控制?？刂频姆绞蕉酁橄拗骑w機(jī)以一定的時(shí)間間隔或者距離間隔通過(guò)某一航路點(diǎn)。然而無(wú)論采用那種方式都會(huì)對(duì)實(shí)施流量控制所在航路點(diǎn)的上游航班造成影響，隨著延誤的傳播，往往還會(huì)對(duì)相鄰管制區(qū)的航班造成影響。解決這一問(wèn)題的方法有兩種：（1）通過(guò)合理的設(shè)置流量控制值來(lái)減少航班的空中延誤。（2）通過(guò)合理的航班排序來(lái)減少航班的空中延誤。本文主要針對(duì)第二種方法進(jìn)行研究。

而以往的航班排序問(wèn)題多是針對(duì)終端區(qū)航班排序或是地面等待問(wèn)題的航班排序，對(duì)由于流量控制原因?qū)е碌暮铰飞巷w行的航班延誤排序的研究卻較少。然而傳統(tǒng)的航班排序算法又并不適合此問(wèn)題的求解，而且運(yùn)行效率較低，收斂速度較慢。因此本文對(duì)解決傳統(tǒng)排序問(wèn)題遺傳算法進(jìn)行了改進(jìn)，并針對(duì)匯聚航路的特點(diǎn)提出了多路編碼的編碼方式，根據(jù)流量控制的實(shí)際情況，進(jìn)行了建模。本文的結(jié)構(gòu)如下：首先對(duì)流量控制點(diǎn)上游的航路特點(diǎn)進(jìn)行了分析，提出了匯聚航路航班排序模型，其次，對(duì)傳統(tǒng)的遺傳算法進(jìn)行了改進(jìn)，最后，對(duì)算法進(jìn)行了仿真，并與傳統(tǒng)的排序算法進(jìn)行了比較，證明了算法的有效性。

1問(wèn)題描述

飛往流量控制點(diǎn)的航班通常經(jīng)由多條匯聚于流量控制點(diǎn)的航路到達(dá)，如圖1所示。圖中A點(diǎn)為流量控制點(diǎn)，1-N對(duì)應(yīng)了匯聚于A點(diǎn)的N條航路，其中2，3航路的航班匯聚于B后再飛往A點(diǎn)，4，5航路的航班匯聚于C點(diǎn)后再飛往A點(diǎn)。對(duì)下游實(shí)施流量控制往往會(huì)對(duì)上游的航班造成延誤影響，如果延誤過(guò)大，超出了流量控制點(diǎn)所在管制區(qū)對(duì)延誤的吸收能力，延誤將會(huì)沿著航路向上游管制區(qū)傳播。這時(shí)如何合理的對(duì)空中航班進(jìn)行排序，減少空中的延誤顯得尤為重要。管制區(qū)對(duì)飛行中的航班延誤，多采用雷達(dá)引導(dǎo)，調(diào)速，空中等待等方式進(jìn)行處理。而空中等待不僅十分耗油，需要較大的空域進(jìn)行實(shí)施，而且會(huì)增加管制員的工作負(fù)荷，因此對(duì)航路上飛行航班的排序時(shí)，在保證航班總延誤最小的情況下，還要盡量減少航班空中的等待的發(fā)生。

圖1 匯聚航路結(jié)構(gòu)示意圖

2匯聚航路航班排序模型建立

綜合以上分析，建模方法如下：

（1）以流量控制點(diǎn)的流量控制時(shí)間長(zhǎng)度為基準(zhǔn)，凡是在此時(shí)間長(zhǎng)度區(qū)間內(nèi)飛行的航班即為所要進(jìn)行排序的航班，記航班總數(shù)為n。

（2）每一條匯聚于流量控制點(diǎn)的航路記為1路，設(shè)總共有m條航路匯聚于流量控制點(diǎn)，即共有m路。選擇標(biāo)準(zhǔn)為所需要進(jìn)行排序的航班經(jīng)過(guò)的航路，如果航路在流量控制點(diǎn)前交匯于某航路點(diǎn)，以該航路點(diǎn)上游的航路作為區(qū)分，如第2路，第4路，該航路點(diǎn)到流量控制點(diǎn)之間的航班標(biāo)記為編號(hào)較小的路的航班。

（3）在第m條路上飛行的航班組成一個(gè)隊(duì)列，該隊(duì)列中的航班不允許出現(xiàn)航班超越，且該隊(duì)列的航班在排序前和排序后經(jīng)過(guò)流量控制點(diǎn)的順序不變。

（4）考慮到航路飛行航班的實(shí)際情況，針對(duì)不同的航班的優(yōu)先級(jí)設(shè)置不同的延誤權(quán)值。

2.1 參數(shù)定義

N：匯聚航路的集合；

F：航班的集合；

：第n條航路上第f航班的延誤權(quán)值；

：第n條匯集航路上的航班集合；

：第n條航路上第f航班預(yù)計(jì)到流量控制點(diǎn)的時(shí)刻；

：第n條航路上第f航班實(shí)際到達(dá)流量控制點(diǎn)的時(shí)刻；

V：流量控制點(diǎn)處的時(shí)間間隔；

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

2.3 約束條件

（1）航班不可加速提前到達(dá)流量控制點(diǎn)：

（2）到達(dá)流量控制點(diǎn)的過(guò)點(diǎn)航班滿足間隔約束：

（3）由上游航路到達(dá)流量控制點(diǎn)的同一行路上的航班不允許超越：

（4）航班實(shí)際到達(dá)流量控制點(diǎn)的時(shí)刻：

指的前一個(gè)航班通過(guò)流量控制點(diǎn)的時(shí)刻。為前后航班航路飛行時(shí)允許的最小飛行間隔。由于流量控制的間隔通常大于，所以公式四可以簡(jiǎn)化為：

3 多路編碼遺傳算法設(shè)計(jì)

根據(jù)以上模型并結(jié)合約束條件，設(shè)計(jì)遺傳算法，來(lái)實(shí)現(xiàn)航路航班的最優(yōu)排序，并以三條匯聚航路為例對(duì)算法進(jìn)行解釋說(shuō)明，如圖2所示。

圖2 三條航路匯聚示意圖

3.1 編碼方法設(shè)計(jì)

以往的遺傳算法在解決航班排序問(wèn)題時(shí)，編碼方式多為格雷編碼，二進(jìn)制編碼，浮點(diǎn)編碼等，而這些編碼方式在解決該模型下的航班排序問(wèn)題時(shí)并不是最合理的選擇，因此針對(duì)該模型中航班排序的問(wèn)題，提出了多路編碼的編碼方式。

所謂多路編碼是指航班（基因）在染色體中的值，是用該航班所在航路的航路號(hào)表示，航路的標(biāo)號(hào)遵循上文中建模方法（2）中的方法進(jìn)行標(biāo)記。如圖2所示，三條匯聚航路的標(biāo)號(hào)分別1，2，3。將1航路上的航班都記為1，將2和3航路上的航班分別記為2和3。設(shè)第一條航路上有5架航班，第二條航路上有5架航班，第三條航路上有2架航班，則染色體由5個(gè)1，5個(gè)2，2個(gè)3排列組合而成，該染色體共有12個(gè)基因。其中5個(gè)1代表著1號(hào)航路上按順序排列的5架航班。5個(gè)2，2個(gè)3的意義同上。染色體形式例如：

G=（112122123213）

若有N條航路匯聚于流量控制點(diǎn)，則每個(gè)基因可能取值的最大范圍記為1到N。本例中每個(gè)基因取值的最大范圍為1到3。對(duì)于航路3的情形，假設(shè)航路3與航路2的航路交匯點(diǎn)到流量控制點(diǎn)間的航路上有m架航班。為了保障同條航路上不出現(xiàn)航班的超越，則當(dāng)某一基因取值為3時(shí)，必須保證該基因前有m個(gè)或m以上個(gè)基因取值為2。因此初始化種群時(shí)若出現(xiàn)如下基因應(yīng)予以舍棄。

G=（312311221212） 出現(xiàn)航班超越

3.2 初始種群

如果在算法開(kāi)始時(shí)能得到一個(gè)平均適應(yīng)度較高的初始群體，再進(jìn)行進(jìn)化，將會(huì)顯著地提高算法的求解性能。針對(duì)這一問(wèn)題首先引入最大交換位置MPS這一概念。此處最大交換位置指的是以到先服務(wù)FCFS原則，依據(jù)各航路航班預(yù)計(jì)到達(dá)流量控制點(diǎn)的時(shí)間，進(jìn)行排序所產(chǎn)生的染色體中，不同航路的航班相對(duì)位置變化的上限。實(shí)際當(dāng)中航班相對(duì)位置的變化會(huì)增加管制員的工作負(fù)荷，文獻(xiàn)三中對(duì)MPS的取值大小選擇對(duì)航班排序延誤的影響和管制員工作負(fù)荷的關(guān)系做了分析，結(jié)論表明，當(dāng)MPS取值大于3時(shí)，將顯著的增加管制員的工作負(fù)荷。因此此處選MPS值為2。

設(shè)計(jì)一個(gè)以三個(gè)基因長(zhǎng)度為單位的時(shí)間窗，沿著染色體從左到右移動(dòng)，步進(jìn)為2，每移動(dòng)一次，隨機(jī)變換時(shí)間窗內(nèi)兩個(gè)基因的位置，當(dāng)時(shí)間窗移動(dòng)到染色體結(jié)尾時(shí)，將該染色體記為新染色體。對(duì)以先到先服務(wù)為原則的初始排序航班進(jìn)行編碼，產(chǎn)生初始染色體。將該染色體進(jìn)行若干次如上變換，將產(chǎn)生的種群定為初始種群。

3.3 交叉算子和變異算子設(shè)計(jì)

由于傳統(tǒng)的交叉算子和變異算子，所產(chǎn)生的染色體，會(huì)帶來(lái)無(wú)效解，降低求解效率，因此，需要對(duì)傳統(tǒng)的交叉算子和變異算子進(jìn)行改進(jìn)，結(jié)合本文中提到的基因編碼方式，可將其看成一種單性遺傳，并不考慮交叉操作。新染色體的產(chǎn)生只通過(guò)基因的變異來(lái)實(shí)現(xiàn)。

變異方式為對(duì)染色體中的基因以隨機(jī)概率向左或向右移動(dòng)小于MPS位。由于要保證子代種群平均適應(yīng)度高于父代種群，因此，對(duì)父代優(yōu)良的基因進(jìn)行變異，比對(duì)父代較差的基因進(jìn)行變異，得到優(yōu)良基因的概率更大。依據(jù)這一原則，采用父代中最優(yōu)的染色體進(jìn)行變異，生成子代種群。

3.4適應(yīng)度函數(shù)

將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，適應(yīng)度函數(shù)公式如下：

3.5 計(jì)算步驟

Step1.航班編碼，初始化種群gen（t），t=1，設(shè)置相應(yīng)的參數(shù)，進(jìn)化代數(shù)GEN，群體大小N等。

Step2.用3.3中的適應(yīng)函數(shù)計(jì)算染色體的適應(yīng)度值，對(duì)其大小進(jìn)行比較，選出適應(yīng)度最大的染色體，

Step3.對(duì)父代最優(yōu)的染色體進(jìn)行選擇，進(jìn)行變異，產(chǎn)生規(guī)模同樣為N的子代種群，t=t+1。

Step4.當(dāng)t>GEN時(shí)，算法停止，否則回到step2.

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

仿真時(shí)采用三條匯聚航路上共20架航班，如圖2所示。延誤權(quán)值化分為0.6，0.3，0.1三個(gè)級(jí)別，每條航路上的航班，及預(yù)計(jì)到達(dá)流量控制點(diǎn)的時(shí)間和延誤權(quán)值見(jiàn)表1。采用MATLAB對(duì)遺傳算法進(jìn)行了編程。流量控制的時(shí)間間隔設(shè)置為2分鐘，種群規(guī)模設(shè)置為100，進(jìn)化代數(shù)設(shè)置為300。

5結(jié)語(yǔ)

本文所提出的多路編碼遺傳算法可以快速求得最優(yōu)解，采用數(shù)據(jù)進(jìn)行仿真，并與先到先服務(wù)的航班排序進(jìn)行對(duì)比，結(jié)果表明，該算法得到的航班排序可以有效減小延誤成本。在此研究的基礎(chǔ)上，下一步將對(duì)區(qū)域中多航路點(diǎn)進(jìn)行流量控制的情況下航路航班的排序進(jìn)行研究。

參考文獻(xiàn)：

[1]趙嶷飛，金長(zhǎng)江.區(qū)域空中交通流量控制研究[J].飛行力學(xué)，2002，20（2）：67-70.

Zhao Y F，Jin C J.An approach to area traffic flow control research [J].Flight Dynamics，2002，20（2）：76-70.

[2]趙嶷飛，張?chǎng)?區(qū)域空中交通流量控制建模研究[J].飛行力學(xué)，2009，27（5）：86-88.

Zhao Y F，Zhang W W. Modeling area air traffic flow control [J]. Flight Dynamics，2009，27（5）：86-88.

[3]徐肖豪，姚源.遺傳算法在終端區(qū)飛機(jī)排序中的應(yīng)用[J].交通運(yùn)輸工程學(xué)報(bào)，2004，4（3）：121-126.

Xu X H，Yao Y. Application of genetic algorithm to aircraft sequencing in terminal area [J].Journal of Transportation Engineering，2004，4（3）：121-126.

[4]Delahaye Daniel，Sofiane Oussedik，Puechmorel Stephane. Airspace Congestion Smoothing by Multi-objective Genetic Algorithm [C].ACM Symposium on Applied Computing，2005：907-912.

[5]Aditya P. Saraf ， Gary L. Slater. Optimal Dynamic Scheduling of Aircraft Arrivals at Congested Airports [C]. Journal of Guidance，Control，And Dynamics，2008，31（1）：53-55.

[6]Shin-Lai Tien， Christine Taylor.A Rout-Based Queuing Network Model for Air Traffic Flow Contingency Management. AIAA Aviation Technology， Integration， and Operations Conference，2011：12-14.

[7]張軍，詹志輝.計(jì)算智能[M].北京：清華大學(xué)出版社，2009.