王莉莉, 胡畔

(中國民航大學(xué) 空中交通管理學(xué)院, 天津 300300)

?

基于優(yōu)先級調(diào)配的進(jìn)離場航班序列動態(tài)優(yōu)化

王莉莉, 胡畔

(中國民航大學(xué) 空中交通管理學(xué)院, 天津 300300)

以可變的優(yōu)先級作為調(diào)配手段,針對航班的進(jìn)離場序列建立了一種動態(tài)優(yōu)化模型。首先,根據(jù)不同進(jìn)離場階段的航空器燃油消耗率和安全系數(shù),進(jìn)行航班初始優(yōu)先級分配;然后,考慮機(jī)場的空中等待航班數(shù)量、空域容量、場面容量以及機(jī)場的起飛需求,對航班優(yōu)先級進(jìn)行二次調(diào)配。以總耗油量為目標(biāo)函數(shù),引入合作型協(xié)同進(jìn)化遺傳算法,設(shè)計了令一對代表個體形成合作團(tuán)體的新的代表個體選擇方案,改善傳統(tǒng)遺傳算法中存在的種群多樣性低、易早熟等問題。仿真結(jié)果表明,在機(jī)場容量限制下,該模型仍可以實現(xiàn)流量的動態(tài)調(diào)配,并有效降低燃油消耗,緩解機(jī)場空域及場面的運行壓力。

合作型協(xié)同進(jìn)化遺傳算法; 動態(tài)優(yōu)化; 優(yōu)先級調(diào)配; 容量限制

0　引言

航班進(jìn)離場優(yōu)化為空中交通流量管理手段之一,對優(yōu)化使用跑道容量、機(jī)場空域資源等具有重要意義。Dear[1]提出將位置約束法(CRS)應(yīng)用于航班的優(yōu)化排序問題。Balakrishnan等[2]在Dear的研究基礎(chǔ)上建立了網(wǎng)絡(luò)圖。除此之外,滑動窗策略[3]、分支定界法[4]、模糊規(guī)劃方法[5]等優(yōu)化方案也被應(yīng)用于解決此類問題。隨后,智能算法[6-8]被引入到航班進(jìn)離場優(yōu)化中,Ciesielskid等[7-8]分別采用傳統(tǒng)遺傳算法、結(jié)合滑動時間窗策略的遺傳算法優(yōu)化航班進(jìn)離場序列。上述研究均僅單獨考慮進(jìn)場、離場或是單跑道情況,未考慮航班延誤時的機(jī)場空域容量及場面運行容量的限制。

在優(yōu)先級調(diào)配方面,李習(xí)鳳[9]提出優(yōu)先級的分配應(yīng)以航班時刻表為基礎(chǔ),并以延誤時間作為主要依據(jù),進(jìn)行航班優(yōu)先級調(diào)配;孔金鳳[10]提出了流量管理中優(yōu)先級分配的精髓,即考慮讓誰優(yōu)先使用有限的空域及容量資源。在上述研究中,大多以宏觀概念說明優(yōu)先級的分配原則,未將其細(xì)化至進(jìn)離場的各個階段,且靜態(tài)的優(yōu)先級已無法滿足機(jī)場的動態(tài)運行。

本文將處于不同階段的航班賦予相應(yīng)的優(yōu)先級,并考慮機(jī)場空域容量及場面運行容量的限制,根據(jù)實時容量、流量狀態(tài)對優(yōu)先級進(jìn)行二次調(diào)配,實現(xiàn)優(yōu)先級的動態(tài)可變。

1　基于優(yōu)先級調(diào)配的優(yōu)化模型

1.1優(yōu)先級調(diào)配模型原理

航班的進(jìn)場過程分為兩個階段:A——航路下降至起始進(jìn)近定位點;B——起始進(jìn)近定位點至跑道端著陸。離場過程分為3個階段:C——航班停機(jī)位等待至航班撤輪檔;D——航班撤輪檔滑行至跑道端口;E——航班從跑道端口開始爬升至起始進(jìn)近定位點。

根據(jù)民航的實際運行可知,民用航空器在低空平飛和爬升運行時的油耗明顯高于高空運行,而在進(jìn)場階段發(fā)動機(jī)一般處于慢車狀態(tài),油耗很小。除此之外,航空器低空運行的危險系數(shù)也顯著高于高空。航空器在航路上飛行的油耗以及危險系數(shù)相對于地面飛行來說也高出很多,因此,在同一時段不同階段的航空器初始優(yōu)先級的大小應(yīng)該為E>B>A>D>C。由于機(jī)場場面的停機(jī)位數(shù)量有限,管制員在空中可指揮的航班數(shù)量有限,因此進(jìn)離場航班的排序在最大程度利用空域容量的同時還必須滿足場面容量的限制。

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

以航班總?cè)加土繛槟繕?biāo)函數(shù),其表達(dá)式為:

(1)

1.3決策變量

決策變量的定義如下:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式中:Xir,Ymn,Zjr為航班對跑道的變量;r=(1,2,…,R)為機(jī)場跑道數(shù)量;pm(m=1,2,…,N)為航班優(yōu)先級;A(t),R(t)分別為t+1時刻空中航班數(shù)、場面航班數(shù);Ca(t+1),Cg(t+1)分別為[t,t+1]時段的場面容量、空域容量。

1.4約束條件

1.4.1優(yōu)先級賦值

初始優(yōu)先級賦值:

(9)

式中:l∈{A,B,C,D,E}為航空器的當(dāng)前位置;α1,α3,α4分別為航空器所處的A,C,D階段的優(yōu)先級,且α*>α1>α4>α3。為保證運行安全,令B,E兩個階段的航班的優(yōu)先級為所有航班中最高。

優(yōu)先級二次調(diào)配:為保證安全,對處在A,C,D三個階段的航班進(jìn)行優(yōu)先級調(diào)配。

(10)

(11)

式中:pi(i=1,2,…,Na)為進(jìn)場航班優(yōu)先級;pj(j=1,2,…,Nd)為離場航班優(yōu)先級;δ1,δ2為增加的優(yōu)先級系數(shù)。

式(10)表示當(dāng)機(jī)場場面容量未達(dá)到飽和,同時機(jī)場上空實際航班數(shù)超過機(jī)場空域容量時,為空中最早到達(dá)的部分航班增大優(yōu)先級,確保其盡快降落。式(11)表示當(dāng)機(jī)場場面實際航班數(shù)大于等于其容量值時,為場面最早撤輪檔的部分航班增大優(yōu)先級,確保其盡快起飛。

1.4.2優(yōu)先級約束

為了保證優(yōu)先級相對較高的航班有優(yōu)先降落或起飛的權(quán)利,對在跑道端著陸或起飛的航班時刻做如下限制:

(12)

(13)

(14)

式(12)表示同為進(jìn)場或同為離場的兩個航班,優(yōu)先級較高者,被分配的時刻較早;反之,則相反。式(13)和式(14)表示將一個進(jìn)場航班和一個離場航班相比較,優(yōu)先級較高者,被分配的時刻較早;反之,則相反。

1.4.3跑道約束

式(15)和式(16)說明所有進(jìn)場(離場)航班都被分配到同一條跑道,且只能在該條跑道上降落(起飛)。

(15)

(16)

1.4.4容量約束

式(17)為獲取t+1時刻機(jī)場上空的實際航班數(shù)量,且當(dāng)總數(shù)量大于總?cè)萘繒r停止新增航班;式(18)為獲取t+1時刻機(jī)場場面的實際航班數(shù)量,且當(dāng)總數(shù)量大于總?cè)萘繒r停止新增航班。

(17)

(18)

式中:ΔE(t+1),ΔG(t+1)分別為[t,t+1]時段機(jī)場上空、場面新增的需要降落的航班數(shù)量;L(t+1),T(t+1)分別為[t,t+1]時段需要降落、起飛的航班數(shù)量。

1.4.5尾流間隔、最大交換位置及降落時間窗約束

式(19)說明計算的兩架降落(起飛)航班之間要滿足的時間間隔;式(20)引入了最大移動位置數(shù)(Maximum Position Shifting,MPS),即在考慮到管制員壓力、飛機(jī)性能等條件,以最大程度滿足公平性為原則,以FCFS為基準(zhǔn),航班前后移動的最大位置數(shù)為nMPS;式(21)是由于飛行性能與進(jìn)離場程序會對進(jìn)場航班產(chǎn)生制約,因此每個進(jìn)場航班都只能在其相應(yīng)的時間窗降落。

(19)

(20)

(21)

式中:Tm為航班的進(jìn)場(離場)時間;Smn,Dmn分別為相鄰兩架航班在相同、不同跑道上起降的安全間隔;Eq(m),Lq(m)分別為航班m在優(yōu)化前、優(yōu)化后在隊列中的位置;Te(i),Tl(i)分別為航班的最早、最晚降落時間。

2　合作型協(xié)同進(jìn)化遺傳算法

2.1種群劃分

本文將原始種群劃分為3個子種群,分別為子種群Φ1,Φ2,Φ3。其中Φ1的染色體以跑道約束、尾流間隔、最大移動位置及降落時間窗約束為主要約束條件;Φ2的染色體以跑道約束和航空器所處位置作為主要約束條件,航空器優(yōu)先級不經(jīng)過二次調(diào)配;Φ3的染色體以跑道約束和機(jī)場的容量約束作為主要約束條件;航空器的初始優(yōu)先級為0。

2.2代表個體

協(xié)同進(jìn)化遺傳算法中,一般以各個子種群的最優(yōu)個體為代表個體,但是此種選擇方法可能會導(dǎo)致種群多樣性的損失。本文采用雙代表個體方案,其中一個為最優(yōu)個體,另一個采用隨機(jī)選擇的方法。例如,種群Φ2和種群Φ3各選出兩個代表個體,代表個體間共有4種組合,分別與種群Φ1的個體相結(jié)合,優(yōu)化后得到4個適應(yīng)度值,取其中的最大值為種群Φ1相應(yīng)個體的適應(yīng)度值。

2.3編碼

本文采用實數(shù)制雙重編碼，如表1所示。其中上行碼表示進(jìn)離場航班編號,下行碼表示跑道編號。例如:以1為起始編號的航班代表進(jìn)場航班,以71為起始編號的航班代表離場航班,0,1,2分別代表需要分配的3條跑道。

表1　編碼示例Table1　Exampleofcoding

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

各子種群的適應(yīng)度函數(shù)相同,均取目標(biāo)函數(shù)的倒數(shù),即:

(22)

2.5算法流程

本文采用的合作型協(xié)同進(jìn)化遺傳算法(CCGA)流程如圖1所示。

圖1　CCGA算法流程Fig.1　Algorithmic flow of CCGA

3　算法仿真

采用MATLAB在總延誤時間、空中等待航班架次、地面等待航班架次3個方面對本文所提出的CCGA算法與FCFS算法所得結(jié)果進(jìn)行對比。

假設(shè)相鄰跑道間的運行模式為獨立平行儀表進(jìn)近。以某機(jī)場3條跑道運行情況為例,對某時段50架連續(xù)航班流的運行狀況進(jìn)行仿真,其中進(jìn)場航班21架,離場航班29架,跑道數(shù)r=3,種群規(guī)模為100,令該時段機(jī)場空中的最大容量為8架,地面最大容量為12架。CCGA算法的交叉操作采用單點交叉方式,航班交叉率與跑道交叉率均為0.9,變異率為0.04,最大移動位置數(shù)為3。

引入“時基”概念,將管制規(guī)則中的距離間隔轉(zhuǎn)換為時間間隔。根據(jù)機(jī)場的進(jìn)離場最小安全間隔規(guī)定,不同機(jī)型之間的最小尾流間隔如表2所示。表中,H,L,S分別代表重型機(jī)、中型機(jī)、輕型機(jī)。

表2　不同機(jī)型間的尾流最小間隔Table2　Theminimumwakeintervalsbetweendifferentaircraftmodels　(s)

根據(jù)機(jī)場的實際運行狀況,分別得到的仿真結(jié)果如圖2～圖4所示。圖2為CCGA的收斂過程,算法進(jìn)化至36代趨于收斂。

圖3為傳統(tǒng)意義的FCFS算法與本文的CCGA算法在總耗油量上的對比情況。由于50架航班的總耗油量與開始時耗油量數(shù)值相差過于懸殊,圖形上不利于看出折線的走勢,因此本文只提取前35架進(jìn)行演示,其中進(jìn)場航班15架,離場航班20架。由圖3可知,CCGA算法的總耗油量小于FCFS算法,FCFS算法最終的總耗油量為34 482.44 kg,CCGA算法為30 029.83 kg。

圖3　總耗油量對比Fig.3　Comparison of total fuel consumption

圖4為實時提取的機(jī)場空中及場面的航班數(shù)量狀況?？梢钥闯?進(jìn)場航班在約37 min之后,離場航班在約53 min之后,傳統(tǒng)的FCFS算法進(jìn)場航班架次快速增加,遠(yuǎn)超過實際機(jī)場空域容量;在實際的計算機(jī)仿真中,為了防止累計延誤航班過多產(chǎn)生累計效應(yīng),在進(jìn)場航班數(shù)量超過6架或離場航班超過13架時,已采取部分限流措施,確保航班數(shù)量始終穩(wěn)定在容量限制范圍內(nèi);與FCFS相比,CCGA能夠充分利用場面容量,降低空中等待航班數(shù)量,提高安全性、降低耗油量。

圖4　空中、場面航班架次對比Fig.4　Comparison of aerial and ground flighter

4　結(jié)束語

本文針對多跑道機(jī)場的航班進(jìn)離場序列,提出了一種基于優(yōu)先級調(diào)配的優(yōu)化模型。研究結(jié)果表明,同以往的成果相比,該模型能夠為處于不同階段的航班賦予優(yōu)先級,實現(xiàn)對航班優(yōu)先級的動態(tài)調(diào)配,在一定程度上實現(xiàn)了流量與容量的相互匹配;模型充分利用了機(jī)場容量,與FCFS算法相比降低了因延誤造成的總?cè)加拖?在一定程度上降低了環(huán)境污染,為在實際運行中解決進(jìn)離場航班延誤問題提供了理論支持。

在以下方面仍需要進(jìn)行進(jìn)一步研究:隨著航班架次的增多,計算時間也隨之增加,計算的時效性還有待提高;機(jī)場的空域容量與場面容量的數(shù)值仍然通過經(jīng)驗獲得,因此今后應(yīng)加強(qiáng)對該數(shù)值有直接影響的因素的研究,使模型更加符合機(jī)場實際的運行情況。

[1]Dear R G.The dynamic scheduling of aircraft in the near terminal area[R].Cambridge,Mass.:Flight Transporta-tion Laboratory,Massachusetts Institute of Technology,1976.

[2]Balakrishnan H,Chandran B.Scheduling aircraft landings under constrained position shifting [R].AIAA-2006-6320,2006.

[3]王莉莉,史忠科,張兆寧.機(jī)場著陸排序的一種滑動窗優(yōu)化算法[J].中國民航學(xué)院學(xué)報,2005,22(6):18-21.

[4]Stiverson P,Rathinam S.Heuristics for a runway-queue management problem[J].Journal of Aerospace Engineering,2011,225(5):481-499.

[5]Reza T,Mojtaba Y,Farzad R.Scheduling the sequence of aircraft landings for a single runway using a fuzzy programming approach[J].Journal of Air Transport Management,2012,25:15-18.

[6]王莉莉, 顧秋麗. 平行跑道到達(dá)航班排序問題研究[J]. 飛行力學(xué), 2013, 6(31): 566-569.

[7]Ciesielski V,Scerri P.An anytime algorithm for scheduling aircraft landing times using Genetic algorithms [J].Australian Journal of Intelligent Information Processing System,1997,4(3):206-213.

[8]Ciesielski V,Scerri P.Real time genetic scheduling of aircraft landing times[C]//Proceedings of the IEEE Conference on Evolutionary Computation.Anchorage,USA:IEEE,1998:360-364.

[9]李習(xí)鳳.機(jī)場地面等待策略及優(yōu)化研究[D].北京:北京交通大學(xué),2008.

[10]孔金鳳.航班優(yōu)先級量化研究[J].中國物流與采購,2010,13(18):66-67.

(編輯：李怡)

Dynamic optimization of arrival and departure flights sequence based on priority allocation

WANG Li-li, HU Pan

(College of Air Traffic Management, CAUC, Tianjin 300300, China)

Through allocated methods of variable priority, this paper established a dynamic optimization model for sequence of arrival and departure flights. Firstly, according to fuel consumption and safety factor of aircraft, locating in different arrival and departure stages, initial priorities were distributed for flights. And then, the priorities were deployed the second time considering the number of flights waiting over the airport, the airspace capacity, the surface capacity and the departure demand of the airport. And objective function is minimum total fuel consumption, Cooperative Co-evolutionary Genetic Algorithm (CCGA) was introduced and it adopted a certain method that made a double represents form into a cooperative group which solves the problems, e.g. low species diversity and easy to be premature of traditional genetic algorithm. Simulation results indicate that this model can achieve dynamic allocation of airport flow under airport capacity limits,relieve the pressure on airport airspace and scene operation and reduces total fuel consumption.

CCGA; dynamic optimization; priority allocation; capacity limitation

2015-09-08;

2015-12-11; 網(wǎng)絡(luò)出版時間:2016-02-29 16:37

國家自然科學(xué)基金與中國民用航空局聯(lián)合資助(61179042)；中央高?；究蒲薪?jīng)費資助(ZXH2012L005)

王莉莉(1973-)，女，陜西興平人，教授，博士，主要研究方向為空域規(guī)劃、空中交通優(yōu)化理論。

V355.1

A

1002-0853(2016)04-0090-05