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

Model and algorithm for coordinated observation and data transmission scheduling of multi-airship and multi-payload by graph coloring theory

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

Near space platform is a category of rising space platforms,which can be used for local area earth observation.Focusing on characteristics of airships and complexity of users’requirements,this study designs a multi-airship and multi-payload coordinated observation and data transmission system,and considers scheduling of common observation tasks and rescheduling of emergency observation tasks.Based on graph coloring theory(GCT),a model for coordinated observation and data transmission scheduling of multi-airship and multi-payload is developed.Observation and data transmission tasks,conflicts between tasks,airships and ground stations are mapped into vertexes,edges and colors of the undirected graph,and then the problem is modelled as a graph coloring problem(GCP),the goal of maximizing the total benefits of completed tasks is transformed to maximizing the total benefits of colored vertexes.This study proposes a memetic algorithm(MA),which designs a Tabu search operator based on profit improvement to update chromosomes,and a crossover strategy to inherit consecutive genes with maximum income of parent chromosomes.Experimental results show that MA can get more satisfactory solutions in a reasonable time for different scale cases than Tabu search and ILOG CPLEX.