飞行管理问题的实时算法 复旦大学谭浩南朱正光刘剑 指导教师蔡志杰 编者按该文以区域内飞机调整飞行角幅度的平方和为目标函数,以自调整时刻起 0.3小时内飞机两两不发生碰撞为约束条件,建立了一个非线性规划模型,用逐步求精的直接 索和引人罚函数,化为无约束极值,用序列无约束最小化(SMT)两种方法进行求解 作者在建模和求解时从实际需要出发,精益求精,将上述两种方法相结合,得到了精度高 基本上是实时的方法与程序,还对模型与方法作出了恰当的分析与评价,文章清晰、完整 摘要本文讨论了在一定区域空间内进行飞行管理避免飞机相撞的模型,提出了直接 计算时间小于10秒,误差不超过0.01度,完全符合问题的要求, 本文接着给出四种不同情况分别用两种方法求解进行比较检验,取得很好的吻合,充分 说明了模型3的可靠性本文还对模型的误差进行分析并对模型进行推厂 关键词非线性规划,直接搜索,罚函数 问题的提出(略) 二、问题的分析 该问题是一个在一定约束条件下的最优化问题,初步分析题意后可知约束条件是非线 的,难以化归为线性规划问题由于题目涉及数据变量不是太多,可以考虑用逐步求精的 接搜索法求解由于题目要求的精度较高,而对于计算时间的要求也较高,如果求解时间 2、3分钟以上将失去任何实际意义我们将求解时间上限定为0.5分,以符合实际的要 .直接搜索法求的近似解难以同时满足两方面的要求但直接搜索法至少能在较短的时间 得到一个较好的可行解,这就为运用非线性规划的方法提供了条件,非线性规划的算法种 多,但均只适用于某些类型的问题由于缺乏适用的计算机软件包,我们自行编写了实 能算法的程序,综合程序准备时间和收敛速度两方面因素我们选择了SUMT算法SUMT 法与直接搜索法相结合,使我们能够在足够短的时间内找到问题的足够精确的解 三、模型假设及说明 1.不碰撞的标准为任意两架飞机的距离大于8km; 飞机飞行方向角调整的幅度不应超过30度; 所有飞机飞行速度均为每小时800km; 4.进人该区域的飞机在到达区域边缘时,与区域内飞机的距离应在60公里以上; 5.最多考虑6架飞机; 6.不必考虑飞机离开此区域后的状况; 7.飞机进入控制区域后完全服从地面控制台的调度,飞机未接到指令时保持飞行状态
8.计算机从记录新进入飞机数据到给各飞机发指令间隔为t1,t1小于0.5分 9.飞机接到指令后可立即转到所需角度,即不考虑转弯半径的影响 说明 1.假设3假定所有飞机速度均为800km/h,是出于对问题的简化.我们将在模型的推 广中给出飞机速度各不相同时的对策 2.假设4是必要的,否则可以给出无解的例证,如图所示,对该假设可作如下解释:飞机 在区域D外靠机上雷达自动保持与其他飞机距离大于60km,进人区域D后由地面控制台 进行统一控制,保证飞机距离大于8km 3.假设5中6架飞机的假设是足够多的.以世界最繁忙的国际航空港之一希思罗机场 邻近区域为例,因假设飞机在区域D作水平飞行,即知该区域内无机场.设在希思罗机场起 降的飞机有一半穿过该区域,希思罗机场1992年起降总架次为22.5万次(文献6),则平均 每小时有15架飞机穿过该区域面一架飞机穿过该区坡最多需198042≈0.28小时,则任 时刻该区域上空飞机架数的期望值不超过4.5架.另外,事实上不同飞机的飞行高度是不 同的,这就进一步减少了该区域同一水平面上飞机的数目.以上讨论虽然稍嫌粗略,但是足 以说明6架飞机的假设是合理的 4,假设8是因为计算机从接到数据到发出命令间存在一个时滞,该时滞固然越小越好 但受机器限制,一般不能忽略我们取0.5分为此时滞的一个上限,以使结果具有实际意义 当t<1秒时,可以认为实现的是实时控制,时滞可以忽略不计 5.虽然假设2给出的调整范围为30度,但实践证明,10度的调整范围就已足够(从后面 的模型1也可看出,即使两机相向飞行,各自所须的调整也不超过8度),因而在今后绝大多 数讨论和程序的编制中都将搜索区间定为[-10,10度 四、文中用到的符号及说明 t;时滞 (x0,y0)第架飞机的坐标 ao第i架飞机初始方位角t时间参数 a第i架飞机方位角D(a1,a)时刻ti,j两机距离 minD(a;a)i,j两机预计最短距离 C S, sina- sina 飞机速度
飞行管理问题的实时算法 87 △xx:-x ∫偏差平方和函数 2y·y-y 求精次数 x逐步求精搜索法中每次求精每层循环次数 g;(x)i,j飞机最短距离构成的不等式约束 (x)关于第i架飞机的等式约束 p(X,r)罚函数 r权因子 五、模型的建立及求解 (一)模型一(两架飞机的情形,略) (二)模型 模型二直接将两机模型运用于多机问题,因为它等价于飞机之间两两不相撞该模型讨 论区域中有6架以下飞机时的情形,利用了模型一判别相撞的函数 crash,同模型一同样采 方向角调整幅度平方和最优为调整原则,从而导出目标函数和约束条件如下 min (a;-aa)2 t.大:minD2(a,a)≥64(i,j=1,2,…6,i≠j),t>0; 或t<0 min D2(ai,a) + Ar,cic+△x +/4S+△x05+4y : Av Ci Ayi+ AtiC 证ash函数只考虑区域中的飞机相撞情况.我们可作如下修改:因为飞机飞过该区域 不超过0.28小时(即飞正方形区域对角线时间),我们可认为仅当minD<8,且0<t 28小时的时候,飞机在区域中相撞;否则不相撞在实际计算时,我们更把上限加大到 小时,实际上是使不相撞的条件更苛刻了一些,相当于对飞机飞离此区域后的情况也作 部分考虑,提高了全局控制的安全性 该模型我们采用直接搜索法讨论了一般情况下对原问题的求解,可在规定时间内得 个近似解,如果放宽时限,则可得一个符合精度要求的最优解 直接搜索法原理十分简单:构造多重循环,对所有可能解进行判断,直接得出在一定精 围内无可置疑的最优解但如不使用任何技巧进行直接搜索,必须耗费大量时间.以本 为例,若在[-10,10]度范围内进行搜索,步长0.01度,共6层循环,需计算6.4×109次 DX66上计算一次循环内函数费时2.7×105秒,此种算法显然是不可取的 为在30秒内算出一个较精确的解,我们采用了逐步求精的方法即每次用一定的步长 的循环次数进行“粗选”,在“粗选”出的解附近以减小了的步长进行“精选”,逐次推
进,直到达到指定精度 设每次求精步长减小的倍数是相同的,则每次求精循环次数也相同,设为x.我们考虑 -10,10]度区间,精度要求达到0.01度,设进行了n次求解,则 =200.01=2000 总循环次数L=n×x6=(log2000og(x/2)×x 由此式可知x减小,则L减小,但若x太小,则可能无法收敛到最优解经验表明x在8 次以上时才能达到较好的搜索效果 求立的量 n=(log200)/(log(8/2)=5,4≈5 此时共需搜索最多5×90=265万次,需费时71.55秒, 为将计算时间控制在30秒以内,我们又采取了一些优化方法,如 a.将底层循环内判别相撞的函数拆细分装在每层循环下,使在高层发现相撞后可提前 结束循环 b.每进入新一层循环把已积累偏差平方和与已得最小偏差平方和比较,若大则结東该 层循环; c.每进入新一层循环把已积累偏差平方和与已得最小偏差平方和比较,若大则结束该 层循环 这些措施大大减少了平均搜索次数,使得在多数情况下计算时间少于30秒,但程序不 能保证在30秒内结束运算,仍存在一些特异情况使计算时间接近最大耗时我们又试用偏 差绝对值和来代替平方和,发现对最优解影响有限,未能明显缩短计算时间 至此可知,用直接搜索法在现有机器条件下难以满足题设要求,要利用该解法,地面控 制台必须满足以下条件之一 1)拥有速度至少为486DX66三倍以上的电脑 2)降低精度要求至0.1度(4次求精步长为7,需时至多10.81秒)即使模型二不能直接 用于飞行管理,它仍有以下作用 1)可算出符合精度要求的最优解供检验其他模型 2)可在相当短的时间内算出具有一定精度的最优解作为其他算法的初值.当精度要求 为1度时,它算出最优解最多只需4.3秒(两次求精步长分别为76),大多情况下运算时间 为2-3秒 (三)模型三 该模型将原问题归结为一个非线性规划问题,并用SUMT算法进行了求解 模型二给出的解法虽然不能满足题设要求,却能在较短时间内给出一个较接近最优解 的可行解由此可行解出发,用适当的非线性规划算法可较快得出满足精度要求的最优解 以a(i=1,2,…,6)为变量,在模型二中我们已经将问题归结为非线性规划问题,主要 约 束条件为 )2, minD2(a,a1)≥64,(i,j=1,2,,6,i≠j), (1) 由于mnD2(a,a)的形式复杂,求导有困难,我们对(1)作一些改变,将目标函数改为
飞行管理问题的实时算法 S2.) i0 coai- cosa s nato 将变量改为C.0,S1,a(i=1,2,…,6)共12个,增加等式约束 (Ci:o cosa: 0)2+(S,io sina o)2=1 使问题(1)变为一个12个变量,21个2次约束条件的目标函数求极小值的问题 minf(X)=>(C2 i0+ S2. o) st.ga(X)=minD(C.0,C,0,S;,0,S,0)-64≥0, h2(X)=0,) (i=1,2,…,6), 工中 c6,60李 10,52,20 minD(C.0,C.0,S.0,S,0) (S1,0-5,0+5 x-((,0-(,0+C,j)·y )2 h, (X)=(C, :o+ cosa:0)2+(S,io sina:o)2-1 Himmelblau在文献[]中列举了三类12种算法,我们对这12种算法进行了比较,主要 是考虑其收敛速度的快慢,其次由于没有现成的软件包可供使用,必须自已编制有关程序 序准备时间的长短,即算法变为程序的复杂程度也必须考虑,综合上述两方面因素,我们 择了序列无约束最小化方法( Sequential Unconstrained Minimization Technique),简称 MT算法 SUMT算法的基本思想是重复地求解一系列无约束问题,它们的解在极限情况下趋于 线性规划问题的极小点算法的详细内容参见文献[1][2[3][4],现概述如下: 首先构造罚函数 P(X,,r)=f(X,)+re g;(X) r∑h3(X1), 中权因子r是一单调递减数列对每个r值求X,使p(X,4)取极小值设精度要求e, x-X-11<ε时结束运算,即为符合所需精度要求的最优解 对此具体问题,我们置 p(X,r)=f(X)+r-12hA(X)+r( Ingi(X)) n-0,n=m8101m,n= e=0.5×10-2 此问题编制程序SUMT1对题目中的数据进行运算,初始值用模型二以精度为1度时算出 量优值代入,结果如下: