基于图着色理论的多飞艇多载荷协同对地观测和数据传输调度模型与算法

作者：周光辉; 敬帅; 梁伟

来源：系统工程理论与实践, 2021, 41(09): 2338-2354.

• 调度
• 对地观测
• 飞艇
• 图着色理论(graph coloring theory
• GCT)
• 文化基因算法(memetic algorithm
• MA)

临近空间平台是一类新兴的空间平台,可用于局部区域的对地观测.本文针对飞艇的特性和用户需求的复杂性,设计了多飞艇多载荷协同对地观测和数据传输体系,考虑常规观测任务的调度,以及应急观测任务的重调度.基于图着色理论(graph coloring theory, GCT),构建多飞艇多载荷协同对地观测和数据传输调度模型.将多飞艇协同对地观测与数据传输任务、任务间的冲突、以及飞艇和地面站分别映射为无向图中的点、边和颜色,从而将问题构建为图着色问题(graph coloring problem,GCP),最大化完成任务总收益的优化目标转换为GCP中最大化着色点收益.提出一种文化基因算法(memetic algorithm,MA),设计基于收益改进的禁忌搜索(Tabu search,TS)算子更新染色体,和对父代染色体中最大收益的连续基因进行遗传的交叉策略.数值实验结果表明,针对不同规模的算例,相较于TS和ILOG CPLEX, MA能够在合理时间内获得更满意的解.

• 单位
  中国科学院大学