基于優先級調配的進離場航班序列動態優化

王莉莉, 胡畔

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

?

基于優先級調配的進離場航班序列動態優化

王莉莉, 胡畔

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

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

合作型協同進化遺傳算法; 動態優化; 優先級調配; 容量限制

0　引言

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

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

本文將處于不同階段的航班賦予相應的優先級,并考慮機場空域容量及場面運行容量的限制,根據實時容量、流量狀態對優先級進行二次調配,實現優先級的動態可變。

1　基于優先級調配的優化模型

1.1優先級調配模型原理

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

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

1.2目標函數

以航班總燃油量為目標函數,其表達式為:

(1)

1.3決策變量

決策變量的定義如下:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

1.4約束條件

1.4.1優先級賦值

初始優先級賦值:

(9)

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

優先級二次調配:為保證安全,對處在A,C,D三個階段的航班進行優先級調配。

(10)

(11)

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

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

1.4.2優先級約束

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

(12)

(13)

(14)

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

1.4.3跑道約束

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

(15)

(16)

1.4.4容量約束

式(17)為獲取t+1時刻機場上空的實際航班數量,且當總數量大于總容量時停止新增航班;式(18)為獲取t+1時刻機場場面的實際航班數量,且當總數量大于總容量時停止新增航班。

(17)

(18)

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

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

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

(19)

(20)

(21)

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

2　合作型協同進化遺傳算法

2.1種群劃分

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

2.2代表個體

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

2.3編碼

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

表1　編碼示例Table1　Exampleofcoding

2.4適應度函數

各子種群的適應度函數相同,均取目標函數的倒數,即:

(22)

2.5算法流程

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

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

3　算法仿真

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

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

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

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

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

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

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

圖4為實時提取的機場空中及場面的航班數量狀況。可以看出,進場航班在約37 min之后,離場航班在約53 min之后,傳統的FCFS算法進場航班架次快速增加,遠超過實際機場空域容量;在實際的計算機仿真中,為了防止累計延誤航班過多產生累計效應,在進場航班數量超過6架或離場航班超過13架時,已采取部分限流措施,確保航班數量始終穩定在容量限制范圍內;與FCFS相比,CCGA能夠充分利用場面容量,降低空中等待航班數量,提高安全性、降低耗油量。

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

4　結束語

本文針對多跑道機場的航班進離場序列,提出了一種基于優先級調配的優化模型。研究結果表明,同以往的成果相比,該模型能夠為處于不同階段的航班賦予優先級,實現對航班優先級的動態調配,在一定程度上實現了流量與容量的相互匹配;模型充分利用了機場容量,與FCFS算法相比降低了因延誤造成的總燃油消耗,在一定程度上降低了環境污染,為在實際運行中解決進離場航班延誤問題提供了理論支持。

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

[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].中國民航學院學報,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]王莉莉, 顧秋麗. 平行跑道到達航班排序問題研究[J]. 飛行力學, 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]李習鳳.機場地面等待策略及優化研究[D].北京:北京交通大學,2008.

[10]孔金鳳.航班優先級量化研究[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; 網絡出版時間:2016-02-29 16:37

國家自然科學基金與中國民用航空局聯合資助(61179042)；中央高校基本科研經費資助(ZXH2012L005)

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

V355.1

A

1002-0853(2016)04-0090-05