平行跑道到达航班排序问题研究

王莉莉, 顾秋丽

(中国民航大学 天津市空管运行规划与安全技术重点实验室, 天津 300300)

平行跑道到达航班排序问题研究

王莉莉, 顾秋丽

(中国民航大学 天津市空管运行规划与安全技术重点实验室, 天津 300300)

研究了在终端区空域繁忙的情况下,如何合理地安排到达航班的降落顺序以及同时为到达航班分配跑道，以增加空中交通流量、减少航班延误。考虑航班之间尾流间隔的不同,建立了平行跑道到达航班的排序模型并设计了双重编码的遗传算法,即用一对染色体确定到达航班的跑道分配与降落序号。研究结果表明,与先到先服务算法、先优化到达航班顺序后优化跑道分配算法以及先优化跑道分配后优化到达航班顺序算法相比,该算法优化后的航班排序与跑道分配有效地减少了航班延误。

空中交通管制; 跑道分配; 到达航班排序; 遗传算法

0 引言

随着我国民航事业的不断发展,空中流量迅速增长,终端区空域拥挤问题造成航班延误现象越来越严重,因此终端区内到达航班的排序与调度(Arrival Scheduling and Sequencing,ASS)问题是一个急需解决的问题,也是空中交通流量管理研究的主要问题。

国外对ASS问题的研究比较早,文献[1]用位置交换约束法(CRS)对单跑道着陆航班排序问题进行了研究,然而随着问题规模的增大,CRS求解模型的实时性不好。文献[2-3]证明了旅行商问题(Traveling Salesman Problem,TSP)是累计不对称问题,并将其应用在航班的动态排序中,得到了航班的最佳着陆次序,但这样可能会使航班的着陆次序变化较大,增加了管制员的负荷。文献[4]通过运用排队论方法,采用离散事件仿真技术来研究多跑道航班动态着陆问题,假设到达航班流服从泊松分布,得出航班到达时间服从指数分布。上述对航班排序的研究主要侧重在为动态到达的航班分配降落跑道,但未在分配跑道的研究中考虑尾流间隔的优化。国内对ASS问题的研究起步较晚,文献[5]将模糊综合评判方法应用于单跑道到达航班排序,综合考虑了航班排序中的各种因素,但模糊综合评判法隶属函数受实际问题影响较大,计算复杂。文献[6-7]运用遗传算法求解了单跑道情况下到达航班的排序问题。文献[8]提出了混合人工鱼群算法,并将其应用在单跑道和多跑道着陆航班的排序中,该算法有效地减少了航班的延误,但当航班数量较多时其求解效率较差。

本文建立了平行跑道到达航班的排序模型。由于该问题是典型的TSP组合优化问题,同时也是难解的NP完全问题,采用常规的求解算法很难满足航班排序实时性的要求。因此,本文设计了基于双重编码的遗传算法对平行跑道到达航班的排序模型进行求解,求解时用一对染色体将航班着陆序号与跑道号对应起来同时优化跑道的分配与航班的着陆顺序,还采用了精英策略以及进化逆转操作,大大提高了遗传算法的求解效率,最后通过仿真验证了其可行性。

1 问题的提出

具有平行跑道的机场终端区平面机构示意图如图1所示。假设终端区内只考虑到达的航班流,航班按照仪表进场程序从不同的航路进入终端区准备着陆,在进场航线交叉点处按照着陆时间先后顺序排成队列。

图1 机场终端区平面结构示意图Fig.1 Diagram of an airport terminal area

由图1可知,终端区空域按起始调度界限与终止调度界限的定义可以分为三个部分。当到达航班穿越设定的起始调度界限时,用排序算法根据到达航班的预计到达时间、航班类型等进行排序并分配其降落的跑道号;当到达航班穿越终止调度界限后,由算法分配给航班着陆的到达时间和跑道将确定,不再改变。两个界限间的时域即为航班动态排序区。

空中交通管制的目的是为了保证航班的安全,使航班与航班之间具有一定的安全间隔。但目前的空中交通管制主要是基于距离间隔保证航班飞行的安全。为了保证流量管理的精确性,本文引入了时基的概念,把飞机的距离间隔转化为时间间隔。根据国际民航组织(ICAO)对无风条件下不同机型的最小尾流间隔作出的规定,通过计算可以得到不同机型间的最小安全间隔时间[9](单位:s),如表1所示。

表1 不同机型间的尾流最小间隔(Sij) Table 1 Minimum wake flow separation between different types of aircraft

从表1可以看出,不同机型间的尾流最小间隔是不同的并且是非对称的,本文基于位置调换法(Position Shifting,PS)利用着陆时不同机型间不同的尾流间隔来调换到达航班的位置顺序以及优化航班的跑道分配。

2 到达航班排序模型的建立

假设某一具有多跑道繁忙机场的终端区航班架数为N,表示为f=(1,2,…,N);设航班i在跑道r的预计降落时间为ETi,实际降落时间为ATir;r=(1,2,…,R)为机场跑道数目;g(i)表示到达航班队列优化后第i个位置的航班;xir为航班对跑道的变量,yij为航班对航班的变量。令:

目标函数以使总的延迟时间最小为原则。目标函数为:

(1)

考虑到排序过程中的各种限制,给出模型的约束条件如下:

(i=1,2,…,N;r=1,2,…,R)

(2)

ATjr-ATir≥Sij

(i,j=1,2,…,N(j>i);r=1,2,…,R)

(3)

ATjr-ATi,r+1≥Dij

(i,j=1,2,…,N(j>i);r=1,2,…,R)

(4)

|i-z|≤MPS,g(i)=z

(i,z=1,2,…,N)

(5)

式(2)说明每架航班都被分配一条跑道降落且每架航班只能降落在一条跑道上;考虑航班之间的尾流间隔要求,式(3)说明前后两架航班i和j在同一跑道上降落时之间的间隔要大于等于Sij,式(4)说明前后两架航班i和j在不同跑道上降落时之间的间隔要大于等于Dij; 式(5)考虑飞机性能、管制员的负荷以及航班先到先服务的公平性原则,引入了最大移动位置数(Maximum Position Shifting,MPS),即以FCFS航班顺序为基准,航班向前或向后移动的最大位置数为MPS。由以上可知yij=yji(i,j=1,2,…,N;i≠j)。

令Tdel=ATir-ETi,当航班i的ATir≤ETi时,Tdel=0,即无延迟。当航班i的ATir>ETi时,Tdel=ATir-ETi。若前后两架航班使用同一条跑道时(i-1为i的前一架航班),则航班的实际到达时间为ATir=max(ATi-1,r+Si,i-1,ETi);若前后两架航班使用不同跑道时,则航班的实际到达时间为ATir=max(ATi-1,r+Di,i-1,ETi)。

3 遗传算法的设计

(1)编码

为了与平行多跑道运行方案相匹配,本文采用的编码方式为二重结构编码。每个染色体由上行码和下行码组成。上行码表示到达航班的降落次序,下行码表示航班降落的跑道号,上下行码都以整数形式进行编码。以两条跑道、7架航班为例,编码方式如表2所示。

表2 二重结构编码方式Table 2 Dual coding mode

(2)种群的初始化

在完成染色体编码以后,必须产生一个初始种群作为起始解,本算法使用了一定比例的FCFS序列,这样保证了在最坏情况下,优化结果优于FCFS序列。

(3)适应度函数

(i,j=1,2，…,N(j>i);r=1,2,…,R)

(4)选择操作

选择操作即从种群中以一定概率选择个体添加到新群体中,个体被选中的概率与其适应度值有关,个体适应度值越大,被选中的概率也越大。

(5)交叉操作

以部分映射杂交的方式确定交叉操作的上行码,子个体的下行码值根据其父代个体中下行码与上行码的对应关系来确定。

(6)变异操作

变异操作采取在父代染色体中随机选取两个位置并将其对换。

(7)进化逆转操作

为提高遗传算法局部的搜索能力,在选择、交叉、变异之后采用了连续多次的进化逆转操作。这里的“进化”是指逆转算子的单方向性,即只有经过逆转后,适应度值有提高的个体才被留下来,否则逆转无效。并且逆转操作只在航班允许的MPS范围内进行。

进化逆转操作采取在父代染色中随机选取两个位置,进行逆转。如选取位置四和位置七进行逆转操作。

4 算法仿真

根据《中国民用航空总局令(第123号)平行跑道同时仪表运行管理规定》第七条所述,平行双跑道同时仪表运行按照跑道用于进近使用方式分为独立平行仪表进近、相关平行仪表进近两种模式。本文设定机场的跑道数r=2,当平行双跑道使用相关平行仪表进近时,不同跑道上航班之间尾流间隔与单跑道类似,因此将两条平行跑道设置为独立的运行状态,即航班在不同跑道上降落的时间间隔Dij=0,以40架航班为例对算法进行了验证。遗传算法的种群大小为100,最大进化代数为50,航班交叉概率pcf=0.9,跑道交叉概率pcr=0.9,航班变异概率pcf=0.05,跑道变异概率pcr=0.05,MPS=3。

到达航班遗传算法的收敛过程如图2所示。由图可知,本文的遗传算法采用了进化逆转操作,改善了遗传算法的局部搜索能力,加快了收敛速度。

经本文算法优化后的航班总延误时间为8 681 s,先到先服务(FCFS)算法、先优化到达航班顺序后优化跑道分配算法以及先优化跑道分配后优化航班排序算法的总延误时间分别为9 987 s,10 534 s,8 709 s,比较结果如图3所示。由仿真结果可知,同时优化到达航班的排序和跑道的分配可以有效减少航班延误时间,提高空中交通管制效率。

图2 遗传算法收敛过程Fig.2 Convergence process of GA

图3 四种算法延误时间的比较Fig.3 Comparison of delay times for four algorithms

5 结束语

本文讨论了终端区到达航班的排序问题,建立了平行跑道终端区到达航班的排序模型,并设计了遗传算法进行求解。采用了精英策略以及进化逆转操作,使其搜索最优解的能力更强,能快速寻找到所需的最优解。本文所设计的遗传算法与先到先服务

(FCFS)算法、先优化到达航班顺序后优化跑道分配算法以及先优化跑道分配后优化航班排序算法相比,不仅有效地减少了航班延误时间,并且实时性更好,提高了空中交通管制效率,能够在一定程度上缓解繁忙机场终端区的拥挤问题。

[1] Dear R G.The dynamic scheduling of aircraft in the near terminal area[R].FTL R76-9,1976.

[2] Psaraftis H N.A dynamic programming approach to the aircraft sequencing problem[R].FTL R78-4,1978.

[3] Bianco L,Rinadi G,Ricciardelli S,et al.Scheduling tasks with sequence-dependent processing times[J].Naval Research Logistics,1988,35(2):177-184.

[4] Bolender M A,Slater G L.Cost analysis of the departure-en route merge problem[J].Journal of Aircraft,2000,37(1):23-29.

[5] 徐肖豪,黄宝军.终端区飞机排序的模糊综合评判方法研究[J].航空学报, 2001,22(3):259-261.

[6] 陶冶,白存儒.基于遗传算法的航班动态排序模型研究[J].中国民航飞行学院学报,2005,5(16):3-7.

[7] 程晓航,薛惠锋,洪鼎松,等.进港飞机调度的精华自适应遗传算法设计[J].交通与计算机,2006,24(6):91-94.

[8] 王飞,徐肖豪.终端区飞机排序的混合人工鱼群算法[J].交通运输工程学报,2008,8(3):68-72.

[9] Dear R G,Sherif Y S.The dynamic scheduling of air-craft in high density terminal areas[J].Microelectron Reliab,1989,29(5):743-749.

Parallelrunwayarrivalaircraft-sequencingoptimization

WANG Li-li, GU Qiu-li

(Tianjin Key Lab of Operation Programming and Safety Technology of Air Traffic Management, CAUC, Tianjin 300300, China)

This paper studies on how to properly sequence the arrival aircraft and assign a runway for them in the case of air traffic congestion in the terminal area so as to increase the air traffic flow and reduce the flights’ delay. A model to solve the problem of parallel runway arrival aircraft-sequencing was set up and the genetic algorithm (GA) of dual code was designed according to the aircraft wake turbulence separation requirements. GA of dual code was that an arrival flight’s sequencing and landing runway was determined by a pair of chromosomes. Compared with the algorithms of first come first service(FCFS), first optimize arrival flights’ sequencing and then the assignment of runways for flights, first optimize the assignment of runways for flights and then the arrival flights sequencing, it is proved the provided model can effectively reduce the flights’ delay by actual data computation.

air traffic control; runway assignment; arrival aircraft-sequencing; genetic algorithm

V355

A

1002-0853(2013)06-0566-04

2013-03-18;

2013-06-04; < class="emphasis_bold">网络出版时间

时间:2013-10-22 14:16

国家自然科学基金委员会与中国民用航空局联合资助(61179042);中央高校基本科研业务费资助(ZXH 2012L005)

王莉莉(1973-),女,陕西兴平人,副教授,博士,研究方向为空中交通管理、人为因素等;

顾秋丽(1988-),女,辽宁锦州人,硕士研究生,研究方向为空中交通管理中的排序问题。

(编辑：姚妙慧)