多飞艇协同对地观测和数据传输调度模型与算法研究

浮空器已经发展成为空间遥感信息获取的重要平台之一.本文针对飞艇的资源特性和需求的复杂性,设计了多飞艇协同对地观测和数据传输工作体系.综合考虑多飞艇协同对地观测和数据传输任务的协调优化,将观测任务和数据传输任务视为有向图中顶点,用飞艇在执行先后序列任务的地理位置间的巡航时间来度量有向图中顶点间的距离,将问题转换为带时间窗口的多车场开放式车辆路径问题(multi depot open vehicle routing problem with time windows,MDOVRPTW),并以最大化总收益作为优化目标,构建多飞艇协同对地观测和数据传输任务调度的混合整数规划模型.提出一种文化基因算法(memetic algorithm,MA),嵌套广义阈值算法(generalized threshold algorithm,GTA)计算染色体中各飞艇总巡航时间最短的任务序列,实现对地观测和数据传输资源的优化分配.研究发现,针对不同规模的算例,并与CPLEX计算结果比较,算法能够在较短的时间内获得满意的解.

Model and algorithm of multi-airship coordinated earth observation and data transmission scheduling

The aerostat has developed into an important platform of spatial sensing information acquisition. Considering characteristics of airship and complexity of requirements, this study designs a multi-airship coordinated earth observation and data transmission scheduling system. To coordinately optimize multi-airship coordinated earth observation and data transmission tasks, earth observation tasks and data transmission tasks are regarded as the vertices in the directed graph, and distance between vertices is measured by cruising time between the geographic locations of an airship execute two consecutive tasks, so that the problem is transformed to multi depot open vehicle routing problem with time windows (MDOVRPTW). A mixed integer linear programming model is developed with the optimization objective of maximizing total reward of airships' coordinated observation and data transmission scheduling. A memetic algorithm (MA) is proposed by nesting a generalized threshold algorithm (GTA) to calculate airship's task sequence with shortest total cruising time, so to realize coordinated optimization of observation and data transmission resources. Experiments show that, compared with result by ILOG CPLEX, MA can obtain satisfactory solutions in a short time for different scales of instances.