基于改进DK算法绕飞限制区的航线规划

摘 要：终端区内往往存在限制区，这些限制区的存在制约了飞行的流畅性，对于一些限制区可以提前向军方申请，引用动态航路概念。绕飞终端区时综合考虑航线长度、飞机性能等指标，选取航线经济性最优为目标函数，实现绕飞限制区的航线网络规划。实例表明，算法运行稳定，效率明显提高。
　　关键词：终端区限制区；航线规划；dijkstra算法
　　引言
　　终端区内航线网络是连接机场和航路的重要机构，但是目前国内的终端区航线规划是基于机场布局，导航设施和限制区进行人工设计，这样的设计方法显然存在着效率较低，设计方案缺乏科学验证等问题。文章重点是将航线自动生成映射到图论中的最短路径问题，引用dijkstra算法搜索出最优航线，引用终端区动态航路概念，通过终端区内限制区的航路即为条件航路，无论是军方还是民航，都不是永久和长期的使用条件航路，但可以在需要时候申请得到使用权，以减轻终端区航路拥堵。
　　1 限制区模型建立
　　二分法求解航线到限制区距离：
　　如图1所示，OA存在极小值，因为等角航线的曲率小于圆形空域的曲率所以极小值是唯一的。可以用数值解法求出近似值。这里选用改进的二分法直接求出OA的最小值如图所示。Y1（？准1，？姿1），Y2（？准2，？姿2）。先求？准1和？准2的均值？准3=？准1+？准2/2 由公式：
　　一点，并且经纬度是Y1，Y2的纬度中点。
　　计算OY和OY2的距离，判断OY1，OY2的大小。如果OY1？芏OY2则选择点Y2和点Y3重复上述步骤，求点Y2Y3的中点Y4，计算OY2和OY3的大小，可以看出这样迭代下去是YN收敛于A点。
　　2 求解任意两点间最短路径模型
　　2.1 带权图邻接矩阵
　　定义（带权有向图的邻接矩阵）设G=（V，E）是一个简单带权的有向图，V={v1，v2......vn}，则G的连接矩阵A=（Aij）是一个n阶方阵，其中：
　　如表2所示，1到16共16个点，在matlab中用M代替∞这里取M=10000，又由于表1各相邻点的距离都相等，这里取w=1，则表1对应的邻接矩阵如下：
　　2.2 算法步骤
　　上面已经给出了带权图邻接矩阵的定义，可以用带权图邻接矩阵求任意两点间的距离。
　　设A=（aij）n×k，B=（bij）k×m，定义Q=A？茚B=（qij）n×m其中qij=min{aij，bij}，现在讨论邻接矩阵应用这两种运算所产生的结果。讨论带权无向图的情形。设A=（aij）n×n是带权无向图G=（V，E）的邻接矩阵，记A（2）=A*A=（aij2）n×n，则有：aij（2）=min{ai1+a1j，ai2+a2j，......，ain+anj}这里的ai1+aj1表示从结点i到节点j的路径长度，ai2+aj2表示经过中间点2到结点j的路径长度，其余相类似，都表示从结点I到节点j的路径长度，aij（2）是取它们的最小值，它们的意义就是从结点I最多经过一个中间点到达结点j的所有路径中长度最短的那条路径。
　　所以最多经过一个中间点是因为一般项aij+akj（1？燮k？燮n）中也包含aii+aij和aii+ajj两项，他们都等于aij，如果他是所有项中的最小值，则aij（2）=aij，在这种情况下就没有经过中间点。同理可知，在A（k）=aij（k）m×n中，aij（k）表示从结点i最多经过（k-1）个中间点的到结点j的所有路径中最短的那条路径，即最短路径。
　　3 实例仿真
　　3.1 定义限制区类型
　　终端区中常常出现限制区，在我国，按照地面目标性质，可以将空中限制区分为民用和军用两种。民用限制区是在重要城市，经济等目标上空划定的空中限制区。军事限制区是在军事要地，兵器试验场上空和航空部队，飞行院校等航空单位的机场飞行空域规划的空中限制区。按照使用期限可以分为固定限制区和临时限制区。将固定限制区定义为A型限制区，将临时限制区定义为B型限制区，对于A型限制区来说，一般采取绕飞的形式。对于B型限制区可以提前和军方申请，经军方批准开放后，就可以在此空域内飞行。
　　3.2 实例分析
　　以S机场07L跑道为例，验证进基于dijkstra算法的进离场航线规划方法。如图2所示，终端区内分布3个高大的限制区：R501，R502，R503。选择规划航线起止点，选择航线Rd1，起始点ABTUB，终止点AGTIS，
　　3.3 算法比较
　　基于改进的dijkstra算法与传统dijkstra算法的比较：