基于优先级调配的进离场航班序列动态优化

王莉莉, 胡畔

(中国民航大学 空中交通管理学院, 天津 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