特殊情况下的进离场航班排序问题研究

王莉莉，顾秋丽

（中国民航大学 空中交通管理学院，天津 300300）

1 引言

随着我国经济的快速发展，空中交通流量不断增加，使得空域资源紧缺，严重影响航班的正点到达.因此优化航班的起降顺序及跑道分配问题是提高空域利用率的有效途径，也是空中交通流量管理研究的主要问题.

目前，解决航班排序问题(Aircraft Sequencing Problem,ASP)最常用的方法是采用先到先服务（First Come First Service，FCFS）方法.国外学者对航班排序问题（ASP）研究如下.2003年，Kari Andersson[1]根据NASA提出的改进空中交通流量的决策支持工具-协同进场规划（CAP）进行了优化方法分析，并验证了进场排序程序能够改善航空运输系统.2006年，Aditya P.Saraf[2]提出了一种对拥挤机场进场航班的组合优化方法，但其未考虑多跑道航班的优化分配问题，人为地规定了航班的降落跑道.2009年，Gautam Gupta[3]采用了一种混合整数线性规划模型求解离场航班的排序问题，但由于受限制约束问题的影响，求解模型的实时性不好.2010年，Andrea D’Ariano[4]将繁忙机场的进离场航班排序问题比作旅行商问题，并采用启发式算法进行求解，仿真证明算法只可以快速找到可行解.国内也有许多学者对ASP问题进行了研究.杨军利[5]等把飞机的排序问题等价于带有准备好时间的渐增周游店员问题,采用了一种近似算法，但是近似程度较低，很难求出最优解.程晓航[6]运用遗传算法求解了单跑道情况下到达航班的排序问题.王飞[7]提出了混合人工鱼群算法并将其应用在单跑道和多跑道着陆航班的排序中，该算法有效地减少了航班的延误，但当航班数量较多时其求解效率较差.

具有平行跑道的机场终端区进离场平面结构示意图如图1所示.进离场航班按照仪表进场/离场程序从不同的航路进入/离开终端区准备着陆/起飞，在进/离场航线交叉点处按照着陆/起飞时间先后顺序排成队列.

由图1可知,进离场航班所经过的终端区空域按起始调度界限与终止调度界限的定义可以分为三个部分.对于进场航班，起始调度界限是一个空间界限，是航班进入进近管制区的界限，终止调度界限则根据特定的距离着陆的时间来确定，终止调度界限也叫动结区界限.然而对于离场航班，起始调度界限则为开始在停机坪做起飞准备,终止调度界限则为航班已进入跑道起飞.起始调度界限与终止调度界限间的时域即为航班动态排序区，在这两个界限之间用排序算法根据航班的预计起飞时间、预计降落时间、航班类型等对航班的起飞与降落顺序进行排序及分配跑道.

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

空中交通管制的目的是为了保证航班的安全，使航班与航班之间具有一定的安全间隔.但目前的空中交通管制主要是基于距离间隔保证航班飞行的安全.为了保证流量管理的精确性，因此本文引入了时基的概念，把飞机的距离间隔转化为时间间隔.根据白云机场进离场距离规定转化为最小安全时间间隔，如表1所示.

本文考虑了机场实际运行中货机只能在某条固定跑道起降的情况，建立了进离场航班的排序模型.由于该问题是典型的TSP组合优化问题，同时也是难解的NP完全问题，采用常规的求解算法很难满足航班排序实时性的要求.本文设计了基于双重编码的遗传算法对平行跑道进离场航班的排序模型进行求解.求解时用一对染色体将航班进离场序号与跑道号对应起来同时优化跑道的分配与进离场航班的起降顺序，并采用了排列编码法区分了载客与载货航班的不同，同时也采用了精英策略及进化逆转操作，大大提高了遗传算法的求解效率.最后通过仿真验证其可行性.

表1 不同机型间的尾流最小间隔（Si j）Table 1 Minimum wake turbulence separation between different aircraft

本文考虑了机场实际运行中货机只能在某条固定跑道起降的情况，建立了进离场航班的排序模型.由于该问题是典型的TSP组合优化问题，同时也是难解的NP完全问题，采用常规的求解算法很难满足航班排序实时性的要求.本文设计了基于双重编码的遗传算法对平行跑道进离场航班的排序模型进行求解.求解时用一对染色体将航班进离场序号与跑道号对应起来同时优化跑道的分配与进离场航班的起降顺序，并采用了排列编码法区分了载客与载货航班的不同，同时也采用了精英策略及进化逆转操作，大大提高了遗传算法的求解效率.最后通过仿真验证其可行性.

2 模型算法

2.1 特殊情况下进离场航班排序模型的建立

假设某一具有多跑道繁忙机场的终端区航班架数为N，包括载客航班数Nk，载货航班数Nh，并且 Nk∪Nh=N,Nk∩Nh=Φ ，表示为 f=(1,2,...,Nk,...,N)；设航班i在跑道r的预计降落时间为ETi,实际降落时间为ATi；r=(1,2,...,R)为机场跑道数目；g(i)表示到达航班队列优化后第i个位置的航班；xir为航班对跑道的变量，yij为航班对航班的变量.

定义决策变量：

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

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

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

令 Tdelay=ATi-ETi，当航班 i的 ATi≤ETi时，令 Tdelay=0，既无延迟.当航班 i的 ATi＞ETi时，Tdelay=ATi-ETi.若前后两架航班使用同一条跑道时（i-1为i的前一架航班），则航班的实际到达（起飞）时间为ATi=max(ATi-1+Si,i-1,ETi)；若前后两架航班使用不同跑道时，则航班的实际到达（起飞）时间为ATi=max(ATi-1+Di,i-1,ETi).

2.2 遗传算法的设计

(1)编码.

为了与平行多跑道运行方案相匹配，本文采用的编码方式为二重结构编码.每个染色体由上行码和下行码组成.上行码表示进离场航班的起降次序,下行码表示进离场航班起降的跑道号.上行码采用排列编码方式进行编码，排列编码也叫序列编码，是针对一些特殊问题的特定编码方式.如航班序列中有两种航班类型，分别为载客航班和载货航班，则将某个终端区内的进离场航班按初始进离场时刻表的时间顺序进行编码，并在同一编码中同时包含两种类型的进离场航班.如载客航班的个数为30，载货航班的个数为6，则编码为1，2，3，31，4，33，5，...,30，36.编码中小于等于30的个体代表载客的进离场航班，大于30的个体代表载货的进离场航班，以两条跑道、36架航班为例，构成如表2所示的染色体.

表2 二重结构编码方式Table 2 The way of dual coding

(2)种群的初始化.

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

(3)适应度函数.

适应度函数表示为

(4）选择操作.

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

(5）交叉操作.

以部分映射杂交的方式确定交叉操作的上行码,子个体的下行码采用随机方式进行交叉.但对于载货航班,如果起降的跑道号与实际要求相符，则该个体不进行交叉操作.

(6）变异操作.

变异操作采取在父代染色体中随机选取两个位置并将其对换进行变异.但对于载货航班，如果起降的跑道号与实际要求相符，则该个体不进行变异.

(7）进化逆转操作.

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

进化逆转操作采取在父代染色中随机选取两个位置，进行逆转.如选取位置四和位置七进行逆转操作，但对于载货航班并且其起降的跑道号与实际要求相符的个体不进行逆转.

进化逆转后：

3 算法仿真

根据《中国民用航空总局令（第123号）平行跑道同时仪表运行管理规定》第十二条所述，平行跑道同时仪表运行按照第七条所述的四种运行模式（独立平行仪表进近、相关平行仪表进近、独立平行离场、隔离平行运行等四种模式）的不同组合，也可以分为半混合运行和混合运行.本文根据广州白云机场的运行情况，令跑道数r=2,平行跑道使用的方式为混合运行的模式.以某时段36架连续航班流为例对算法进行了验证，其中航班序号为1-30的航班为正常的载客航班，对起飞和降落的跑道没有要求；航班序号31-36号航班为载货航班，由于实际运行的需要，他们只能在规定的跑道上进行起降，本文令载货航班只能在02号跑道上起飞与降落.本文遗传算法的种群大小为100，最大进化代数为50，航班交叉概率 pcf=0.9,跑道交叉概率 pcr=0.9，航班变异概率 pcf=0.05，跑道变异概率 pcr=0.05，MPS=3.

考虑机场实际运行中对载货航班起降跑道有特殊要求的进离场航班的遗传算法的收敛过程如图2所示.本文的遗传算法采用了进化逆转操作，改善了遗传算法的局部搜索能力，加快了收敛速度.经本文算法优化后，对跑道有规定的31-36号载货进离场航班都在规定的02号跑道上进行了起降，优化后的排序结果与FCFS算法的结果对比如图3所示.优化后的航班总延误时间为1912秒，FCFS算法总延误时间为2468秒，比较结果如图4所示.由仿真结果可知，本文所建立的模型和算法能够有效解决实际运行中对载货航班的跑道限制要求，31-36号进离场航班中不符合跑道要求的航班在优化后都在规定的跑道上进行了起降，并且以总的延迟时间为目标对1-36号航班的起降顺序进行了合理地优化，大大减少航班延误的总时间，提高了空中交通管制效率.

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

图3 GA与FCFS排序结果比较Fig.3 Comparison of FCFS and GA algorithm’s sequencing

图4 FCFS与GA延误时间对比Fig.4 Comparison of FCFS and GA algorithm’s delay time

4 研究结论

本文讨论了终端区进离场航班的排序问题，并同时考虑了机场实际运行中对载货航班起降跑道的特殊限制，建立了载货航班只能在规定跑道上进行起降的进离场航班的排序模型，并设计了双重编码的遗传算法进行求解，合理地安排了进离场航班的起降顺序，以及同时为进离场航班分配跑道.遗传算法中采用了精英策略及进化逆转操作，使其搜索最优解的能力更强,能够快速寻找到所需的最优解.仿真结果证明了模型和算法的有效性，以36架连续航班流为例，本文所设计的遗传算法与先到先服务算法相比，能有效地减少航班延误总时间556 s，并且实现了特殊航班只能在规定跑道起降的要求，具有实际意义，提高了空中交通管制效率，能够在一定程度上缓解繁忙机场终端区的拥挤问题.

[1]Kari Andersson,William Hall,Stephen Atkins,et al.Opti⁃mization-based analysis of collaborative airport arrival planning[J].Transportation Science,2003,37(4):422-433.

[2]Aditya P Saraf,Gary L Slater.An efficient combinatorial optimization algorithm for optimal scheduling of aircraft arrivals at congested airports[C]//Aerospace Conference,IEEE,2006.

[3]Gautam Gupta,Waqar Malik,Yoon C Jung.A Mixed in⁃teger linear program for airport departure scheduling[C]//Hilton Head,South Carolina:9th AIAA Aviation Technol⁃ogy,Integration,and Operations Conference(ATIO),2009.

[4]Andrea D’Ariano,Paolo D’Urgolo,Dario Pacciarelli,et al.Optimal sequencing of aircrafts take-off and landing at a busy airport[C]//Madeira Island,Portugal:201013th International IEEE,Annual Conference on Intelligent Transportation Systems,2010.

[5]杨军利,方群,向小军.终端区飞机排序的规划模型和算法研究[J].飞行力学，2005,23（2）：77-80.[YANG J L,FANG Q,XIANG X J.Research on the scheduling model and algorithm for aircraft sequencing problem in TMA[J].Flight Dynamics,2005,23（2）：77-80.]

[6]程晓航，薛惠锋，洪鼎松，等.进港飞机调度的精华自适应遗传算法设计[J].交通与计算机,2006,24(6):91-94.[CHENG XH,XUE HF,HONG DS,et al.Design of elit⁃ist adaptive genetic algorithm in arrival aircrafts sched⁃uling[J].Transport and Computer,2006,24(6):91-94.]

[7]王飞,徐肖豪.终端区飞机排序的混合人工鱼群算法[J].交通运输工程学报,2008,8(3):68-72.[WANG F,X U XH.Mixed artificial fish school algorithm of aircraft se⁃quencing in terminal area[J].Journal of Traffic and Transportation Engineering,2008,8(3):68-72.]