An Efficient Local Search Heuristic for Earth Observation Satellite Integrated Scheduling
Open accessThe DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Abstract
Earth observation satellites (EOSs) are taking a large number of pictures with increasing resolution which produce massive image data. Satellite data transmission becomes the bottleneck part in the process of EOS resource management. In this paper, we study the earth observation satellite integrated scheduling problem (EOSIS) where the imaging activities and download activities are considered integratively. We propose an integer linear programming model to formulate the problem. Due to the NP-hardness of the problem, we propose an efficient local search heuristic (ELSH) to solve problems of large size. ELSH uses a dedicated local search method to guarantee algorithm performance and efficient constraint handling mechanisms to guarantee algorithm efficiency. Numerical experimental results show that the algorithm demonstrates excellent performance on a set of benchmark instances. The ELSH achieves optimal results for all small-size instances (with 50 targets, two satellites, and three ground stations), and is very robust for large instances with up to 2000 targets. Moreover, the proposed ELSH easily dominates the state-of-the-art algorithm.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“The first category mission planning method can only deal with small scale point targets and greatly increases the computational complexity of the model, with a sharp increase in the number of point targets.”
From Integrated Imaging Mission Planning Modeling Method for Multi-Type Targets for Super-Agile Earth Observation Satellite (2022) · cites this paper as [14]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“The first category directly treats each point target as an atomic task [2, 9-14]”
From Integrated Imaging Mission Planning Modeling Method for Multi-Type Targets for Super-Agile Earth Observation Satellite (2022) · cites this paper as [14]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
F-Race and Iterated F-Race: An Overview
Birattari, M., Yuan, Z., Balaprakash, P., & Stützle, T. (2010) · Experimental Methods for the Analysis of Optimization Algorithms · doi:10.1007/978-3-642-02538-9_13 · Cited by 413 · cited 1×
“To achieve a reasonable tuning of the parameters and a good algorithm performance, we adopt the iterated F-race (IFR) method, which allows an automated parameter configuration [30].”
MethodThree Scheduling Algorithms Applied to the Earth Observing Systems Domain
Wolfe, W. J., & Sorensen, S. E. (2000) · Management Science · doi:10.1287/mnsc.46.1.148.15134 · Cited by 313 · cited 2×
“The scheduling of earth observation satellite is an NP-hard problem [5]; therefore, the EOSIS problem is also an NP-hard problem.”
BackgroundLiu, X., Laporte, G., Chen, Y., & He, R. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.04.006 · Cited by 250 · cited 1×
“• Random removal: Select q requests from a given solution (schedule) randomly and remove them; • Priority removal: Iteratively removes the request with the lowest profit until the request bank is full; • Opportunity removal: Iteratively removes the request with the largest number of VTWs; ties are first broken by prof…”
BackgroundSelf-citationAn improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling
He, L., Liu, X., Laporte, G., Chen, Y., & Chen, Y. (2018) · Computers & Operations Research · doi:10.1016/j.cor.2018.06.020 · Cited by 200 · cited 3×
“We extend the benchmark instances proposed by [13] by including three well-known Chinese ground stations, namely JiaMusi, KaShi, and SanYa, whose precise locations can be found in [23].”
BackgroundMethodSelf-citationWang, P., Reinelt, G., Gao, P., & Tan, Y. (2011) · Computers & Industrial Engineering · doi:10.1016/j.cie.2011.02.015 · Cited by 195 · cited 1×
“[7] used branch and price to solve the imaging scheduling problem.”
MethodHybridizing genetic algorithms with hill-climbing methods for global optimization: two possible ways
Renders, J.-M., & Bersini, H. (2002) · Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence · doi:10.1109/icec.1994.349948 · Cited by 185
A mixed integer linear programming model for multi-satellite scheduling
Chen, X., Reinelt, G., Dai, G., & Spitz, A. (2019) · European Journal of Operational Research · doi:10.1016/j.ejor.2018.11.058 · Cited by 162 · cited 2×
“[8] considered a simplified version of the problem and formulated the problem as a MIP model.”
BackgroundPlanning and scheduling algorithms for the COSMO-SkyMed constellation
Bianchessi, N., & Righini, G. (2008) · Aerospace Science and Technology · doi:10.1016/j.ast.2008.01.001 · Cited by 148 · cited 1×
“In reality, the scheduling of EOSs with separate considerations for imaging and data transmission is quite difficult because the two operations are highly coupled [4].”
BackgroundGenetic Algorithms for Satellite Scheduling Problems
Xhafa, F., Sun, J., Barolli, A., Biberaj, A., & Barolli, L. (2012) · Mobile Information Systems · doi:10.1155/2012/717658 · Cited by 108
Swarm satellite mission scheduling & planning using Hybrid Dynamic Mutation Genetic Algorithm
Zheng, Z., Guo, J., & Gill, E. K. A. (2017) · Acta Astronautica · doi:10.1016/j.actaastro.2017.04.027 · Cited by 85 · cited 1×
“5] 1 c2 large penalty multiplier [1, 25] 10 ρ1 penalty for VTW violation [10, 50] 15 ρ2 penalty for memory violation [10, 50] 25”
Background
Cited by
Zhang, J., & Xing, L. (2021) · Computers & Operations Research · doi:10.1016/j.cor.2021.105626 · Cited by 125
Wen, Z., Li, L., Song, J., Zhang, S., & Hu, H. (2023) · Advances in Space Research · doi:10.1016/j.asr.2022.10.024 · Cited by 46
Lu, Z., Shen, X., Li, D., & Chen, Y. (2022) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2022.3176951 · Cited by 29
Self-citationLee, M., Yu, S., Kwon, K., Lee, M., Lee, J., & Kim, H. (2024) · Aerospace · doi:10.3390/aerospace11010083 · Cited by 31
Efficient and fair PPO-based integrated scheduling method for multiple tasks of SATech-01 satellite
Qi, S. H. I., Li, L., Fang, Z., Bi, X., Huaqiu, L. I. U., Zhang, X., Chen, W., & Yu, J. (2023) · Chinese Journal of Aeronautics · doi:10.1016/j.cja.2023.10.011 · Cited by 24
Metadata
- Authors
- Chen, Y., Lu, J., He, R., & Ou, J.
- Affiliations
- National University of Defense Technology (CN)
- Corresponding author
- Chen, Yuning
- Venue
- Applied Sciences
- Publisher
- MDPI AG
- Published
- 2020-08-13
- Volume
- 10
- Issue
- 16
- Pages
- 5616
- ISSN
- 2076-3417 (ISSN-L)
- OpenAlex
- W3049549869
- Cited by
- 24
- References
- 30
- Citations by year
- 2026: 4 · 2025: 7 · 2024: 5 · 2023: 3 · 2022: 2 · 2021: 2 · 2020: 1
- FWCI
- 1.20
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- Locations
- Applied Sciences (publishedVersion, cc-by)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- Funders
- the National Natural Science Foundation of China (71701203)
- National Natural Science Foundation of Hunan Province (2018JJ3618)
- Topics
- Physical Sciences › Engineering › Aerospace Engineering › Satellite Communication Systems
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Scheduling and Optimization Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Constraint Satisfaction and Optimization
- Keywords
- Earth observation satellites, satellite scheduling, integrated scheduling, local search, integer linear programming, satellite data download, ground station, constraint handling, NP-hard scheduling
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.