The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
An Exact Algorithm for Agile Earth Observation Satellite Scheduling with Time-Dependent Profits
Open accessAbstract
Abstract The scheduling of an Agile Earth Observation Satellite (AEOS) consists of selecting and scheduling a subset of possible targets for observation in order to maximize the collected profit related to the images while satisfying its operational constraints. In this problem, a set of candidate targets for observation is given, each with a time-dependent profit and a visible time window. The exact profit of a target depends on the start time of its observation, reaching its maximum at the midpoint of its visible time window. This time dependency stems from the fact that the image quality is determined by the look angle between the satellite and the target to be observed. We present an exact algorithm for the single-orbit scheduling for an AEOS considering the time-dependent profits. The algorithm is called Adaptive-directional Dynamic Programming with Decremental State Space Relaxation (ADP-DSSR). This algorithm is based on the dynamic programming approach for the Orienteering Problem with Time Windows (OPTW). Several algorithmic improvements are proposed to address the time-dependent profits. The proposed algorithm is evaluated based on extensive computational tests. The experimental results show that the algorithmic improvements significantly reduce the required computational time. The comparison between the proposed exact algorithm and a state-of-the-art heuristic illustrates that our algorithm can find the optimal solutions for sufficiently large instances within limited computational time. The results also show that our algorithm is capable of efficiently solving benchmark OPTW instances.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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?
Exact methods for AEOS scheduling provide strong optimality guarantees but are computationally limited to small problem instances.
“exact methods provide strong optimality guarantees but are computationally limited to small problem instances.”
From Scheduling multiple agile Earth observation satellites with multiple observations (2026) · cites this paper as Peng et al., 2020
The paper supports the optimality part: Section 5 says its exact algorithm solves AEOS scheduling to optimality. But Section 5.2 says the algorithm solves large-scale single-orbit instances in under 10 seconds and is almost as fast as a heuristic for most tested instances, contrary to the claim that it is computationally limited to small instances. (LLM, conf=0.88)
Checked by a reasoning model — may be wrong.
Experimental — accuracy not yet measured
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
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
Solomon, M. M. (1987) · Operations Research · doi:10.1287/opre.35.2.254 · Cited by 4,321
A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
Desrochers, M., Desrosiers, J., & Solomon, M. (1992) · Operations Research · doi:10.1287/opre.40.2.342 · Cited by 1,223
2008 IEEE International Conference on Robotics and Automation
(2008) · IEEE Transactions on Robotics · doi:10.1109/tro.2008.921895 · Cited by 919
A tabu search heuristic for periodic and multi-depot vehicle routing problems
Cordeau, J.-F., Gendreau, M., & Laporte, G. (1997) · Networks · doi:10.1002/(sici)1097-0037(199709)30:2 · Cited by 845
Feillet, D., Dejax, P. J., Gendreau, M., et al. (2004) · Networks · doi:10.1002/net.20033 · Cited by 692
Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows
Desaulniers, G., Errico, F., Irnich, S., & Schneider, M. (2016) · Operations Research · doi:10.1287/opre.2016.1535 · Cited by 504
Selecting and scheduling observations of agile satellites
Lemaı̂tre, M., Verfaillie, G., Jouhaud, F., Lachiver, J.-M., & Bataille, N. (2002) · Aerospace Science and Technology · doi:10.1016/s1270-9638(02)01173-2 · Cited by 472
Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
Dror, M. (1994) · Operations Research · doi:10.1287/opre.42.5.977 · Cited by 327
Three 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 318
New dynamic programming algorithms for the resource constrained elementary shortest path problem
Righini, G., & Salani, M. (2007) · Networks · doi:10.1002/net.20212 · Cited by 284
Bianchessi, N., Cordeau, J., Desrosiers, J., Gilbert Laporte, A., & Raymond, V. (2006) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.12.026 · Cited by 255
Liu, X., Laporte, G., Chen, Y., & He, R. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.04.006 · Cited by 250
An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling
He, L., Liu, X., Gilbert Laporte, A., Chen, Y., & Chen, Y. (2018) · Computers & Operations Research · doi:10.1016/j.cor.2018.06.020 · Cited by 210
Accelerated label setting algorithms for the elementary resource constrained shortest path problem
Boland, N., Dethridge, J., & Dumitrescu, I. (2005) · Operations Research Letters · doi:10.1016/j.orl.2004.11.011 · Cited by 201
Wang, P., Reinelt, G., Gao, P., & Tan, Y. (2011) · Computers & Industrial Engineering · doi:10.1016/j.cie.2011.02.015 · Cited by 198
Daily imaging scheduling of an earth observation satellite
Lin, W.-C., Liao, D.-Y., Liu, C.-Y., & Lee, Y.-Y. (2005) · IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans · doi:10.1109/tsmca.2005.843380 · Cited by 173
A mixed integer linear programming model for multi-satellite scheduling
Chen, X., Reinelt, G., Dai, G., & Spitz, A. (2018) · European Journal of Operational Research · doi:10.1016/j.ejor.2018.11.058 · Cited by 167
Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows
Dabia, S., Røpke, S., Woensel, T. V., et al. (2012) · Transportation Science · doi:10.1287/trsc.1120.0445 · Cited by 165
Righini, G., & Salani, M. (2008) · Computers & Operations Research · doi:10.1016/j.cor.2008.01.003 · Cited by 159
Xu, R., Chen, H., Liang, X., & Wang, H. (2016) · Expert Systems with Applications · doi:10.1016/j.eswa.2015.12.039 · Cited by 156
Maximizing the value of an Earth observation satellite orbit
Cordeau, J.-F., & Laporte, G. (2005) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601926 · Cited by 150
Habet, D., Vasquez, M., & Vimont, Y. (2008) · Computational Optimization and Applications · doi:10.1007/s10589-008-9220-7 · Cited by 117
Peng, G., Dewil, R., Verbeeck, C., Gunawan, A., Xing, L., & Vansteenwegen, P. (2019) · Computers & Operations Research · doi:10.1016/j.cor.2019.05.030 · Cited by 113
Self-citationGabrel, V., Moulet, A., Murat, C., & Paschos, V. T. (1997) · Annals of Operations Research · doi:10.1023/a:1018920709696 · Cited by 96
Tilk, C., Rothenbächer, A.-K., Gschwind, T., et al. (2017) · European Journal of Operational Research · doi:10.1016/j.ejor.2017.03.017 · Cited by 79
A column generation algorithm for the vehicle routing problem with soft time windows
Liberatore, F., Righini, G., & Salani, M. (2010) · 4OR · doi:10.1007/s10288-010-0136-6 · Cited by 75
Multi satellites scheduling algorithm based on task merging mechanism
Xiaolu, L., Bai, B., Yingwu, C., & Yao, F. (2014) · Applied Mathematics and Computation · doi:10.1016/j.amc.2013.12.109 · Cited by 61
Third International Conference on Natural Computation (ICNC 2007)
(2007) · doi:10.1109/icnc12646.2007 · Cited by 60
Wang, J., Demeulemeester, E. L., Hu, X., Qiu, D., & Jin, L. (2018) · IEEE Systems Journal · doi:10.1109/jsyst.2018.2874223 · Cited by 57
Scheduling Observations of Agile Satellites with Combined Genetic Algorithm
Li, Y., Xu, M., & Wang, R. (2007) · International Conference on Natural Computation (ICNC) · doi:10.1109/icnc.2007.652 · Cited by 48
(2005) · Cited by 38
Vehicle Routing with Time Windows and Time-Dependent Rewards: A Problem from the American Red Cross
Yi, J. (2003) · Manufacturing & Service Operations Management · doi:10.1287/msom.5.1.74.12758 · Cited by 32
Single-machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm
Chand, S., Traub, R. D., & Uzsoy, R. (1996) · Naval Research Logistics (NRL) · doi:10.1002/(sici)1520-6750(199608)43:5 · Cited by 29
Solving the Orienteering Problem with Time Windows via the Pulse Framework
Duque, D., Lozano, L., & Medaglia, A. L. (2014) · Computers & Operations Research · doi:10.1016/j.cor.2014.08.019 · Cited by 28
(2003) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2003.1245623 · Cited by 21
Multi-robot routing with linear decreasing rewards over time
Ekic, A., Keskinocak, P., & Koenig, S. (2009) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2009.5152803 · Cited by 17
Flagged first, then by citations
Cited by
Sorted by citations
Scheduling multiple agile Earth observation satellites with multiple observations
Wang, X., Han, C., & Leus, R. (2026) · Advances in Space Research · doi:10.1016/j.asr.2025.10.042 · Cited by 24
An Innovative Priority-Aware Mission Planning Framework for an Agile Earth Observation Satellite
Zhu, G., Zheng, Z., Ouyang, C., Guo, Y., & Sun, P. (2025) · Aerospace · doi:10.3390/aerospace12040309 · Cited by 4
Metadata
- Authors
- Peng, G., Song, G., Xing, L., Gunawan, A., & Vansteenwegen, P.
- Affiliations
- National University of Defense Technology (CN)
- Singapore Management University (SG)
- KU Leuven (BE)
- Corresponding author
- Xing, Lining
- Venue
- Computers & Operations Research
- Publisher
- Elsevier BV
- Published
- 2020-08
- Volume
- 120
- Pages
- 104946
- ISSN
- 0305-0548 (ISSN-L)
- OpenAlex
- W3014882452
- Semantic Scholar
- 51eacda6c3284cb9a35b0afe894bd96b630f7ff9
- Cited by
- 93
- References
- 36
- Citations by year
- 2026: 16 · 2025: 32 · 2024: 17 · 2023: 10 · 2022: 7 · 2021: 10 · 2020: 1
- FWCI
- 4.46
- Type
- journal article
- Language
- en
- Open access
- green
- lirias.kuleuven.be
- Licence
- Locations
- Computers & Operations Research (publishedVersion)
- Lirias (submittedVersion, other-oa)
- Singapore Management University Institutional Knowledge (InK) (Singapore Management University) (submittedVersion)
- Funders
- Foundation for the Author of National Excellent Doctoral Dissertation of the People's Republic of China (2014-92)
- National Natural Science Foundation of China (71801218, 61525304, 61873328, 61773120, 71501180, U1501254)
- China Scholarship Council (201703170228)
- Topics
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Vehicle Routing Optimization Methods
- Physical Sciences › Engineering › Aerospace Engineering › Satellite Communication Systems
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Scheduling and Optimization Algorithms
- Keywords
- agile Earth observation satellites, look angle, image quality, exact algorithms
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
