A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2017-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2017/7345941 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832560492262981632 |
|---|---|
| author | Xiaogeng Chu Yuning Chen Lining Xing |
| author_facet | Xiaogeng Chu Yuning Chen Lining Xing |
| author_sort | Xiaogeng Chu |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-cbad55639a5448e394a5e2e4e5e35a4a |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2017-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-cbad55639a5448e394a5e2e4e5e35a4a2025-02-03T01:27:28ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2017-01-01201710.1155/2017/73459417345941A Branch and Bound Algorithm for Agile Earth Observation Satellite SchedulingXiaogeng Chu0Yuning Chen1Lining Xing2College of Information Systems and Management, National University of Defense Technology, Changsha, Hunan 410073, ChinaCollege of Information Systems and Management, National University of Defense Technology, Changsha, Hunan 410073, ChinaCollege of Information Systems and Management, National University of Defense Technology, Changsha, Hunan 410073, ChinaThe 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.http://dx.doi.org/10.1155/2017/7345941 |
| spellingShingle | Xiaogeng Chu Yuning Chen Lining Xing A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling Discrete Dynamics in Nature and Society |
| title | A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling |
| title_full | A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling |
| title_fullStr | A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling |
| title_full_unstemmed | A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling |
| title_short | A Branch and Bound Algorithm for Agile Earth Observation Satellite Scheduling |
| title_sort | branch and bound algorithm for agile earth observation satellite scheduling |
| url | http://dx.doi.org/10.1155/2017/7345941 |
| work_keys_str_mv | AT xiaogengchu abranchandboundalgorithmforagileearthobservationsatellitescheduling AT yuningchen abranchandboundalgorithmforagileearthobservationsatellitescheduling AT liningxing abranchandboundalgorithmforagileearthobservationsatellitescheduling AT xiaogengchu branchandboundalgorithmforagileearthobservationsatellitescheduling AT yuningchen branchandboundalgorithmforagileearthobservationsatellitescheduling AT liningxing branchandboundalgorithmforagileearthobservationsatellitescheduling |