Ensemble of Metaheuristic and Exact Algorithm Based on the Divide-And-Conquer Framework for Multisatellite Observation Scheduling
Guohua Wu (Central South University China)
Qizhang Luo (Central South University China, National University of Singapore)
Xiao Du (Central South University China)
Yingguo Chen (National University of Defense Technology)
Ponnuthurai Nagaratnam Suganthan (Qatar University, Nanyang Technological University)
Xinwei Wang (TU Delft - Learning & Autonomous Control)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Satellite observation scheduling plays a significant role in improving the efficiency of Earth observation systems. To solve the large-scale multisatellite observation scheduling problem, this article proposes an ensemble of metaheuristic and exact algorithms based on a divide-And-conquer framework (EHE-DCF), including a task allocation phase and a task scheduling phase. In the task allocation phase, each task is allocated to a proper orbit based on a metaheuristic incorporated with a probabilistic selection and a tabu mechanism derived from ant colony optimization and tabu search, respectively. In the task scheduling phase, we construct a task scheduling model for every single orbit and solve the model by using an exact method (i.e., branch and bound, B&B). The task allocation and task scheduling phases are performed iteratively to obtain a promising solution. To validate the performance of the EHE-DCF, we compare it with B&B, three divide-And-conquer-based metaheuristics, and a state-of-The-Art metaheuristic. Experimental results show that the EHE-DCF can obtain higher scheduling profits and complete more tasks compared with existing algorithms. The EHE-DCF is especially efficient for large-scale satellite observation scheduling problems.