A three-phase solution method for the scheduling problem of using earth observation satellites to observe polygon requests

摘要

The scheduling problem of using Earth observation satellites (EOSs) to observe polygon requests (SEP), which is a large-scale nonlinear combinatorial optimization problem in a continuous solution space, is strongly coupled with computational geometry. We propose a novel three-phase solution method, which consists of grid-based split, cover optimization and strip selection, for solving the problem. The grid-based split generates numerous flexible strips and the cover optimization involves the pre-selection of the strips for covering each polygon. At last, the strip selection computes the final schedule for each EOS according to the results of the pre-selection. We develop an effective dynamic greedy algorithm for the second phase and tabu search algorithm for the third phase. We perform numerical tests on the simulated instances to verify the advantages of our method against seven other solution methods. The results show that the proposed method outperforms the other solution methods in the case of all the tested instances and parameter settings.