基于历史雷达轨迹分析的4D航迹规划

基于历史雷达轨迹分析的4D航迹规划*

马广辉张军峰▲王菲陈强

(南京航空航天大学民航学院南京211106)

摘要航空器4D航迹规划可有效解决我国当前面临的航班延误问题，并且能够加速空管自动化与智能化技术的应用与实施。因此提出了1种基于历史雷达轨迹分析的4D航迹规划方法：首先利用动态时间规整与层次聚类算法对进场历史雷达轨迹进行聚类分析,复现盛行交通流,继而根据盛行交通流和标准进场航线完成水平路径设计；其次对进场历史雷达数据统计分析，确定各进场航路点的高度/速度范围，然后基于航空器在终端区尽量保持高高度飞行的原则完成高度剖面设计；再次为使航空器可以按规定时间到达指定航路点，根据各航路点的速度范围设置合理参数，通过对参数优化调整完成所需速度剖面的设计。最后以上海浦东国际机场VMB进场场景为例进行仿真验证，平均误差为2.5s，误差率为1.9‰ 。仿真结果表明基于历史雷达轨迹分析的4D航迹规划方法可有效实现航班的准点降落，从而减少航班延误,提高终端空域运行效率。

关键词智能交通；4D航迹规划；聚类；动态时间规整；空中交通管制

中图分类号：V355文献标志码：A

收稿日期：2014-05-19修回日期：2015-07-21

基金项目*国家自然科学(批准号：71401072)、江苏省自然科学

作者简介：第一马广辉(1988-)，硕士研究生.研究方向：航迹规划及决策支持.E-mail：347335153@qq.com

A 4D Trajectory Planning method based

on Historical Radar Tracks of Air Traffic

MA GuanghuiZHANG JunfengWANG FeiCHEN Qiang

(CollegeofCivilAviation,NanjingUniversityofAeronauticsandAstronautics,Nanjing211106,China)

Abstract:4D trajectory planning can solve flight delay problems and accelerate the implementation and application of automation and intellectualization in Air Traffic Control. 4D trajectory planning based on analysis of historical radar tracks was proposed. Historical radar tracks were clustered and analyzed by Dynamic Time Warping algorithm and Hierarchical clustering. Horizontal paths were designed based on the reproduced traffic flow and standard arrival routes. The ranges of altitudes and speeds of aircrafts were determined by statistical analysis of historical radar tracks. The altitude profiles were designed based on the principle of aircrafts should keeping high altitude as much as possible in the terminal area. Finally, the speed profiles which satisfy the scheduled time of arrivals were designed based on optimized parameters. Arrival flights to Shanghai Pudong Airport were selected as a simulation scenario as a result of the mean error of 2.5 s and the margin of error of 1.9‰. The simulation result indicates that the proposed 4D trajectory planning method can achieve flights landing punctuality, reduce flight delays and improve the efficiency of the terminal airspace.

Key words:intelligent transportation; 4D trajectory planning; clustering; Dynamic Time Warping; air traffic control

▲通信作者：张军峰(1979-)，博士，副教授.研究方向：空中交通管制自动化.E-mail：zhangjunfeng@nuaa.edu.cn

0引言

近年来，民航运输业的高速发展极大地提高了出行效率。然而随着空中交通量的持续增长，导致终端空域拥堵，流量控制频繁，安全运行压力倍增，大面积航班延误等一系列问题。于是，冲突探测与解脱、进离场排序与调度等空管自动化与智能化方法[1]成为空中交通管理领域的研究重点，而民用航空器4D航迹规划是确保上述方法有效实施的关键因素。

航迹规划是在综合考虑飞行器到达时间、油耗、威胁，以及飞行区域等因素的前提下，规划最优飞行航迹，以保证圆满完成飞行任务[2]。航迹规划在无人机领域的研究成果颇丰[3-4]，具体算法主要包括最优式算法，启发式算法和随机型算法。笔者主要研究航迹规划在民航智能空中交通管理领域的研究与应用，因为航迹规划不仅可以为冲突解脱提供有效路径，还能够根据进离场调度产生的优化时间生成相应4D航迹，以确保航空器安全准时到达指定地点，从而减少航班延误，提高运行效率。

对民航空中交通管理领域航迹规划的研究，美国国家航空航天局(NASA)[5-6]提出了终端空域航空器导引算法，自飞机当前位置开始生成飞行轨迹，包括航向、速度、高度和时间，并预先设定的时间在指定航路点终止。我国王大海等[7]研究了航空器在终端空域运行时高度/速度剖面生成算法，结合水平轨迹，设计了3D飞行剖面与4D导航指令。上述航迹规划方法，计算效率高，但是以上方法未充分考虑终端空域实际运行，水平进场路径设计单一。当前在大流量终端区，管制员在指挥大流量航班降落时，为保证飞机的无冲突安全着陆会实施复杂的雷达引导，导致部分航班的飞行轨迹偏离标准的进场航线，因此单一的水平进场路径已不能适应当前日益增加的空中交通流量，亟需设计多条合理水平进场路径。大数据挖掘在空中交通管理领域的应用研究可以辅助水平进场路径的设计，从海量庞杂的历史雷达轨迹中提取盛行交通流，可以为4D航迹规划中水平轨迹的设计提供参考。对于历史雷达轨迹的分析，Agrawal等[8]提出对序列数据库进行有效的相似性搜索算法，王超等[9]提出基于航迹聚类的终端区进场程序管制适用性分析方法。以上方法都是基于欧式距离对航迹进行聚类，传统的欧氏距离方法计算简便，但不能有效地求得2条航迹的相似度，使得两条空间形状相似的航迹可能无法聚类，从而无法准确复现盛行交通流。

为解决上述问题，笔者在充分考虑进场航空器实际运行的前提下，首先利用动态时间规整算法(DTW)[10]和层次聚类方法[11]对历史雷达轨迹进行聚类分析，此种方法可以有效求得2条航迹的相似度，使得空间形状相似的航迹有效聚类，进而可以准确复现盛行交通流，为设计多条合理水平进场路径提供参考；其次统计各航路点的速度高度范围，在水平进场路径的基础上设计满足到达时刻要求的速度高度剖面；最后，以上海浦东国际机场VMB进场场景为例进行仿真验证。

1历史雷达轨迹分析

由于笔者研究航迹聚类的主要目的是找出盛行交通流，为终端空域进场航迹规划提供水平路径参考，因此着力点主要集中在历史雷达轨迹的空间形状上。应用欧氏距离是进行历史雷达轨迹聚类的常用方法，然而，这种方法的弊端是：①2条历史雷达轨迹如果在起始阶段有小的偏差，就会在后续阶段导致非常大的计算偏差，致使形状非常相似的轨迹不能聚到一类；②历史雷达轨迹的长度可能并不相等，而且不同历史雷达轨迹可能存在时间轴上的位移。在上述情况下，传统的欧氏距离无法有效地求得2条轨迹之间的距离(或者相似性)，而动态时间规整(DTW)算法可有效解决此类问题。

动态时间规整算法是1种衡量2个时间序列相似度的方法。本文中的航迹分别可视作时间序列，如图1所示，上下2条实线代表2条航迹，2条航迹之间的虚线代表2条航迹之间相似的点。DTW使用所有这些相似点之间的距离和，称之为归整路径距离，来衡量2条航迹之间的相似性。

图1　航迹规整示意图 Fig.1　Schematic diagram of trajectory warping

设需要计算相似度的2条航迹为X与Y，长度分别为|X|和|Y|，规整路径的形式为

W=w1,…,wk,…,wKk∈{1,2,…K}

(1)

其中：max(|X|，|Y|)≤K≤|X|+|Y|，wk的形式为(i,j),i为X中i坐标； j为Y中j坐标。

(2)

式中：i≤i′≤i+1,j≤j′≤j+1。

最后得到距离最短的1个规整路径

(3)

式中Dist(i,j)为2点间的欧式距离。

基于上述的动态时间规整算法，并结合层次聚类能够设计多条水平进场路径，以满足大流量航班流的运行需求。

通过分机型统计雷达轨迹经过每个航路点的高度/速度，并加以整理分析，进而可以确定出每类机型在各航路点的高度/速度范围。

2速度剖面设计

由于航空器在进场时基本是按照既定的飞行路径运行，即标准仪表进场航线(STAR)。因此可以根据飞经各航路点坐标，计算各相邻航路点的距离及进场飞行的总距离。

当航空器飞行的高度剖面在合理范围内，且航空器所飞行的水平路径已确定时，航空器的到场时刻由航空器的地速决定，不同的速度剖面对应不同的到场时刻。显然，最大速度剖面对应最短到达时间；最小速度剖面对应最长到达时间；当所要求的到场时间介于最长和最短到达时间之间时，总有1个合理的速度剖面与之相对应，如图2所示。

图2　速度剖面设计示意图 Fig.2　Schematic diagram of speed profile design

以航路点i-1与航路点i之间的航段进行说明，其中最大速度剖面中v(i-1)max，vimax分别代表第i-1航路点和第i航路点的最大速度， dicmax为以速度v(i-1)max飞过的距离，diamax为由速度v(i-1)max减速到速度vimax飞过的距离，最小速度剖面与之类似；动态速度剖面中v(i-1)、vi分别代表第i-1、第i航路点的速度， di1为以速度v(i-1)飞过的距离，di2为以速度vi飞过的距离，dia为由速度v(i-1)减速到速度vi飞过的距离，D表示航路点i-1与i之间航段距离。

本节主要针对上述分析，优化设计能够满足给定到达时间的速度剖面。

2.1最大最小速度剖面

由于进场飞行阶段总体而言是减速运行，因此后1航路点的速度总是小于前1航路点的速度，为获得最大速度剖面，每1航路点都采用最大速度，并且在每1航段的最后减速。最大速度剖面如图2中点划线所示。航空器以最大速度剖面飞行时对应最短耗时tmin，对包含n个航路点的航线段所对应的最短耗时tmin予以计算，如图3所示。其中：a为加速度(各类机型减速度来源于航空器基础数据BADA[12])，timin，tiamin，ticmin分别为航路点i-1与i之间总航段及减速阶段和匀速阶段所需最短耗时。

图3　最大速度剖面飞行时的耗时计算示意图 Fig.3　Schematic diagram of flying time calculation based on maximum speed profile

与最大速度剖面获取不同，最小速度剖面需在每1航段起始阶段减速，减速到后1航路点所允许的最小速度。同理，可以计算出航空器以最小速度剖面飞行时所需的最长耗时tmax。

2.2动态速度剖面

当给定到达时间t(tmin≤t≤tmax)，总存在合理的速度剖面与之相对应。为满足航空器在给定t时刻到达指定位置，设置参数r，并满足0≤r≤1，利用参数r可以确定航空器飞经每个航路点时所需的速度，以及航空器在每相邻的两个航路点间所应减速的位置。现对包含n个航路点的航线段所对应的满足到达时间t的动态速度剖面予以推导计算，如图4所示。其中：tmin，tmax为最短和最长耗时，ti，ti1，ti2，tia分别为航空器在航路点i-1与i之间飞行总时间以及以速度v(i-1)、vi飞行的时间和由速度v(i-1)到vi的时间，tz为航段飞行总时间。

图4　动态速度剖面耗时计算示意图 Fig.4　Schematic diagram of flying time calculation based on dynamical speed profile

由于最大速度剖面与最小速度剖面的速度变化范围不同，上述设计中会带来一定误差，使得飞行时间稍提前于所要求的到达时间t，即Δt≤0；因此在计算速度vi时，需要对r适当修正，以使tz恰好与给定时间t相等，最终生成符合时间t的速度剖面。

3仿真验证与结果分析

笔者提出的4D航迹规划遵循以下步骤：①利用动态时间规整与层次聚类对历史雷达轨迹聚类分析，根据聚类结果和标准仪表进场航线设计水平路径；②利用历史雷达数据统计各航路点的高度/速度范围，根据所设计的水平路径和统计的高度范围，设计相应高度剖面；③根据给定到达时间和速度范围，选择合理水平路径，设计满足条件的速度剖面；④将所设计的水平路径，高度剖面和速度剖面相应组合，即完成4D航迹规划。

3.1水平路径设计

以浦东国际机场北向进场运行构建仿真场景，并选取2013年1月2日至8日的经由VMB进场的A320机型航班数据进行聚类分析。上海终端区范围、扇区划分以及经由VMB进场的A320航班雷达轨迹见图5。

利用DTW算法及基于最小偏差平方和法的层次聚类法对历史雷达轨迹进行聚类分析。航迹聚类结果见图6。

图5　经由VMB点进场航班雷达轨迹示意图 Fig.5　Schematic diagram of arrival tracks through VMB

图6　航迹聚类结果树型图 Fig.6　Tree diagram of track clustering results

图6所示的航迹聚类结果树型图，为使航迹分类相对集中又具典型性，设置最小偏差平方和为2.8×1010来对聚类树进行水平剪枝，位于剪枝线之下的每1个子树即为1组聚类，共包含6个航迹聚类。对所得到的6个航迹聚类求取其平均轨迹，再结合标准仪表进场航线设计相应的水平进场路径，见图7。

3.2速度高度统计及高度剖面设计

统计经由VMB进港点进场航班高度，速度范围，见表1。

表1　经由VMB进场航班的高度速度范围

图7　自VMB进场的航空器盛行交通流示意图 Fig.7　Schematic diagram of prevailing arrival track through VMB

由历史雷达数据统计出的航空器在各航路点的高度是航空器真实飞过的高度，可以认为高度范围是合理的。同时航空器在较高高度飞行能够减少燃油消耗，并且降低噪声污染，因此本文在高度剖面的设计上在保证航空器安全无冲突的前提下遵循保持较高高度飞行的原则，且高度剖面在所统计出的高度范围内，如图8所示。

图8　VMB标准仪表进场航线高度剖面设计示意图 Fig.8　Schematic diagram of altitude profile design for VMB-STAR

3.3速度剖面设计及仿真验证

根据所设计的6条水平进场路径，同时可以获得自VMB进场的不同水平路径所对应的总路程和飞行耗时范围，见表2。

由表2可见，不同水平路径的飞行耗时范围多有重合，当满足781s≤t≤2046s时，可能有多条水平路径符合给定到达时刻的条件。由于短路径可以降低油耗，因此首先选择满足条件的最短路径，当所选择的最短路径使得进场航空器之间存在冲突时，更换为次短路径，以此类推，直至找到满足航空器之间无冲突的路径。

表2　VMB点不同水平进场路径对应的路程和耗时范围

设到达时间t=1300s，则路径1～6均可实现所设定到达时间，分别设计相对应的速度剖面，此处选取路径3和路径5的速度剖面进行说明，如图9所示，图中黑色实线表示利用参数优化生成的动态速度剖面。

当前在终端区实际运行中，管制员控制航班进场时间的方式主要是调整航班水平进场轨迹，然而相同的水平进场轨迹对应的耗时不尽相同，如表3所示为2013年1月2日沿水平路径5进场的航班，最长耗时为1348s，最短耗时为1252s，相差96s，此即为当前终端区运行中航班不能按计划到达时间到场的原因。

为验证上述4D航迹规划方法的准确性及可靠性，选用文献[13]中的基于BADA及航空器意图的4D航迹预测工具作为仿真软件，对上述规划的6条航迹分别进行仿真验证，如图10所示为路径5对应航迹的仿真结果，误差为2s，另外5条航迹的误差分别为：3，1，2，4，3，平均误差为2.5s， 误差率为1.9‰. 因误差较小，故可认为航空器按照上述规划的4D航迹飞行可以准点到达指定航路点，从而验证上述4D航迹规划方法可以有效保障航班按计划到达时间(STA)到场，从而提高航班准点运行能力。

图9　不同水平进场路径对应的速度剖面示意图 Fig.9　Schematic diagram of speed profile design corresponding to different horizontal track

图10　航空器沿路径5对应航迹飞行结果示意图 Fig.10　Schematic diagram of the result for aircraft flying along the trajectory of path 5

航班号总路程/km耗时/s DKH11382161258 CCA12572161348 CES52002161344 CSC89752161269 CCA45912161269 CES5212161252

4结束语

笔者所提出的基于历史雷达轨迹分析的进场动态4D航迹规划方法，是在对历史雷达轨迹进行聚类分析的基础上，设计出符合终端区实际运行的多条水平进场路径；并通过对历史雷达数据的统计分析，确定出每个进港航路点的高度、速度范围，进而设计出科学合理的高度、速度剖面。仿真结果表明，笔者提出的进场动态4D航迹规划方法在不考虑风等气象因素的情况下可以有效保障航空器准点降落，提高航班准点率。然而实际运行场景中风等天气因素的影响无法避免，会对航迹规划结果带来影响，因此如何将实际运行时风等气象因素的影响引入到高度/速度剖面的设计，并与进场管理系统相结合，是未来研究的1个重要方向。另外，如何将燃油消耗、噪声污染或解脱冲突作为优化指标引入航迹规划，是未来研究的另1个重要方向。

参考文献

[1]HANCERLIOGULLARI G, RABADI G, Al-SALEM A H, et al. Greedy algorithms and meta-heuristics for a multiple runway combined arrival-departure sequencing problem[J]. Journal of Air Transport Management,2013, 32(3): 39-48.

[2] 郑昌文，严平，丁明跃，等. 飞行器航迹规划研究现状与趋势[J]. 宇航学报， 2007，28(6): 1441-1445.

ZHENG Changwen, YAN Ping, DING Mingyue, et al. Research status and trend of route planning for flying vehicles[J]. Journal of Astronautics, 2007, 28(6): 1441-1445.

[3]李世晓,朱凡,张健,等. 改进A*算法的多约束航迹规划[J]. 电光与控制, 2014, 21(7): 36-40.

LI Shixiao, ZHU Fan, ZHANG Jian, et al. Multi-Restriction path planning based on improved A* algorithm [J]. Electronics Optics & Control, 2014, 21(7): 36-40.(in Chinese)

[4]YOU Feng, ZHANG Ronghui, LIE Guo, et al.Trajectory planning and tracking control for autonomous lane change maneuver based on the cooperative vehicle infrastructure system[J]. Expert Systems with Applications, 2015,42(14):5932-46.

[5]ERZBWRGER H, LEE H Q. Terminal area guidance algorithm for automated air traffic control[R]. Washington D.C.:NASA, 1972.

[6]Washington D.C.:PECSVARADI T. Four-dimensional guidance algorithm for aircraft in an air traffic control environment[R]. Washington D.C.NASA, 1975.

[7]王大海,苏彬,杨俊. 终端区域4D导引的高度剖面与速度剖面研究[J]. 飞行力学, 2000, 18(1): 14-18.

WANG Dahai, SU Bin, YANG Jun. Altitude and speed profile counting method of the 4D guidance in terminal area[J]. Flight Dynamics, 2000, 18(1): 14-18.(in Chinese)

[8]AGRAWAL R, FALOUTSOS C, SWAMI A. Efficient similarity search in sequence databases [M].Berlin:Springer Berlin Heidelberg, 1993: 69-84.

[9]王超, 徐肖豪, 王飞.基于航迹聚类的终端区进场程序管制适用性分析[J].南京航空航天大学学报,2013,45(1):130-139.

WANG Chao, XU Xiaohao, WANG Fei. ATC serviceability analysis of terminal arrival procedures using trajectory clustering[J].Journal of Nanjing University of Aeronautics &Astronautics, 2013,45(1):130-139.(in Chinese)

[10] 张连海，冯志远，陈琦，等.基于动态时间规整的语音样例快速检索算法[J].计算机应用研究，2014,31(6)：1688-1692.

ZHANG Lianhai，FENG Zhiyuan，CHEN Qi，et al. Fast query-by-example spoken term detection algorithm based on dynamic time warping[J]. Application Research of Computers, 2014,31(6)：1688-1692.(in Chinese)

[11]韩忠明, 陈妮, 张慧, 等. 一种非对称距离下的层次聚类算法[J].模式识别与人工智能，2014,27(5)：410-416.

HAN Zhongming，CHEN Ni，ZHANG Hui，et al. A hierarchical clustering algorithm based on asymmetric distance[J]. 2014,27(5)：410-416.(in Chinese)

[12]EUROCONTROL EXPERIMENTAL CENTER. User Manual for the Base of Aircraft Data (Revision 3.12)[R]. Brétigny-Sur-Orge,France:EEC , 2014.

[13]张军峰, 蒋海行, 武晓光, 等.基于BADA及航空器意图的4D航迹预测[J].西南交通大学学报，2014,49(3):553-558.

ZHANG Junfeng, JIANG Haihang, WU Xiaoguang, et al. 4D Trajectory Prediction Based on BADA and Aircraft Intent[J]. Journal of Southwest Jiaotong University, 2014,49(3):553-558.(in Chinese)