More Web Proxy on the site http://driver.im/

research-article

Solving dynamic satellite image data downlink scheduling problem via an adaptive bi-objective optimization algorithm

Authors:

Zhongxiang Chang,

Abraham P. Punnen,

Shi ChengAuthors Info & Claims

Volume 160, Issue C

https://doi.org/10.1016/j.cor.2023.106388

Published: 01 December 2023 Publication History

Abstract

The satellite image data downlink scheduling problem (SIDSP) plays a critical role in the mission planning operation of earth observation satellites. However, with recent developments in satellite technology, the traditional SIDSP is poorly effective for modern satellites. To offer additional modeling flexibility and renewed capabilities, a dynamic SIDSP (DSIDSP), which combines two interlinked operations of image data segmentation and image data downlink dynamically, was introduced. We have formulated the DSIDSP as a bi-objective problem of optimizing the image data transmission rate and the service-balance degree. Harnessing the power of an adaptive large neighborhood search (ALNS) algorithm with a nondominated sorting genetic algorithm II (NSGA-II), an adaptive bi-objective memetic algorithm, NSGA2ALNS, is developed to solve DSIDSP. Results of extensive computational experiments carried out using benchmark instances are also presented. Our experimental results reveal that the NSGA2ALNS algorithm is an effective and efficient method of solving DSIDSP based on various performance metrics. In addition, new benchmark instances are also provided for DSIDSP that could be used in future research.

Highlights

•

Model: To transmit an increased quantity of image data and balance the service rate of all earth observation satellites (EOSs) involved, exploiting the modern segment & rearrange capabilities, the DSIDSP was modeled and explored as a novel scheduling problem with two dynamic phases.

•

Algorithm: A memetic algorithm, which combined the nondominated sorting genetic algorithm II (NSGA-II) and the adaptive large neighborhood search (ALNS) algorithm, was proposed to solve the DSIDSP problem.

•

Benchmark: We designed enriched simulation experiments to test our models, algorithms, and operators.

References

[1]

An P., Wang X., Zhang Z., Gao F., Distribution of overseas satellites ground stations and their operational characteristics, Remote Sens. Technol. Appl. 23 (6) (2008) 697–704,.

[2]

Barbulescu L., Watson J.-P., Whitley L.D., Howe A.E., Scheduling space–ground communications for the air force satellite control network, J. Sched. 7 (2004) 7–34,.

Digital Library

[3]

Bradstreet L., While L., Barone L., A fast incremental hypervolume algorithm, IEEE Trans. Evol. Comput. 12 (6) (2008) 714–723,.

Digital Library

[4]

Chang, Z., Chen, Y., Yang, W., Zhou, Z., 2019. Analysis of Mission Planning Problem for Video Satellite Imaging with Variable Imaging Duration. In: 2019 IEEE Symposium Series on Computational Intelligence. SSCI, pp. 1700–1707. https://doi.org/10.1109/SSCI44817.2019.9003151.

[5]

Chang Z., Chen Y., Yang W., Zhou Z., Mission planning problem for optical video satellite imaging with variable image duration: A greedy algorithm based on heuristic knowledge, Adv. Space Res. 66 (11) (2020) 2597–2609,.

[6]

Chang Z., Zhou Z., Li R., Xiao H., Xing L., Observation scheduling for a state-of-the-art SAREOS: Two adaptive multi-objective evolutionary algorithms, Comput. Ind. Eng. 169 (2022),.

Digital Library

[7]

Chang Z., Zhou Z., Xing L., Yao F., Integrated scheduling problem for earth observation satellites based on three modeling frameworks: an adaptive bi-objective memetic algorithm, Mem. Comput. 13 (2) (2021) 203–226,.

[8]

Chang Z., Zhou Z., Yao F., Liu X., Observation scheduling problem for AEOS with a comprehensive task clustering, J. Syst. Eng. Electron. 32 (2) (2021) 347–364,.

[9]

Chen X., Li X., Wang X., Luo Q., Wu G., Task scheduling method for data relay satellite network considering breakpoint transmission, IEEE Trans. Veh. Technol. 70 (1) (2021) 844–857,.

[10]

Deb K., Agrawal S., Pratap A., Meyarivan T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput. 6 (2) (2002) 182–197,.

Digital Library

[11]

Du Y., Xing L., Zhang J., Chen Y., He Y., MOEA based memetic algorithms for multi-objective satellite range scheduling problem, Swarm Evol. Comput. 50 (2019),.

[12]

Guo H., Liu J., Li A., Zhang J., Earth observation satellite data receiving, processing system and data sharing, Int. J. Digit. Earth 5 (3) (2012) 241–250,.

[13]

Hamacher H.W., Pedersen C.R., Ruzika S., Finding representative systems for discrete bicriterion optimization problems, Oper. Res. Lett. 35 (3) (2007) 336–344,.

Digital Library

[14]

He L., de Weerdt M., Yorke-Smith N., Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm, J. Intell. Manuf. 31 (2020) 1051–1078,.

[15]

He L., Liu X., Laporte G., Chen Y., Chen Y., An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling, Comput. Oper. Res. 100 (2018) 12–25,.

[16]

He Y., Xing L., Chen Y., Pedrycz W., Wang L., Wu G., A generic Markov decision process model and reinforcement learning method for scheduling agile earth observation satellites, IEEE Trans. Syst. Man Cybern.: Syst. 52 (3) (2022) 1463–1474,.

[17]

Huang W., Sun s., Jiang H., Gao C., Zong X., GF-2 satellite 1 m/4 m camera design and in-orbit commissioning, Chin. J. Electron. 27 (2018) 1316–1321,.

[18]

Jakhu R.S., Pelton J.N., The development of small satellite systems and technologies, in: Small Satellites and their Regulation, Springer, New York, 2014, pp. 13–20,.

[19]

Jawak S.D., Luis A.J., Improved land cover mapping using high resolution multiangle 8-band WorldView-2 satellite remote sensing data, J. Appl. Remote Sens. 7 (1) (2013) 1–22,.

[20]

Kadziński M., Tervonen T., Tomczyk M.K., Dekker R., Evaluation of multi-objective optimization approaches for solving green supply chain design problems, Omega 68 (2017) 168–184,.

[21]

Karapetyan D., Mitrovic Minic S., Malladi K.T., Punnen A.P., Satellite downlink scheduling problem: A case study, Omega 53 (2015) 115–123,.

[22]

Kidd M.P., Lusby R., Larsen J., Equidistant representations: Connecting coverage and uniformity in discrete biobjective optimization, Comput. Oper. Res. 117 (2020),.

[23]

Li J., Li J., Chen H., Jing N., A data transmission scheduling algorithm for rapid-response earth-observing operations, Chin. J. Aeronaut. 27 (2) (2014) 349–364,.

[24]

Li J., Wu G., Liao T., Fan M., Mao X., Pedrycz W., Task scheduling under a novel framework for data relay satellite network via deep reinforcement learning, IEEE Trans. Veh. Technol. (2022) 1–15,.

[25]

Liu X., Laporte G., Chen Y., He R., An adaptive large neighborhood search metaheuristic for agile satellite scheduling with time-dependent transition time, Comput. Oper. Res. 86 (2017) 41–53,.

[26]

Lu, S., Chang, Z., Zhou, Z., Yao, F., 2021. An Adaptive Multi-objective Memetic Algorithm: a Case of Observation Scheduling for Active-imaging AEOS. In: 2021 7th International Conference on Big Data and Information Analytics (BigDIA). pp. 285–294. https://doi.org/10.1109/BigDIA53151.2021.9619648.

[27]

Luo K., Wang H., Li Y., Li Q., High-performance technique for satellite range scheduling, Comput. Oper. Res. 85 (2017) 12–21,.

Digital Library

[28]

Malladi K.T., Minic S.M., Karapetyan D., Punnen A.P., Satellite constellation image acquisition problem: A case study, in: Fasano G., Pintér J.D. (Eds.), Space Engineering: Modeling and Optimization with Case Studies, Springer International Publishing, Cham, 2016, pp. 177–197,.

[29]

Marinelli F., Nocella S., Rossi F., Smriglio S., A Lagrangian heuristic for satellite range scheduling with resource constraints, Comput. Oper. Res. 38 (11) (2011) 1572–1583,.

Digital Library

[30]

Neri F., Cotta C., Memetic algorithms and memetic computing optimization: A literature review, Swarm Evol. Comput. 2 (2012) 1–14,.

[31]

Pisinger D., Ropke S., A general heuristic for vehicle routing problems, Comput. Oper. Res. 34 (8) (2007) 2403–2435,.

Digital Library

[32]

She Y., Li S., Li Y., Zhang L., Wang S., Slew path planning of agile-satellite antenna pointing mechanism with optimal real-time data transmission performance, Aerosp. Sci. Technol. 90 (2019) 103–114,.

[33]

Vazquez A.J., Erwin R.S., On the tractability of satellite range scheduling, Optim. Lett. 9 (2015) 311–327,.

[34]

Wang S., Jin R., Zhu J., SuperView-1- China’s first commercial remote sensing satellite constellation with a high resolution of 0.5 m, Aerosp. China 19 (1) (2018) 31–38,.

[35]

Wang R., Purshouse R.C., Fleming P.J., Preference-inspired coevolutionary algorithms for many-objective optimization, IEEE Trans. Evol. Comput. 17 (4) (2013) 474–494,.

Digital Library

[36]

Wang P., Reinelt G., A heuristic for an earth observing satellite constellation scheduling problem with download considerations, Electron. Notes Discrete Math. 36 (2010) 711–718,.

[37]

Wang P., Reinelt G., Gao P., Tan Y., A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation, Comput. Ind. Eng. 61 (2) (2011) 322–335,.

Digital Library

[38]

Wang X., Wu G., Xing L., Pedrycz W., Agile earth observation satellite scheduling over 20 years: Formulations, methods, and future directions, IEEE Syst. J. 15 (3) (2021) 3881–3892,.

[39]

Wu X., Che A., A memetic differential evolution algorithm for energy-efficient parallel machine scheduling, Omega 82 (2019) 155–165,.

[40]

Wu X., Che A., Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search, Omega 94 (2020),.

[41]

Wu G., Luo Q., Du X., Chen Y., Suganthan P.N., Wang X., Ensemble of metaheuristic and exact algorithm based on the divide-and-conquer framework for multisatellite observation scheduling, IEEE Trans. Aerosp. Electron. Syst. 58 (5) (2022) 4396–4408,.

[42]

Wu G., Luo Q., Zhu Y., Chen X., Feng Y., Pedrycz W., Flexible task scheduling in data relay satellite networks, IEEE Trans. Aerosp. Electron. Syst. 58 (2) (2022) 1055–1068,.

[43]

Xiao Y., Zhang S., Yang P., You M., Huang J., A two-stage flow-shop scheme for the multi-satellite observation and data-downlink scheduling problem considering weather uncertainties, Reliab. Eng. Syst. Saf. 188 (2019) 263–275,.

[44]

Zhang J., Xing L., Peng G., Yao F., Chen C., A large-scale multiobjective satellite data transmission scheduling algorithm based on SVM+NSGA-II, Swarm Evol. Comput. 50 (2019),.

[45]

Zhou Z., Chen E., Wu F., Chang Z., Xing L., Multi-satellite scheduling problem with marginal decreasing imaging duration: An improved adaptive ant colony algorithm, Comput. Ind. Eng. 176 (2023),.

Digital Library

[46]

Zufferey N., Amstutz P., Giaccari P., Graph colouring approaches for a satellite range scheduling problem, J. Sched. 11 (2008) 263–277,.

Digital Library

Cited By

Lin XChen YXue JZhang BHe LChen Y(2024)Large-volume LEO satellite imaging data networked transmission scheduling problemExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123649249:PBOnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123649
Cheng SLu HLei X(2024)Automated Planning and Scheduling with Swarm IntelligenceAdvances in Swarm Intelligence10.1007/978-981-97-7184-4_3(26-35)Online publication date: 22-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-7184-4_3

Recommendations

Solving satellite image data downlink scheduling problem with family attribute via a bi-stage differential evolutionary algorithm
Abstract
Due to the asynchronous development of observation and transition capabilities, the original image data (OID) obtained by a one-time observation cannot be completely transmitted in one transmission cycle between the EOS and GS, which is named a ...
Highlights
- Model: A novel satellite image data downlink scheduling model is formatted considering two phases.
- Algorithm: A bi-stage differential evolutionary algorithm (DE-CD) is developed.
- Benchmark: The enriched simulation experiments is ...
The bi-objective quadratic multiple knapsack problem

The single objective quadratic multiple knapsack problem (QMKP) is a useful model to formulate a number of practical problems. However, it is not suitable for situations where more than one objective needs to be considered. In this paper, we extend the ...
A set-based genetic algorithm for solving the many-objective optimization problem

Many-objective optimization problems are very common and important in real-world applications, and there exist few methods suitable for them. Therefore, many-objective optimization problems are focused on in this study, and a set-based genetic algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Operations Research

Computers and Operations Research Volume 160, Issue C

Dec 2023

500 pages

ISSN:0305-0548

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 December 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lin XChen YXue JZhang BHe LChen Y(2024)Large-volume LEO satellite imaging data networked transmission scheduling problemExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123649249:PBOnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123649
Cheng SLu HLei X(2024)Automated Planning and Scheduling with Swarm IntelligenceAdvances in Swarm Intelligence10.1007/978-981-97-7184-4_3(26-35)Online publication date: 22-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-7184-4_3

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents