A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling
Joint Authors
Xing, Lining
Chu, Xiaogeng
Chen, Yuning
Source
Discrete Dynamics in Nature and Society
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-15, 15 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-09-07
Country of Publication
Egypt
No. of Pages
15
Main Subjects
Abstract EN
The agile earth observing satellite scheduling (AEOSS) problem consists of scheduling a subset of images among a set of candidates that satisfy imperative constraints and maximize a gain function.
In this paper, we consider a new AEOSS model which integrates a time-dependent temporal constraint.
To solve this problem, we propose a highly efficient branch and bound algorithm whose effective ingredients include a look-ahead construction method (for generating a high quality initial lower bound) and a combined use of three pruning strategies (which help to prune a large portion of the search space).
We conducted computational experiments on a set of test data that were generated with information from real-life scenarios.
The results showed that the proposed algorithm is efficient enough for engineering application.
In particular, it is able to solve instances with 55 targets to optimality within 164 seconds on average.
Furthermore, we carried out additional experiments to analyze the contribution of each key algorithm ingredient.
American Psychological Association (APA)
Chu, Xiaogeng& Chen, Yuning& Xing, Lining. 2017. A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling. Discrete Dynamics in Nature and Society،Vol. 2017, no. 2017, pp.1-15.
https://search.emarefa.net/detail/BIM-1151707
Modern Language Association (MLA)
Chu, Xiaogeng…[et al.]. A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling. Discrete Dynamics in Nature and Society No. 2017 (2017), pp.1-15.
https://search.emarefa.net/detail/BIM-1151707
American Medical Association (AMA)
Chu, Xiaogeng& Chen, Yuning& Xing, Lining. A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling. Discrete Dynamics in Nature and Society. 2017. Vol. 2017, no. 2017, pp.1-15.
https://search.emarefa.net/detail/BIM-1151707
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1151707