A three-phase solution method for the scheduling problem of using earth observation satellites to observe polygon requests. (April 2019)

• Record Type: Journal Article
• Authors: Zhu, Waiming; Hu, Xiaoxuan; Xia, Wei; Sun, Haiquan
• Is Part Of: Computers & industrial engineering. Volume 130(2019)
• Page Start: 97
• Page End: 107
• Publication Date: 2019-04
• Subjects: EOS schedule -- Covering problem -- Polygon request -- Grid-based split; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.02.014
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A three-phase solution strategy is proposed to solve the scheduling problem. Corresponding algorithms are developed for the three phases, respectively. Several numerical tests are used to demonstrate that this strategy is competitive. Abstract: Thes cheduling problem of usingE arth observation satellites (EOSs) to observep olygon 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.