基于 BSP 和动态规划的大规模空域扇区划分

摘要

In order to improve the efficiency and accuracy of large-scale airspace sector partition algorithm,this paper studied sector optimum partition combined with binary space partitions(BSP)and dynamic programming.After analysis of the structure of airspace and the spatial distribution of air traffic flow,it established an airspace graph model of traffic flow and constraints. BSP algorithm could balance average flow effectively.By dynamic programming it presented a multiple stages optimum BSP method to search minimal coordination flow.And it improved efficiency of the algorithm.The simulation results show that it can balance the average flow between sectors,and the optimization of minimal coordination flow is a suboptimal solution.The running time of dividing 10 sectors is about 4 min.%为了解决大范围管制空域划分为多扇区时的算法效率和准确性问题，研究了结合二叉空间分割和动态规划的空域扇区优化划分方法。在分析了管制空域结构和交通流量分布的基础上，提出了空域交通流量图模型和扇区边界优化的约束条件。应用二叉空间分割算法实现了扇区间平均流量的均衡，结合动态规划方法提出了逐阶段动态搜索协调流量最小的二叉空间分割算法，解决了算法运行效率低的问题。仿真实例表明，该方法均衡了不同扇区间的平均流量，保证了协调流量最小的优化结果为一个次优解。划设10个扇区时的运行时间约为4 min。