多星联合任务规划中的启发式求解方法研究

A Heuristic Method for Earth Observing Satellites United Imaging Scheduling

多星联合任务规划问题需要考虑卫星侧视、星载存储容量、星上能量、数据传输等多种约束,是一个复杂的组合优化问题。通过对卫星成像约束条件抽象,建立联合规划的数学模型,将问题归约为特殊的多时间窗约束车辆装卸问题,面向应急条件下的应用,结合领域应用特点,提出基于动态装载概率模型和估算总装载量的启发式搜索任务规划算法(HADPPEC),并与实际运行的多星任务规划系统进行了大量实验比较。结果表明本方法比传统方法在运行时间和算法结果上都更出色。

Earth Observing Satellites（EOSs） imaging scheduling is characterized by multiple complex constraints, including power, thermal, data capacity, data transmission and the limited time each satellite spends over each target, thus is a complicated combinatorial optimization problem. We constructed a mathematical model for the problem by abstracting the imaging constraints of different EOSs, treated the problem as a special Pickup and Delivery Problem with Time Windows, and proposed a greedy heuristic algorithm which is based on dynamic pickup probability and estimated vehicle total pickup capability. At the end we carried out some experiments upon real application problems and compared with the now-using satellite imaging scheduling system. The result shows that the proposed approach outperformed the old approach on both execute time and the evaluation.