本发明公开了一种用于航线规划的最优路径生成方法，本发明是在仅输入部分转弯信息下，通过对航线进行分割和回溯处理，利用二叉树搜索和剪枝方法启发式的遍历所有可行航线，并提取当前输入信息下所能得到的最优航线，从而解决传统航线规划方法计算量大、耗时长的问题。本发明提出的方法能够根据实际系统环境和性能要求，调整搜索过程中的参数，从而保证本方法搜索到最优路径的耗时满足系统快速生成航线方案的实际需求。
1.一种用于航线规划的最优路径生成方法，其特征在于，包括如下步骤：步骤1，获取转弯点数据集合(P1,P2,...,PN)，Pi表示第i个转弯点，i取值为1～N，N为转弯点总数，转弯点数据即为航线转弯过程序列；
步骤4，将航线转弯过程序列表示为二叉树，计算得到所有转弯过程的全部信息；
步骤7，输出最优航线：搜索二叉树中性能最好的叶子节点，将根节点到叶子节点的路径提取并作为最优航线输出；
步骤2-1，经纬度坐标转换：将每个转弯点经纬度数据转换为XY坐标系下的坐标；
步骤2-2，转弯点类型标注：Ci＝1时表示第i个转弯过程的转弯开始点，Ci＝2时表示转弯圆心点，Ci＝3时表示转弯结束点；
步骤2-3，如果一个转弯点对应的转弯方向已经指定，则标注该转弯过程的转弯方向，Di＝1时表示顺时针转弯，Di＝-1时表示逆时针转弯；
步骤2-4，每个转弯过程由转弯开始点、转弯圆心点、转弯结束点和转弯方向唯一确定；
步骤3包括：假设第i个转弯点为转弯结束点，则分别将前后两侧离第i个转弯点最近的非转弯结束点的位置设置为航线分割点，根据该方法对整个航线进行分割得到子航线序列；
步骤4包括：通过二叉树的形式表示转弯过程序列，以上一个转弯过程为父节点进行分支，设置当前转弯方向顺时针为一个分支，当前转弯方向逆时针为另外一个分支，由于每个转弯过程由转弯方向、转弯开始点、转弯圆心点和转弯结束点唯一标识，当输入一个点信息后，该转弯过程的另外两个未知点的位置信息利用相邻转弯点已获取的信息进行解算，分为如下四种情况：情况一，已知当前转弯过程的转弯开始点和下一转弯过程的转弯开始点情况：情况一中，已知第i个转弯过程的转弯开始点位置坐标 和第i+1个转弯过程的转弯开始点位置坐标 则有如下方程：其中，(a,b)为转弯圆心点坐标 指向转弯结束点坐标 的向量,r为转弯半径，公式(1)中第一个方程表示向量长度等于转弯半径，第二个方程表示向量(a,b)与转出切线垂直，通过求解上述方程获得向量(a,b)的值，其中，转弯圆心点坐标 通过下述公式(2)获得：利用第i-1个转弯过程的转弯结束点位置坐标 和第i个转弯过程的转弯开始点位置坐标 得到第i个转弯过程转入切线与正北方向的夹角θ，则有：情况二，已知当前转弯过程的转弯开始点和下一转弯过程的转弯圆心点情况：情况二中，根据下一点的转弯方向有两种情况：顺时针和逆时针；
其中， 根据公式(2)得到，利用公式(4)和当前转弯过程的转弯方向，求出(a,b)，根据公式(3)得到当前转弯过程的转弯结束点信息；
其中， 根据公式(2)得到，利用公式(5)和当前转弯过程的转弯方向，求出(a,b)，根据公式(3)得到当前转弯过程的转弯结束点信息；
情况三，已知当前转弯过程的转弯圆心点和下一转弯过程的转弯圆心点情况：情况三中，计算出第i-1个转弯过程的转弯结束点到当前第i个转弯圆的切线，从而得到切线与正北方向的夹角θ，然后利用公式(2)计算出当前转弯过程的转弯开始点，根据第i+1个转弯过程的转弯方向，将公式(4)或者公式(5)与公式(3)进行联立求解，计算出当前转弯过程的转弯结束点信息，从而获得当前转弯过程的全部信息；
情况四，已知当前转弯过程的转弯圆心点和下一转弯过程的转弯开始点情况：情况四中，计算出第i-1个转弯过程的转弯结束点到当前第i个转弯圆的切线，从而得到切线与正北方向的夹角θ，然后利用公式(2)计算出当前转弯过程的转弯开始点，利用公式(1)和公式(3)计算出当前转弯过程的转弯结束点，从而获得当前转弯过程的全部信息；
在完成当前转弯过程的转弯信息计算后，取下一个转弯点对应的转弯过程，继续迭代计算，直至计算出本子航线序列的所有转弯过程信息。
2.根据权利要求1所述的方法，其特征在于，步骤4中，对于每个一个转弯过程的转弯距离和直线飞行距离按如下方式计算：步骤4-1，计算转弯开始点和转弯中心点的连线与水平方向的夹角；
步骤4-2，计算转弯结束点和转弯中心点的连线与水平方向的夹角；
步骤4-3，转弯角度即为步骤4-1和步骤4-2所述两个角度之差；
步骤4-5，利用当前转弯过程的转弯结束点和下一个转弯过程的转弯开始点位置信息，计算出相邻转弯过程的直线飞行距离。
3.根据权利要求2所述的方法，其特征在于，步骤5包括：当步骤4中的当前转弯过程对应的输入转弯点为转弯结束点时，停止正向二叉树搜索过程，从该子航线的最后一个输入转弯点开始逆向进行计算，此时对每个转弯过程的已有信息进行反转标识，即进行点属性更改和转弯方向更改，将转弯开始点和转弯结束点互换,将顺时针和逆时针互换,继续调用步骤4中的四种解算方法进行求解，得到每个转弯过程的信息，然后继续逆向取上一个转弯点的转弯过程进行迭代计算，直至计算出本子航线的所有转弯过程信息。
4.根据权利要求3所述的方法，其特征在于，步骤6包括：对于二叉树中的每个节点，除了保存该节点代表的转弯过程的转弯方向外，还存有该转弯过程的转弯距离和飞到下一个转弯过程的转弯开始点的直线飞行距离，每次步骤4和步骤5在完成一次转弯过程的计算后，会对新生成的节点进行计算，以得到从根节点到新生成的节点的总飞行距离，根据总飞行距离对新生成节点排序，如果当前新生成节点数未超过最大允许的分支数，则保留全部新节点，否则，按照总飞行距离对新节点进行排序，从大到小删除新节点及其分支，直至分支数小于设定的最大允许的分支数。
5.根据权利要求4所述的方法，其特征在于，步骤7包括：在完成所有转弯过程的转弯信息计算后，计算根节点到每个叶子节点的总飞行距离，并进行排序，将总飞行距离最短的叶子节点的路径提取，并将该路径下所有转弯过程的转弯方向、3种类型转弯点的位置输出，从而得到最优航线。
一种用于航线规划的最优路径生成方法
技术领域
[0001] 本发明涉及航线规划技术领域，尤其涉及一种用于航线规划的最优路径生成方法。
背景技术
[0002] 目前，航天航空技术正在不断快速发展，航线规划和绘制作为航天航空技术中的重要组成部分，也影响着军民航管理系统的运行效率。特别的，对于无人机飞行航线管理系统，在规划、绘制无人飞行器航线时，为了绘制方便，通常由操作人员在地图上绘出单点航线。对于每个航线点，其属性可以有三种类型，分别是转弯开始点、转弯圆心点和转弯结束点。对于不同位置的航线点，由于该航线点执行任务不同，相应点的属性也不同，例如无人机执行侦察任务时，通常选择转弯圆心点作为航线点，而在执行攻击投弹任务时，通常选择转弯开始点作为航线点。另外，操作人员在绘出航线点时，多数也不对转弯方向做要求，因此在完成单点航线绘制时，需要根据航线点类型对航线进行计算，选择合理的转弯方向以获得最优航线。
[0003] 基于航线单点的航线规划问题主要面临如下几个难点。首先，由于输入的转弯单点信息不完整，例如一些转弯单点无转弯方向信息，飞行器的飞行航线有多种可能。对于每一个转弯过程，其转弯方向有2种可能，因而所有可能飞行航线数与转弯点数成指数增长关系。因此，如何在指数增长的解空间中搜索到最优飞行航线是航线规划的一个主要难点。其次，飞行航线管理系统通常对最优航线的计算时间有要求。由于可行的飞行航线数目过于庞大，通过遍历搜索最优飞行航线的常规方法会由于计算异常耗时的原因而不可行。因此，如何在庞大的解空间中快速的搜索到最优飞行航线也是一个主要难点。最后，当每个转弯过程的飞行航向已知时，如果输入的转弯单点中无转弯结束点，则每个转弯单点可以通过利用前面相邻点的转弯三点信息(转弯开始点、圆心点、结束点)和后面相邻点的位置唯一确定当前转弯过程的全部信息。但是当输入的转弯单点中存在转弯结束点时，该转弯结束点对应的转弯过程信息可能无法按照上述方法求出(例如若干个转弯结束点相邻的情况)。因此，如何有效的处理转弯结束点情况也是航线规划的一个难点。
[0004] 近年来，航线规划作为飞行航线管理系统的核心功能，得到了很多关注。常见的航线规划方法有动态规划方法[陈长林,孙迈,宋顺达.基于Voronoi图的突防航线动态规划.指挥控制与仿真,2009,31(5):27-29]、粒子群方法[吴逸,李强,代科学,王国师.基于粒子群算法的预警机航线规划.空军雷达学院学报,2010,24(6):410-413]、A*方法[周荣坤,黄丽芳.一种航线规划算法应用.火力与指挥控制,2010,35(6):176-182]等。对于基于航线单点的航迹规划问题，已有传统方法没有针对航线单点这种输入信息进行航线规划，并且忽略了飞行器的转弯过程。另外，已有传统方法通常是利用一些基于迭代的优化方法进行启发式搜索，这类方法面临迭代耗时、收敛速度慢的问题，因而不能满足飞行航线管理系统的实际应用需求。
发明内容
[0005] 为了解决无人机飞行管理系统中的航线规划问题，本发明提供了一种基于二叉树分割搜索和剪枝的最优航线规划方法。
[0006] 现有的航线规划方法需要利用基于迭代的优化方法进行求解，面临计算耗时的困难。为了提高航线规划的计算效率，本发明要利用启发式信息，限制遍历搜索的可行解空间，保证搜索方向维持在最优航线解的方向，从而实现航线规划方案的快速生成。
[0007] 所采用的技术方案是：基于二叉树分割搜索和剪枝的最优航线规划方法，包括如下步骤：
[0008] 步骤1，假设操作人员共绘出了N个航线单点。获取转弯点数据集合(P1,P2,...,PN)，Pi表示第i个转弯点，i取值为1～N，N为转弯点总数；
[0009] 步骤2，对转弯点数据进行预处理，完成经纬度坐标转换、转弯点类型标注、转弯过程属性标注功能；
[0010] 步骤3，对航线进行分割处理：根据转弯点类型，对整个航线进行分割得到子航线序列，并保存每个子航线，作为航线二叉树搜索、回溯、剪枝处理的输入；
[0011] 步骤4，将航线转弯过程序列表示为二叉树，计算得到所有转弯过程的全部信息：针对每个子航线，计算每个转弯点对应的转弯过程的可能转向，并作为新的叶子节点插入到当前二叉树；依据相邻两个转弯过程的转弯点类型，计算相邻两个转弯过程的转弯距离、直线飞行距离；
[0012] 步骤5，对子航线回溯处理：针对子航线中出现转弯点类型为转弯结束点的情况，采用回溯处理的方法，从子航线最后一个转弯过程向前递推，计算每个转弯过程的可能转向，插入到当前二叉树，并计算相应的转弯距离和直线飞行距离；
[0013] 步骤6，对二叉树进行剪枝：根据系统的硬件条件和性能要求，设置二叉树最大允许分支数，对二叉树每个叶子节点的性能(即当前已飞行距离)进行排序，根据二叉树最大允许分支数进行剪枝；
[0014] 步骤7，输出最优航线：搜索二叉树中性能最好的叶子节点，将根节点到叶子节点的路径提取并作为最优航线输出。
[0015] 步骤2包括：
[0016] 步骤2-1，经纬度坐标转换：将每个转弯点经纬度数据转换为XY坐标系下的坐标；
[0017] 步骤2-2，转弯点类型标注：Ci＝1时表示第i个转弯过程的开始点，Ci＝2时表示转弯圆心点，Ci＝3时表示转弯结束点；
[0018] 步骤2-3，如果一个转弯点对应的转弯方向已经指定，则标注该转弯过程的转弯方向，Di＝1时表示顺时针转弯，Di＝-1时表示逆时针转弯；
[0019] 步骤2-4，每个转弯过程由转弯开始点、转弯圆心点、转弯结束点和转弯方向唯一确定。
[0020] 步骤3包括：假设第i个转弯点为转弯结束点，则分别将前后两侧离第i个转弯点最近的非转弯结束点的位置设置为航线分割点，根据该方法对整个航线进行分割得到子航线序列。
[0021] 步骤4包括：通过二叉树的形式表示转弯过程序列，以上一个转弯过程为父节点进行分支，设置当前转弯方向顺时针为一个分支，当前转弯方向逆时针为另外一个分支。由于每个转弯过程可以由转弯方向、转弯开始点、圆心点和结束点唯一标识，当操作人员输入一个点信息后，该转弯过程的另外两个未知点的位置信息可以利用相邻转弯点已获取的信息进行解算，分为如下四种情况：
[0022] 情况一，转弯开始点和转弯开始点情况：
[0023] 情况一中，已知第i个转弯过程的转弯开始点位置坐标 和第i+1个转弯过程的转弯开始点位置坐标 则有如下方程：
[0024]
[0025] 其中，(a,b)为转弯圆心点坐标 指向转弯结束点坐标 的向量,r为转弯半径，公式(1)中第一个方程表示向量长度等于转弯半径，第二个方程表示向量(a,b)与转出切线垂直，通过求解上述方程获得向量(a,b)的值，利用第i-1个转弯过程的转弯结束点位置坐标 和第i个转弯过程的转弯开始点位置坐标 得到第i个转弯过程转入切线与正北方向的夹角θ，则有：
[0026]
[0027]
[0028] 情况二，转弯开始点和转弯圆心点情况：
[0029] 情况二中，根据下一点的转弯方向有两种情况：顺时针和逆时针；
[0030] 当下一点转弯方向为顺时针时，有如下方程：
[0031]
[0032] 其中， 根据公式(2)得到，利用公式(4)和当前转弯过程的转弯方向，求出(a,b)，根据公式(3)得到当前转弯过程的转弯结束点信息；
[0033] 当下一点转弯方向为逆时针时，有如下方程：
[0034]
[0035] 根据该公式(5)得到当前转弯过程的转弯圆心点和结束点信息；
[0036] 情况三，转弯圆心点和转弯圆心点情况：
[0037] 情况三中，可以计算出第i-1个转弯过程的转弯结束点到当前第i个转弯圆的切线，从而得到切线与正北方向的夹角θ。然后，利用公式(2)即可计算出当前转弯过程的转弯开始点。根据第i+1个转弯过程的转弯方向，将公式(4)或者公式(5)与公式(3)进行联立求解，即可计算出当前转弯过程的转弯结束点信息，从而获得当前转弯过程的全部信息；
[0038] 情况四，转弯圆心点和转弯开始点情况：
[0039] 情况四中，可以计算出第i-1个转弯过程的转弯结束点到当前第i个转弯圆的切线，从而得到切线与正北方向的夹角θ。然后，利用公式(2)即可计算出当前转弯过程的转弯开始点，利用公式(1)和公式(3)即可计算出当前转弯过程的转弯结束点，从而获得当前转弯过程的全部信息；
[0040] 在完成当前转弯过程的转弯信息计算后，取下一个转弯点对应的转弯过程，继续迭代计算，直至计算出本子航线序列的所有转弯过程信息。
[0041] 步骤4中，对于每个一个转弯过程的转弯距离和直线飞行距离按如下方式计算：
[0042] 步骤4-1，计算转弯开始点和转弯中心点的连线与水平方向的夹角；
[0043] 步骤4-2，计算转弯结束点和转弯中心点的连线与水平方向的夹角；
[0044] 步骤4-3，转弯角度即为步骤4-1和步骤4-2所述两个角度之差；
[0045] 步骤4-4，转弯距离即为转弯角度乘以转弯半径；
[0046] 步骤4-5，利用当前转弯过程的转弯结束点和下一个转弯过程的转弯开始点位置信息，,计算出相邻转弯过程的直线飞行距离。
[0047] 步骤5包括：当步骤4中的当前转弯过程对应的输入转弯点为转弯结束点时，停止正向二叉树搜索过程，从该子航线的最后一个输入转弯点开始逆向进行计算，此时对每个转弯过程的已有信息进行反转标识，即进行点属性更改和转弯方向更改，将转弯开始点和结束点互换,将顺时针和逆时针互换,继续调用步骤4中的四种解算方法进行求解，得到每个转弯过程的信息，然后继续逆向取上一个转弯点的转弯过程进行迭代计算，直至计算出本子航线的所有转弯过程信息。
[0048] 步骤6包括：对于二叉树中的每个节点，除了保存该节点代表的转弯过程的转向外，还存有该转弯过程的转弯飞行距离和飞到下一个转弯过程开始点的直线飞行距离，每次步骤4和步骤5在完成一次转弯过程的计算后，会对新生成的节点进行计算，以得到从根节点到新生成的节点的总飞行距离，根据总飞行距离对新生成节点排序，如果当前新生成节点数未超过最大允许的分支数，则保留全部新节点，否则，按照总飞行距离对新节点进行排序，从大到小删除新节点及其分支，直至分支数小于设定的最大允许的分支数。
[0049] 步骤7包括：在完成所有转弯过程的转弯信息计算后，计算根节点到每个叶子节点的总飞行距离，并进行排序，将总飞行距离最短的叶子节点的路径提取，并将该路径下所有转弯过程的转弯方向、3种类型(转弯开始点、圆心点、结束点)转弯点的位置输出，从而得到最优航线。
[0050] 有益效果：本发明实现过程中不需要进行迭代优化计算，并且通过航线分割和剪枝的方法能够限制最优航线搜索空间，相比于传统的规划方法，具有计算负担小，能够满足系统快速生成最优航线方案的需求。
[0051] 本发明能够根据输入的部分转弯信息自动对航线进行分割，并对每个子航线进行二叉树搜索、剪枝和回溯处理，从而能够解决传统方法在求解最优航线时面临的高计算量困难；本发明能够根据系统的硬件条件调整搜索算法的参数，保证本发明搜索到最优路径的耗时满足系统实际需求。
附图说明
[0052] 下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述或其他方面的优点将会变得更加清楚。
[0053] 图1是本发明的航线规划方法原理框图。
[0054] 图2是转弯点类型示意图。
[0055] 图3是本发明的二叉搜索树示意图。
[0056] 图4a～图4c是本发明方法的转弯点信息解算示意图。
[0057] 图5a～图5b是本发明方法确定的航迹规划路径和计算时间图。
具体实施方式
[0058] 下面结合附图及实施例对本发明做进一步说明。
[0059] 如图1所示，本发明主要包括：初始化模块、数据预处理模块、航线分割模块、航线二叉树搜索模块、子航线回溯处理模块、航线二叉树剪枝模块以及最优航线提取输出模块。结合流程图说明具体实现步骤为：
[0060] 步骤1：初始化。通过操作人员输入获得转弯点的信息集合，该集合表示为P1,P2,...,PN，其中转弯点总数为N；
[0061] 步骤2：数据预处理。对输入的转弯点信息集合进行标注，完成坐标转换(WGS84经纬度转换为XY坐标系、CGCS2000经纬度转换为XY坐标系)、转弯点类型标注(Ci＝1表示第i个转弯过程的开始点，Ci＝2表示转弯圆心点，Ci＝3表示转弯结束点)。如果该转弯点对应的转弯方向已经指定，则标注该转弯过程的转弯方向(Di＝1表示顺时针转弯，Di＝-1表示逆时针转弯)。具体转弯点类型如图2所示，可以看出，每个转弯过程由转弯开始点、圆心点、结束点和转弯方向唯一确定(在本发明中假设飞行器的转弯半径固定)。
[0062] 步骤3：航线分割处理。当操作人员输入的转弯点类型存在转弯结束点时，无法通过前面相邻的转弯过程信息确定当前转弯点(转弯结束点)对应的转弯过程信息。为了解决上述困难，本发明提出了一种航线分割方法，其分割思想如下。假设第i个转弯点为转弯结束点，则分别将前后两侧离第i个转弯点最近的非转弯结束点的位置设置为航线分割点。例如，假设转弯点的类型序列为(3 3 1 3 2 2 1 3 3 1)，则该航线可以分割为(3 3 1)、(1 3 2)、(2 2 1)、(1 3 3 1)四段子航线序列。对于每条子航线序列，由于最后一个转弯点非转弯结束点，因此后续可以采用回溯的方法求解每条子航线序列的所有可能航线，从而解决正向计算无法处理转弯结束点的难点。具体回溯方法见步骤5；
[0063] 步骤4：航线二叉树搜索。每个转弯过程由转弯开始点、圆心点、结束点和转弯方向唯一确定，在计算当前转弯过程的剩余信息时(除当前转弯点外的另外2个点和转弯方向)，对于转弯方向，由于当前转弯过程可能有两种飞行方向，因此可以通过二叉树的形式表示转弯过程序列，以上一个转弯过程为父节点进行分支，如图3所示(1表示顺时针飞行，-1表示逆时针飞行，正向计算时j＝i+1)；对于转弯过程的另外2个点的位置信息，需要利用相邻转弯点已获取的信息进行解算，可以分为如下四种情况：
[0064] 情况一，转弯开始点-转弯开始点情况：
[0065] 如图4a所示，情况一中，已知第i个转弯过程的转弯开始点位置 和第i+1个转弯过程的转弯开始点位置 则有如下方程：
[0066]
[0067] 其中，(a,b)为转弯圆心点 指向转弯结束点 的向量,r为转弯半径。上式第一个方程表示向量长度等于转弯半径，第二个方程表示向量(a,b)与转出切线垂直。
通过求解上述方程即可获得向量(a,b)的值(存在两组可能值，结合第i个转弯过程的转弯方向可以去除一组解)。另外，由于第i-1个转弯过程的转弯信息此时已完全已知，因此可以利用 和 得到第i个转弯过程转入切线与正北方向的夹角θ，则有：
[0068]
[0069]
[0070] 需要注意的是，上式中右边的+/-号取决于当前转弯过程的转弯方向，推导过程类似。
[0071] 情况二，转弯开始点-转弯圆心点情况：
[0072] 如图4b和图4c所示，情况二中，根据下一点的转弯方向有两种情况：顺时针(图4b)和逆时针(图4c)。
[0073] 当下一点转弯方向为顺时针时，有如下方程：
[0074]
[0075] 其中， 可以根据公式(2)得到。利用公式(4)和当前转弯过程的转弯方向，可以求出(a,b)。根据公式(3)即可得到当前转弯过程的转弯结束点信息。
[0076] 当下一点转弯方向为逆时针时，有如下方程：
[0077]
[0078] 类似，可以得到当前转弯过程的转弯圆心点和结束点信息。
[0079] 情况三，转弯圆心点-转弯圆心点情况：
[0080] 情况三中，可以计算出第i-1个转弯过程的转弯结束点到当前第i个转弯圆的切线，从而得到切线与正北方向的夹角θ。然后，利用公式(2)即可计算出当前转弯过程的转弯开始点。根据第i+1个转弯过程的转弯方向，将公式(4)或者公式(5)与公式(3)进行联立求解，即可计算出当前转弯过程的转弯结束点信息，从而获得当前转弯过程的全部信息。
[0081] 情况四，转弯圆心点-转弯开始点情况：
[0082] 情况四中，可以计算出第i-1个转弯过程的转弯结束点到当前第i个转弯圆的切线，从而得到切线与正北方向的夹角θ。然后，利用公式(2)即可计算出当前转弯过程的转弯开始点，利用公式(1)和公式(3)即可计算出当前转弯过程的转弯结束点，从而获得当前转弯过程的全部信息。
[0083] 在完成当前转弯过程的转弯信息计算后，取下一个转弯点对应的转弯过程，继续迭代计算，直至本子航线序列的所有转弯过程信息已全部计算出。对于每个一个转弯过程的转弯距离按如下方式计算：
[0084] (a)计算转弯开始点和转弯中心点的连线与水平方向的夹角；
[0085] (b)计算转弯结束点和转弯中心点的连线与水平方向的夹角；
[0086] (c)转弯角度即为上述两个角度之差；
[0087] (d)转弯距离即为转弯角度乘以转弯半径；
[0088] 利用当前转弯过程的转弯结束点和下一个转弯过程的转弯开始点位置信息，即可计算出相邻转弯过程的直线飞行距离。
[0089] 步骤5：子航线回溯处理。当步骤4中的当前转弯过程对应的输入转弯点为转弯结束点时，停止正向二叉树搜索过程，从该子航线的最后一个输入转弯点开始逆向进行计算，此时对每个转弯过程的已有信息进行反转标识，即点属性更改(转弯开始点、结束点互换),转弯方向更改(顺时针、逆时针互换),此时图3中有j＝i-1。继续调用步骤4中介绍的四种解算方法进行求解，完善每个转弯过程的信息。然后继续逆向取上一个转弯点的转弯过程进行迭代计算，直至本子航线的所有转弯过程信息已全部计算出。
[0090] 步骤6：航线二叉树剪枝。对于二叉树中的每个节点，除了保存该节点代表的转弯过程的转向外，还存有该转弯过程的转弯飞行距离和飞到下一个转弯过程开始点的直线飞行距离。每次步骤4和步骤5在完成一次转弯过程的计算后，会对新生成的节点进行计算，以得到从根节点到新生成的节点的总飞行距离。然后根据总飞行距离对新生成节点排序，如果当前新生成节点数未超过最大允许的分支数，则保留全部新节点。否则，按照总飞行距离对新节点进行排序，删除总飞行距离较大的新节点及其分支，如图3所示(颜色越深表示总飞行距离越短，最后两个新节点及其分支被删除)。
[0091] 步骤7：最优航线提取输出。在完成所有转弯过程的转弯信息计算后，计算根节点到每个叶子节点的总飞行距离，并进行排序。将总飞行距离最短的叶子节点的路径提取，并将该路径下所有转弯过程的转弯方向、3种类型转弯点的位置输出，从而完成最优航线的规划。
[0092] 本发明的实验结果如图5a和图5b所示。其中，硬件环境为：CPUi7-4770，内存8G，在航迹规划时，二叉树的最大允许分支数设为300。图5a展示了20个转弯过程的最优航线计算结果，其中圆点表示操作人员输入的每个转弯过程的转弯单点，该单点类型是随机生成。图5b展示了本发明方法的计算时间随转弯点数变化的关系。从图5a和图5b可以看出，本发明可以快速有效的搜索到较优的航线路径，计算耗时不超过2秒。在实际使用时，根据硬件条件可以适当修改最大分支数目
[0093] 本发明的特点包括：本发明中航线分割处理、子航线回溯处理能解决输入航线单点存在转弯结束点而无法正向解算的困难，二叉树搜索和剪枝则可以解决传统航线搜索方法遍历搜索或者迭代优化搜索耗时多的难点。在二叉树剪枝时，基于实际系统的硬件运行环境和使用人员的实际航线规划时间要求，可以动态的调整二叉树的最大允许分支参数，保证本发明能在规定时间内输出有效航线。
[0094] 本发明提供了一种用于航线规划的最优路径生成方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。
