图切割快速生成扇区的蚁群算法

摘要

扇区划分是平衡管制员工作负荷、提升空域通行能力的有效技术措施。采用Voronoi图自顶向下切割空域的方法具有自动保证扇区凸性、连通性和压缩性的特性,但计算时间过长。根据航迹状态计算工作负荷,构建了Voronoi图自顶向下切割空域模型,设计了动态步长蚁群搜索算法。测试结果表明,在太原高空划分成4个扇区的情况下,与MC-CLFV(Monte Carlo method by changing location of flexible vertices)算法相比较,采用动态步长蚁群搜索算法求解,扇区的不平衡性显著减少,总工作负荷也减少了11.2%。大规模重复实验表明,随扇区数量增加,解的质量差异减少,但解的效率差异却不断增大,划分8个扇区时,动态步长蚁群搜索算法的计算时间统计中位数值仅为MC-CLFV算法的1/10。这说明该算法在一次划分数量少的时候,质量高而且计算时间短,在采用多层规划扇区的时候,应该采用组合数字和较小的划分方案。研究结果为采用Voronoi图直接切割空域形成管制扇区奠定了基础。