基于歷史雷達軌跡分析的4D航跡規(guī)劃*

馬廣輝張軍峰▲王菲陳強

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

摘要航空器4D航跡規(guī)劃可有效解決我國當前面臨的航班延誤問題，并且能夠加速空管自動化與智能化技術(shù)的應用與實施。因此提出了1種基于歷史雷達軌跡分析的4D航跡規(guī)劃方法：首先利用動態(tài)時間規(guī)整與層次聚類算法對進場歷史雷達軌跡進行聚類分析,復現(xiàn)盛行交通流,繼而根據(jù)盛行交通流和標準進場航線完成水平路徑設(shè)計；其次對進場歷史雷達數(shù)據(jù)統(tǒng)計分析，確定各進場航路點的高度/速度范圍，然后基于航空器在終端區(qū)盡量保持高高度飛行的原則完成高度剖面設(shè)計；再次為使航空器可以按規(guī)定時間到達指定航路點，根據(jù)各航路點的速度范圍設(shè)置合理參數(shù)，通過對參數(shù)優(yōu)化調(diào)整完成所需速度剖面的設(shè)計。最后以上海浦東國際機場VMB進場場景為例進行仿真驗證，平均誤差為2.5s，誤差率為1.9‰ 。仿真結(jié)果表明基于歷史雷達軌跡分析的4D航跡規(guī)劃方法可有效實現(xiàn)航班的準點降落，從而減少航班延誤,提高終端空域運行效率。

關(guān)鍵詞智能交通；4D航跡規(guī)劃；聚類；動態(tài)時間規(guī)整；空中交通管制

中圖分類號：V355文獻標志碼：A

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

基金項目*國家自然科學(批準號：71401072)、江蘇省自然科學

作者簡介：第一馬廣輝(1988-)，碩士研究生.研究方向：航跡規(guī)劃及決策支持.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引言

近年來，民航運輸業(yè)的高速發(fā)展極大地提高了出行效率。然而隨著空中交通量的持續(xù)增長，導致終端空域擁堵，流量控制頻繁，安全運行壓力倍增，大面積航班延誤等一系列問題。于是，沖突探測與解脫、進離場排序與調(diào)度等空管自動化與智能化方法[1]成為空中交通管理領(lǐng)域的研究重點，而民用航空器4D航跡規(guī)劃是確保上述方法有效實施的關(guān)鍵因素。

航跡規(guī)劃是在綜合考慮飛行器到達時間、油耗、威脅，以及飛行區(qū)域等因素的前提下，規(guī)劃最優(yōu)飛行航跡，以保證圓滿完成飛行任務[2]。航跡規(guī)劃在無人機領(lǐng)域的研究成果頗豐[3-4]，具體算法主要包括最優(yōu)式算法，啟發(fā)式算法和隨機型算法。筆者主要研究航跡規(guī)劃在民航智能空中交通管理領(lǐng)域的研究與應用，因為航跡規(guī)劃不僅可以為沖突解脫提供有效路徑，還能夠根據(jù)進離場調(diào)度產(chǎn)生的優(yōu)化時間生成相應4D航跡，以確保航空器安全準時到達指定地點，從而減少航班延誤，提高運行效率。

對民航空中交通管理領(lǐng)域航跡規(guī)劃的研究，美國國家航空航天局(NASA)[5-6]提出了終端空域航空器導引算法，自飛機當前位置開始生成飛行軌跡，包括航向、速度、高度和時間，并預先設(shè)定的時間在指定航路點終止。我國王大海等[7]研究了航空器在終端空域運行時高度/速度剖面生成算法，結(jié)合水平軌跡，設(shè)計了3D飛行剖面與4D導航指令。上述航跡規(guī)劃方法，計算效率高，但是以上方法未充分考慮終端空域?qū)嶋H運行，水平進場路徑設(shè)計單一。當前在大流量終端區(qū)，管制員在指揮大流量航班降落時，為保證飛機的無沖突安全著陸會實施復雜的雷達引導，導致部分航班的飛行軌跡偏離標準的進場航線，因此單一的水平進場路徑已不能適應當前日益增加的空中交通流量，亟需設(shè)計多條合理水平進場路徑。大數(shù)據(jù)挖掘在空中交通管理領(lǐng)域的應用研究可以輔助水平進場路徑的設(shè)計，從海量龐雜的歷史雷達軌跡中提取盛行交通流，可以為4D航跡規(guī)劃中水平軌跡的設(shè)計提供參考。對于歷史雷達軌跡的分析，Agrawal等[8]提出對序列數(shù)據(jù)庫進行有效的相似性搜索算法，王超等[9]提出基于航跡聚類的終端區(qū)進場程序管制適用性分析方法。以上方法都是基于歐式距離對航跡進行聚類，傳統(tǒng)的歐氏距離方法計算簡便，但不能有效地求得2條航跡的相似度，使得兩條空間形狀相似的航跡可能無法聚類，從而無法準確復現(xiàn)盛行交通流。

為解決上述問題，筆者在充分考慮進場航空器實際運行的前提下，首先利用動態(tài)時間規(guī)整算法(DTW)[10]和層次聚類方法[11]對歷史雷達軌跡進行聚類分析，此種方法可以有效求得2條航跡的相似度，使得空間形狀相似的航跡有效聚類，進而可以準確復現(xiàn)盛行交通流，為設(shè)計多條合理水平進場路徑提供參考；其次統(tǒng)計各航路點的速度高度范圍，在水平進場路徑的基礎(chǔ)上設(shè)計滿足到達時刻要求的速度高度剖面；最后，以上海浦東國際機場VMB進場場景為例進行仿真驗證。

1歷史雷達軌跡分析

由于筆者研究航跡聚類的主要目的是找出盛行交通流，為終端空域進場航跡規(guī)劃提供水平路徑參考，因此著力點主要集中在歷史雷達軌跡的空間形狀上。應用歐氏距離是進行歷史雷達軌跡聚類的常用方法，然而，這種方法的弊端是：①2條歷史雷達軌跡如果在起始階段有小的偏差，就會在后續(xù)階段導致非常大的計算偏差，致使形狀非常相似的軌跡不能聚到一類；②歷史雷達軌跡的長度可能并不相等，而且不同歷史雷達軌跡可能存在時間軸上的位移。在上述情況下，傳統(tǒng)的歐氏距離無法有效地求得2條軌跡之間的距離(或者相似性)，而動態(tài)時間規(guī)整(DTW)算法可有效解決此類問題。

動態(tài)時間規(guī)整算法是1種衡量2個時間序列相似度的方法。本文中的航跡分別可視作時間序列，如圖1所示，上下2條實線代表2條航跡，2條航跡之間的虛線代表2條航跡之間相似的點。DTW使用所有這些相似點之間的距離和，稱之為歸整路徑距離，來衡量2條航跡之間的相似性。

圖1　航跡規(guī)整示意圖 Fig.1　Schematic diagram of trajectory warping

設(shè)需要計算相似度的2條航跡為X與Y，長度分別為|X|和|Y|，規(guī)整路徑的形式為

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個規(guī)整路徑

(3)

式中Dist(i,j)為2點間的歐式距離。

基于上述的動態(tài)時間規(guī)整算法，并結(jié)合層次聚類能夠設(shè)計多條水平進場路徑，以滿足大流量航班流的運行需求。

通過分機型統(tǒng)計雷達軌跡經(jīng)過每個航路點的高度/速度，并加以整理分析，進而可以確定出每類機型在各航路點的高度/速度范圍。

2速度剖面設(shè)計

由于航空器在進場時基本是按照既定的飛行路徑運行，即標準儀表進場航線(STAR)。因此可以根據(jù)飛經(jīng)各航路點坐標，計算各相鄰航路點的距離及進場飛行的總距離。

當航空器飛行的高度剖面在合理范圍內(nèi)，且航空器所飛行的水平路徑已確定時，航空器的到場時刻由航空器的地速決定，不同的速度剖面對應不同的到場時刻。顯然，最大速度剖面對應最短到達時間；最小速度剖面對應最長到達時間；當所要求的到場時間介于最長和最短到達時間之間時，總有1個合理的速度剖面與之相對應，如圖2所示。

圖2　速度剖面設(shè)計示意圖 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飛過的距離，最小速度剖面與之類似；動態(tài)速度剖面中v(i-1)、vi分別代表第i-1、第i航路點的速度， di1為以速度v(i-1)飛過的距離，di2為以速度vi飛過的距離，dia為由速度v(i-1)減速到速度vi飛過的距離，D表示航路點i-1與i之間航段距離。

本節(jié)主要針對上述分析，優(yōu)化設(shè)計能夠滿足給定到達時間的速度剖面。

2.1最大最小速度剖面

由于進場飛行階段總體而言是減速運行，因此后1航路點的速度總是小于前1航路點的速度，為獲得最大速度剖面，每1航路點都采用最大速度，并且在每1航段的最后減速。最大速度剖面如圖2中點劃線所示。航空器以最大速度剖面飛行時對應最短耗時tmin，對包含n個航路點的航線段所對應的最短耗時tmin予以計算，如圖3所示。其中：a為加速度(各類機型減速度來源于航空器基礎(chǔ)數(shù)據(jù)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ài)速度剖面

當給定到達時間t(tmin≤t≤tmax)，總存在合理的速度剖面與之相對應。為滿足航空器在給定t時刻到達指定位置，設(shè)置參數(shù)r，并滿足0≤r≤1，利用參數(shù)r可以確定航空器飛經(jīng)每個航路點時所需的速度，以及航空器在每相鄰的兩個航路點間所應減速的位置?，F(xiàn)對包含n個航路點的航線段所對應的滿足到達時間t的動態(tài)速度剖面予以推導計算，如圖4所示。其中：tmin，tmax為最短和最長耗時，ti，ti1，ti2，tia分別為航空器在航路點i-1與i之間飛行總時間以及以速度v(i-1)、vi飛行的時間和由速度v(i-1)到vi的時間，tz為航段飛行總時間。

圖4　動態(tài)速度剖面耗時計算示意圖 Fig.4　Schematic diagram of flying time calculation based on dynamical speed profile

由于最大速度剖面與最小速度剖面的速度變化范圍不同，上述設(shè)計中會帶來一定誤差，使得飛行時間稍提前于所要求的到達時間t，即Δt≤0；因此在計算速度vi時，需要對r適當修正，以使tz恰好與給定時間t相等，最終生成符合時間t的速度剖面。

3仿真驗證與結(jié)果分析

筆者提出的4D航跡規(guī)劃遵循以下步驟：①利用動態(tài)時間規(guī)整與層次聚類對歷史雷達軌跡聚類分析，根據(jù)聚類結(jié)果和標準儀表進場航線設(shè)計水平路徑；②利用歷史雷達數(shù)據(jù)統(tǒng)計各航路點的高度/速度范圍，根據(jù)所設(shè)計的水平路徑和統(tǒng)計的高度范圍，設(shè)計相應高度剖面；③根據(jù)給定到達時間和速度范圍，選擇合理水平路徑，設(shè)計滿足條件的速度剖面；④將所設(shè)計的水平路徑，高度剖面和速度剖面相應組合，即完成4D航跡規(guī)劃。

3.1水平路徑設(shè)計

以浦東國際機場北向進場運行構(gòu)建仿真場景，并選取2013年1月2日至8日的經(jīng)由VMB進場的A320機型航班數(shù)據(jù)進行聚類分析。上海終端區(qū)范圍、扇區(qū)劃分以及經(jīng)由VMB進場的A320航班雷達軌跡見圖5。

利用DTW算法及基于最小偏差平方和法的層次聚類法對歷史雷達軌跡進行聚類分析。航跡聚類結(jié)果見圖6。

圖5　經(jīng)由VMB點進場航班雷達軌跡示意圖 Fig.5　Schematic diagram of arrival tracks through VMB

圖6　航跡聚類結(jié)果樹型圖 Fig.6　Tree diagram of track clustering results

圖6所示的航跡聚類結(jié)果樹型圖，為使航跡分類相對集中又具典型性，設(shè)置最小偏差平方和為2.8×1010來對聚類樹進行水平剪枝，位于剪枝線之下的每1個子樹即為1組聚類，共包含6個航跡聚類。對所得到的6個航跡聚類求取其平均軌跡，再結(jié)合標準儀表進場航線設(shè)計相應的水平進場路徑，見圖7。

3.2速度高度統(tǒng)計及高度剖面設(shè)計

統(tǒng)計經(jīng)由VMB進港點進場航班高度，速度范圍，見表1。

表1　經(jīng)由VMB進場航班的高度速度范圍

圖7　自VMB進場的航空器盛行交通流示意圖 Fig.7　Schematic diagram of prevailing arrival track through VMB

由歷史雷達數(shù)據(jù)統(tǒng)計出的航空器在各航路點的高度是航空器真實飛過的高度，可以認為高度范圍是合理的。同時航空器在較高高度飛行能夠減少燃油消耗，并且降低噪聲污染，因此本文在高度剖面的設(shè)計上在保證航空器安全無沖突的前提下遵循保持較高高度飛行的原則，且高度剖面在所統(tǒng)計出的高度范圍內(nèi)，如圖8所示。

圖8　VMB標準儀表進場航線高度剖面設(shè)計示意圖 Fig.8　Schematic diagram of altitude profile design for VMB-STAR

3.3速度剖面設(shè)計及仿真驗證

根據(jù)所設(shè)計的6條水平進場路徑，同時可以獲得自VMB進場的不同水平路徑所對應的總路程和飛行耗時范圍，見表2。

由表2可見，不同水平路徑的飛行耗時范圍多有重合，當滿足781s≤t≤2046s時，可能有多條水平路徑符合給定到達時刻的條件。由于短路徑可以降低油耗，因此首先選擇滿足條件的最短路徑，當所選擇的最短路徑使得進場航空器之間存在沖突時，更換為次短路徑，以此類推，直至找到滿足航空器之間無沖突的路徑。

表2　VMB點不同水平進場路徑對應的路程和耗時范圍

設(shè)到達時間t=1300s，則路徑1～6均可實現(xiàn)所設(shè)定到達時間，分別設(shè)計相對應的速度剖面，此處選取路徑3和路徑5的速度剖面進行說明，如圖9所示，圖中黑色實線表示利用參數(shù)優(yōu)化生成的動態(tài)速度剖面。

當前在終端區(qū)實際運行中，管制員控制航班進場時間的方式主要是調(diào)整航班水平進場軌跡，然而相同的水平進場軌跡對應的耗時不盡相同，如表3所示為2013年1月2日沿水平路徑5進場的航班，最長耗時為1348s，最短耗時為1252s，相差96s，此即為當前終端區(qū)運行中航班不能按計劃到達時間到場的原因。

為驗證上述4D航跡規(guī)劃方法的準確性及可靠性，選用文獻[13]中的基于BADA及航空器意圖的4D航跡預測工具作為仿真軟件，對上述規(guī)劃的6條航跡分別進行仿真驗證，如圖10所示為路徑5對應航跡的仿真結(jié)果，誤差為2s，另外5條航跡的誤差分別為：3，1，2，4，3，平均誤差為2.5s， 誤差率為1.9‰. 因誤差較小，故可認為航空器按照上述規(guī)劃的4D航跡飛行可以準點到達指定航路點，從而驗證上述4D航跡規(guī)劃方法可以有效保障航班按計劃到達時間(STA)到場，從而提高航班準點運行能力。

圖9　不同水平進場路徑對應的速度剖面示意圖 Fig.9　Schematic diagram of speed profile design corresponding to different horizontal track

圖10　航空器沿路徑5對應航跡飛行結(jié)果示意圖 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結(jié)束語

筆者所提出的基于歷史雷達軌跡分析的進場動態(tài)4D航跡規(guī)劃方法，是在對歷史雷達軌跡進行聚類分析的基礎(chǔ)上，設(shè)計出符合終端區(qū)實際運行的多條水平進場路徑；并通過對歷史雷達數(shù)據(jù)的統(tǒng)計分析，確定出每個進港航路點的高度、速度范圍，進而設(shè)計出科學合理的高度、速度剖面。仿真結(jié)果表明，筆者提出的進場動態(tài)4D航跡規(guī)劃方法在不考慮風等氣象因素的情況下可以有效保障航空器準點降落，提高航班準點率。然而實際運行場景中風等天氣因素的影響無法避免，會對航跡規(guī)劃結(jié)果帶來影響，因此如何將實際運行時風等氣象因素的影響引入到高度/速度剖面的設(shè)計，并與進場管理系統(tǒng)相結(jié)合，是未來研究的1個重要方向。另外，如何將燃油消耗、噪聲污染或解脫沖突作為優(yōu)化指標引入航跡規(guī)劃，是未來研究的另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] 鄭昌文，嚴平，丁明躍，等. 飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢[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*算法的多約束航跡規(guī)劃[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]王大海,蘇彬,楊俊. 終端區(qū)域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]王超, 徐肖豪, 王飛.基于航跡聚類的終端區(qū)進場程序管制適用性分析[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] 張連海，馮志遠，陳琦，等.基于動態(tài)時間規(guī)整的語音樣例快速檢索算法[J].計算機應用研究，2014,31(6)：1688-1692.

ZHANG Lianhai，F(xiàn)ENG 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)