文章快速检索 高级检索

1. 天津大学 计算机科学与技术学院, 天津 300072;
2. 中国民航大学 空中交通管理学院, 天津 300300

Geometric approach for intercontinental formation flight path planning
XU Xiaohao1,2, MENG Linghang1,2 , ZHAO Yifei2
1. School of Computer Science and Technology, Tianjin University, Tianjin 300072;
2. College of Air Traffic Management, Civil Aviation University of China, Tianjin 300300, China
Abstract:For intercontinental formation flight path planning problem, a basic model was developed based on the aerodynamic models and spherical metric characteristics of formation flight. The problem was then abstracted as the weighted geodesic Steiner minimum tree (WGSMT) problem in spherical point set due to its topological characteristics. The principles of simplifying WGSMT to a finite geometry planning problem were proposed. We also proved that the connecting points induced by obstacles only changed the topology of their adjacent Steiner points while did not lose the accuracy of solution. Finally, a two stage formation path planning algorithm based on “construct-repair” approach was developed, whose validity was verified by an example. Significance of the study is that the sphere geometric fundamentals of intercontinental formation path planning are built,which therefore makes the complexity of the problem depend on the scale of flight set rather than that of geographic grids, thereby reduces the complexity of the problem dramatically.
Key words: air transportation     formation flight     path planning     Steiner minimal tree(SMT)     geometric approach
﻿

Hino提出一种两阶段编队路径规划方法:编队路径拓扑选择(Formation Path Topology Selection,FPTS)和编队路径优化(Formation Path Optimization,FPO)[15].FPTS阶段考虑飞行性能约束,建立实现节油目的的集结包线和脱离包线;FPO阶段在集结包线和脱离包线构成的凸边界内利用时序二次型优化规划集结点和脱离点.Xu等提出一种两阶段编队路径优化框架[16]:首先通过预设航班编队的时间和空间边界约束,利用类似于滤波的方法从大规模航班集合中识别可行编队航班集;然后利用整数规划在可行编队航班集上优化编队调度逻辑.Hino和Xu从编队气动耦合理论出发建立编队路径节点的规划域,使问题的复杂度大为降低,但球面度量考虑不足.

1 问题描述 1.1 编队路径

 图 1 编队飞行路径结构 Fig. 1 Formation flight path structure

 图 2 编队路径结构抽象出的树状网络 Fig. 2 Tree network structure abstracted from formation flight path

1.2 当量航程

1.3 数学模型 1.3.1 目标函数

1) fi=〈di,ai,qi〉表示航班fi的起飞机场、降落机场和机队规模;

2) 编队飞行路径网络T(D,A,R,B,E,Q,W)：

D={di|i=1,2,…,m}为所有候选航班的起飞机场集合;

A={aj|j=1,2,…,n}为所有候选航班的降落机场集合;R={ri|i=1,2,…,m-1}为规划的集结点集合;

B={bj|j=1,2,…,n-1}为规划的脱离点集合;

E=[eij]2(m+n-1)×2(m+n-1)T中节点的邻接矩阵,eij=1表示vivj邻接,vi∈D∪R∪B∪A,vj∈D∪R∪B∪A,否则,eij=0;

Q={qij|i=1,2,…,2(m+n-1),j=1,2,…,2(m+n-1)}为各边上的编队规模;

W={wij|i=1,2,…,2(m+n-1),j=1,2,…,2(m+n-1)}为E的权重集合.

1.3.2 当量航程约束

 图 3 当量航程约束 Fig. 3 Equivalent voyage constraint
1.3.3 集结时间窗约束

vi∈D时,Λi表示允许的最大地面延误时间;当vi∈R时,Λi表示允许的最大空中等待时间.

1.3.4 拓扑结构约束

1) 所有集结点入度不大于2、出度为1,所有脱离点入度为1、出度不大于2.

2) 所有衔接点的出度和入度均为1.

1.3.5 流量平衡约束

1.3.6 飞行受限区约束

 图 4 飞行受限区限制的编队飞行路径 Fig. 4 Formation flight path constrained by flight restricted area
1.3.7 备降机场约束

 图 5 备降机场约束不满足时新增中间衔接航路点ck Fig. 5 A new connection point ck is added whenever ETOPS constraint is not satisfied
2 WGSMT的有限几何简化

2.1 基本定义

Steiner最小树(Steiner Minimal Tree,SMT)问题是具备NP(Non-Polynomialtime,NP)难的经典几何问题,在网络分析与布局、城市交通规划、大规模集成电路设计、决策优化等领域有着广泛的应用.Courant和Robbins给出了Steiner点满足的基本几何性质[18].Melzak给出了SMT问题的有限几何简化原则,使SMT问题转化为一个有限问题[19].文献[13-14]利用欧氏空间上的角度条件及建立在该角度条件上的有限几何简化原则规划编队路径,球面度量特征考虑不足.

Dolan等给出GSMT(Geodesic Steiner Minimal Tree,GSMT)的定义[20].

2.2 WGSMT编队路径存在的充分必要条件

Cockayne[21]和Weng[22]推导出GSMT Steiner角恰好为120°.本节推导WGSMT编队路径存在的充分必要条件.

 图 6 球面3点的Steiner点 Fig. 6 Steiner point of 3 points on sphere

2.3 WGSMT的有限几何简化

 图 7 球面3点WGSMT的有限几何简化 Fig. 7 Simplifying WGSMT to a finite geometric planning problem of 3 points on sphere

1) 对于球面3点A、BC,根据式(20)计算∠ASB,进而利用式(29)计算∠ABC′∠BAC′;在球面点集{A,B,C}的凸包外侧,利用大圆弧构造球面等腰△ABC′及其球面外接圆,使满足式(29),则大圆弧与△ABC′球面外接圆交于异于C′的另外一点S即为球面3点A、BC满足角度条件式(20)~式(22)的WGSMT Steiner点,如图 6所示.

2) 对于球面4点A、BC、D,在球面点集{A,B,C,D}的凸包外侧,分别利用构造球面等腰和球面等腰△及外接圆,使

 图 8 球面4点WGSMT的有限几何简化 Fig. 8 Simplifying WGSMT to a finite geometric plan problem of 4 points on sphere

3) 对于任意Steiner角,假定为图 7所示∠BSC,若∠BSC＜∠BAC,根据上述规则所规划的Steiner点S将位于球面点集{A,B,C}的凸包外侧,此时应取S点为A点,度为2.在编队路径中,表明该点恰位于某一机场.

3 编队飞行路径规划的几何方法

1) 主要编队燃油效益区间为洲际航空运输,满足规划精度要求的规划空间巨大.

2) 边的权重依赖于编队调度方案,具备动态网络流特征.

3) 编队路径具备球面度量特征和航空约束特征,求解困难.

1) 给定意图编队的航班集合已经满足约束条件式(9)与式(10).实际上,可以从式(9)与式(10)出发,建立可接受编队模式[16]的时间维和空间维判别边界,利用含边界约束的最优层次聚类得到满足式(9)与式(10)的航班集,本文不研究该问题.

2) 同一起飞机场的航班集飞往同一降落机场.如果存在起飞机场di的航班集飞往nj个降落机场an1,an2，…,anj,流量依次为qn1,qn2，…,qnj,则将di分解为nj个与di地理位置相同的虚拟起飞机场dn1,dn2，…,dnj,令(dn1,an1),(dn2,an2)，…,(dnj,anj)的流量依次为qn1,qn2，…,qnj;反之,如果存在mi个起飞机场dm1,dm2，…,dmi的航班飞往同一降落机场am,流量分别为qm1,qm2，…,qmi,则将am分解为mi个与am位置相同的虚拟降落机场am1,am2，…,ami,令(dm1,am1),(dm2,am2)，…,(dmi,ami)的流量依次为qm1,qm2，…,qmi.

 图 9 WGSMT编队路径 Fig. 9 WGSMT formation path

1) 如果D、A非空,按照深度优先规则,基于起降机场对的影响力因子λij,每次从D、A中仅选择λij最大起降机场对(di1,aj1,qi1j1)及与其空间维相似度最高的起降机场对(di2,aj2,qi2j2)构造球面4点的WGSMT.利用WGSMT有限几何简化原则,得到集结点ri1和脱离点bj2,如图 10所示.其中,虚线为当前单独执行任务路径;实线为规划的编队路径.

 图 10 球面4点的WGSMT构造 Fig. 10 Constructing WGSMT of 4 points on sphere

2) 在D、A中利用(ri1,bj2,qi1j1+qi2j2)取代正则点对(di1,aj1,qi1j1)和(di2,aj2,qi2j2),得到更新后的规划域;转至1),直至完成所有正则点对的构造.

3) 经过前两步1)和2)后,所得到的编队路径可能存在3种情况:

① 所有Steiner点的度恰好为3,WGSMT编队路径满拓.

② 存在Steiner点的度为2,表明某一机场为集结点或脱离点.

③ 存在Steiner点的度大于3,如图 11中的ri1bj1.出现该情况的原因在于递归构造WGSMT树的过程中,利用Steiner点代替其支撑的正则点进行构造.此路径非几何意义上的最优.修复方法:从di1di2选择与di3空间相似度较高的一点,假定为di2点,构造r′i2=3-Steiner(di2,di3,ri1);同样,从di1di2选择与di3空间相似度较高的一点,假定为aj3点,构造bj2=3-Steiner(aj2,aj3,bj1),最终得到如图 12所示的满拓WGSMT.

 图 11 存在Steiner点的度大于3的WGSMT Fig. 11 WGSMT with Steiner points whose degrees are greater than 3

 图 12 修复后的WGSMT Fig. 12 Repaired WGSMT

1) 构造rm－1bn－1之间的最短避障路径.

 图 13 rm－1与bn－1间的最短避障路径 Fig. 13 Shortest obstacle-avoidance path between rm－1 and bn－1

2) 构造OAWGSMT编队飞行路径.

 图 14 OAWGSMT编队路径 Fig. 14 OAWGSMT formation path

 图 15 球面3点OAWGSMT构造 Fig. 15 Constructing OAWGSMT of 3 points on sphere

 图 16 球面4点OAWGSMT构造 Fig. 16 Constructing OAWGSMT of 4 points on sphere
4 算 例

 起降机场对 航班号 起飞机场 降落机场 航班架次 纬度/(°) 纬度/(°) 纬度/(°) 纬度/(°) 上海-长滩 Z2029 31.20 121.34 33.82 -118.15 1 香港-洛杉矶 CX880 22.31 113.91 33.94 -118.41 1 台北-旧金山 CI004BR028 25.08 121.23 37.62 -122.38 2 台北-洛杉矶 CI008BR016 25.08 121.23 33.94 -118.41 2 台北-温哥华 CI032 BR010 25.08 121.23 49.19 -123.18 2 台北-奥克兰 CI053 25.08 121.23 37.71 -122.34 1

 名称 纬度/(°) 经度/(°) 等级 香港国际机场 N22.31 E113.91 4F 东京羽田国际机场 N35.77 E140.39 4F 斯雷登堪察次克机场 N56.24 E162.69 4D 安克雷奇国际机场 N61.19 W150.01 4E 旧金山国际机场 N37.62 W122.38 4E

 图 17 WGSMT编队飞行路径 Fig. 17 WGSMT formation flight path

 图 18 OAWGSMT编队飞行路径 Fig. 18 OAWGSMT formation flight path

 起降机场对 起飞机场 降落机场 架次 计划航程/n mile WGSMT OAWGSMT 纬度/(°) 经度/(°) 经度/(°) 经度/(°) 当量航程/n mile 节省/% 当量航程/n mile 节省/% 上海-长滩 31.20 121.34 33.82 -118.15 1 5 649.29 3 281.08 41.92 3 226.98 42.88 香港-洛杉矶 22.31 113.91 33.94 -118.41 1 6 294.23 3814 39.41 3 822.95 39.26 台北-旧金山 25.08 121.23 37.62 -122.38 2 5 606.80 3 229.43 42.40 3 238.84 42.23 台北-洛杉矶 25.08 121.23 33.94 -118.41 2 5 893.70 3 413 42.09 3 422.19 41.93 台北-温哥华 25.08 121.23 49.19 -123.18 2 5 175.85 2 977.24 42.48 3 006.85 41.91 台北-奥克兰 25.08 121.23 37.71 -122.34 1 5 605.20 3 230.54 42.37 3 239.95 42.20

1) 由于执行ETOPS-180标准,计划航线和编队路径均位于ETOPS一圆内,无不满足备降机场约束的编队航段.

2) WGSMT编队路径有2个满拓的集结点rhtrhts、2个满拓的脱离点bvasllbasll、2个度为2的脱离点“旧金山”和“洛杉矶”;OAWGSMT编队路径有1个满拓的集结点rht,1个度为2的集结点上海,2个满拓的脱离点bvasllbasll,2个度为2的脱离点“旧金山”和“洛杉矶”,1个衔接点c.两种路径均满足节点度约束和流量平衡约束.

3) 只有“上海-长滩”的OAWGSMT编队路径的燃油经济性优于WGSMT.原因是由于衔接点c的引入,使“上海”由正则点变为集结点,几何航程缩短.

4) 编队飞行的燃油经济性约40%左右,所有编队航空器获得相对均衡的编队燃油经济效益.该结果较为乐观,主要原因在于:

① 未考虑大间距编队飞行时黏性阻力、大气浮力、大气紊流、尾涡碰撞、定位误差等因素影响;

② 未考虑集结机动和脱离机动区范围影响;

③ 未考虑编队稳定性限制的最大编队规模束.

5 结 论

1) 针对洲际航空编队飞行路径规划问题,提出当量航程定义,使编队飞行的燃油经济性得以表达;在此基础上,建立了编队路径飞行规划问题在球面上的数学表达.

2) 基于编队路径的拓扑特征,将编队路径规划问题抽象为WGSMT问题,推导出WGSMT Steiner点的角度条件,建立了WGSMT问题的有限几何简化原则,形成了WGSMT Steiner点的编队路径的精确几何构造方法.

3) 针对OAWGSMT编队路径规划问题,证明了衔接点的引入仅改变紧邻的Steiner点的拓扑特征.

4) 在2)和3)的基础上,构造基于“构造-修复”思想的编队飞行路径几何规划方法.

 [1] Airport Council International.Global traffic forecast 2006—2025 executive summary,Edition 2007[R].Montreal:Airport Council International,2007. [2] Rojo J J.Future trends in local air quality impacts of aviation[D].Massachusetts:Massachusetts Institute of Technology,2007. Click to display the text [3] Blake W,Multhopp D.Design,performance and modeling considerations for close formation flight,AIAA-1998-4343[R].Reston:AIAA,1998. Click to display the text [4] Dijkers H P A,Van Nunen R,Bos D A,et al.Integrated design of a long-haul commercial aircraft optimized for formation flying,AIAA-2011-6969[R].Reston:AIAA,2011. Click to display the text [5] Nehrbass J G,Frommer J B,Garison L A,et al.Point to point commercial aircraft service design study including formation flight and morphing[C]//AIAA 4th Aviation Technology,Integration and Operations(ATIO)Forum.Reston:AIAA,2004:20-22. [6] Ning S A.Aircraft drag reduction through extended formation flight[D].Stanford:Stanford University,2011. [7] Ning S A,Flanzer T C,Kroo I M,et al.Aerodynamic performance of extended formation flight[J].Journal of Aircraft,2011,48(3):855-865. Click to display the text [8] Ning S A,Kroo I M.Compressibility effects of extended formation flight,AIAA-2011-3812[R].Reston:AIAA,2011. Click to display the text [9] Flanzer T C,Bieniawski S R,Blake W B,et al.Operational analysis for the formation flight for aerodynamic benefit program,AIAA-2014-1460[R].Reston:AIAA,2014. Click to display the text [10] Xue M,Hornby G.An analysis of the potential savings from using formation flight in the NAS,AIAA-2012-4524[R].Reston:AIAA,2012. Click to display the text [11] Ribichini G,Frazzoli E.Efficient coordination of multiple-aircraft systems[C]//Proceedings of IEEE Conference on Decision and Control.Piscataway,NJ:IEEE Press,2003,1:1035-1040. Click to display the text [12] Bower G C,Flanzer T C,Kroo I M.Formation geometries and route optimization for commercial formation flight,AIAA-2009-3615[R].Reston:AIAA,2009. Click to display the text [13] Kent T,Richards A.A geometric approach to optimal routing for commercial formation flight,AIAA-2012-4769[R].Reston:AIAA,2012. Click to display the text [14] Kent T E,Richards A G.On optimal routing for commercial formation flight,AIAA-2013-4889[R].Reston:AIAA,2013. Click to display the text [15] Hino T.Real time path planning method of aircraft formations[C]//28th International Congress of the Aeronautical Scicences.Brisbane:ICAS,2012:1-5. Click to display the text [16] Xu J S,Ning S A,Bower G C,Kroo I M,et al.Aircraft route optimization for formation flight[J].Journal of Aircraft,2014,51(2):490-501. Click to display the text [17] Chiles P.ETOPS redefined[J].AeroSafety World,2007,2(3):88-92. [18] Courant R,Robbins H.What is mathematics?[M].New York:Oxford University Press,1951. [19] Melzak Z A.On the problem of Steiner[J].Canadian Mathematical Bulletin,1961,4(2):143-148. [20] Dolan J,Weiss R,Smith J M G.Minimal length tree networks on the unit sphere[J].Annals of Operations Research,1991,33(7):501-535. Click to display the text [21] Cockayne E J.On fermat’s problems on the surface of a sphere[J].Mathematics Magazine,1972,45(4):216-219. Click to display the text [22] Weng J F.Steiner trees on curved surfaces[J].Graphs and Combinatorics,2001,17(2):353-363. Click to display the text

#### 文章信息

XU Xiaohao, MENG Linghang, ZHAO Yifei

Geometric approach for intercontinental formation flight path planning

Journal of Beijing University of Aeronautics and Astronsutics, 2015, 41(7): 1155-1164.
http://dx.doi.org/10.13700/j.bh.1001-5965.2014.0515