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

王莉莉, 胡畔

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

?

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

王莉莉, 胡畔

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

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

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

0　引言

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

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

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

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

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

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

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

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

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

(1)

1.3決策變量

決策變量的定義如下:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

1.4約束條件

1.4.1優(yōu)先級(jí)賦值

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

(9)

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

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

(10)

(11)

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

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

1.4.2優(yōu)先級(jí)約束

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

(12)

(13)

(14)

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

1.4.3跑道約束

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

(15)

(16)

1.4.4容量約束

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

(17)

(18)

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

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

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

(19)

(20)

(21)

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

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

2.1種群劃分

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

2.2代表個(gè)體

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

2.3編碼

本文采用實(shí)數(shù)制雙重編碼，如表1所示。其中上行碼表示進(jìn)離場航班編號(hào),下行碼表示跑道編號(hào)。例如:以1為起始編號(hào)的航班代表進(jìn)場航班,以71為起始編號(hào)的航班代表離場航班,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在總延誤時(shí)間、空中等待航班架次、地面等待航班架次3個(gè)方面對(duì)本文所提出的CCGA算法與FCFS算法所得結(jié)果進(jìn)行對(duì)比。

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

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

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

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

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

圖3　總耗油量對(duì)比Fig.3　Comparison of total fuel consumption

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

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

4　結(jié)束語

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

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

[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ī)場著陸排序的一種滑動(dòng)窗優(yōu)化算法[J].中國民航學(xué)院學(xué)報(bào),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í)量化研究[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ò)出版時(shí)間:2016-02-29 16:37

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

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

V355.1

A

1002-0853(2016)04-0090-05