Journal Home > Volume 29 , Issue 3

An agile earth-observing satellite equipped with multimode cameras capable of transmitting observation data to other satellites is developed to rapidly respond to requests with multiple observation modes. This gives rise to the Multisatellite Multimode Crosslink Scheduling (MMCS) problem, which involves allocating observation requests to agile satellites, selecting appropriate timing and observation modes for the requests, and transmitting the data to the ground station via the satellite communication system. Herein, a mixed integer programming model is introduced to include all complex time and operation constraints. To solve the MMCS problem, a two-stage heuristic method, called Fast insertion Tabu Search with Conflict-avoidance (FTS-C) heuristic, is developed. In the first stage, a conflict-avoidance insertion algorithm is designed to generate a high-quality initial solution by considering the requests transmission and download. Further, the tabu search-based second stage optimizes the initial solution. Finally, an extensive empirical study based on a real-world situation demonstrates that FTS-C can generate a solution with higher quality in less time than other state-of-the-art algorithms and the CPLEX solver.


menu
Abstract
Full text
Outline
About this article

A Fast Insertion Tabu Search with Conflict-Avoidance Heuristic for the Multisatellite Multimode Crosslink Scheduling Problem

Show Author's information Weiyi Yang1Lei He1Xiaolu Liu1( )Weican Meng2Yingwu Chen1
College of Systems Engineering, National University of Defense Technology, Changsha 410000, China
Beijing Institude of Tranking and Telecommunication Technology, Beijing 100000, China

Abstract

An agile earth-observing satellite equipped with multimode cameras capable of transmitting observation data to other satellites is developed to rapidly respond to requests with multiple observation modes. This gives rise to the Multisatellite Multimode Crosslink Scheduling (MMCS) problem, which involves allocating observation requests to agile satellites, selecting appropriate timing and observation modes for the requests, and transmitting the data to the ground station via the satellite communication system. Herein, a mixed integer programming model is introduced to include all complex time and operation constraints. To solve the MMCS problem, a two-stage heuristic method, called Fast insertion Tabu Search with Conflict-avoidance (FTS-C) heuristic, is developed. In the first stage, a conflict-avoidance insertion algorithm is designed to generate a high-quality initial solution by considering the requests transmission and download. Further, the tabu search-based second stage optimizes the initial solution. Finally, an extensive empirical study based on a real-world situation demonstrates that FTS-C can generate a solution with higher quality in less time than other state-of-the-art algorithms and the CPLEX solver.

Keywords: earth observation satellites scheduling, tabu search heuristic, data transmission and download, mixed integer programming model

References(43)

[1]

J. Wang, E. Demeulemeester, and D. Qiu, A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds, Comput. Oper. Res., vol. 74, pp. 1–13, 2016.

[2]

F. Yao, J. Li, Y. Chen, X. Chu, and B. Zhao, Task allocation strategies for cooperative task planning of multi-autonomous satellite constellation, Adv. Space Res., vol. 63, no. 2, pp. 1073–1084, 2019.

[3]
H. Chen, Z. Zhong, J. Wu, and N. Jing, Multi-satellite data downlink resource scheduling algorithm for incremental observation tasks based on evolutionary computation, in Proc. 2015 Seventh Int. Conf. on Advanced Computational Intelligence, Wuyi, China, 2015, pp. 251–256.
DOI
[4]

J. Wu, J. Xiong, H. Dai, Y. Wang, and C. Xu, MIX-RS: A multi-indexing system based on HDFS for remote sensing datastorage, Tsinghua Science and Technology, vol. 27, no. 6, pp. 881–893, 2022.

[5]

R. Xu, H. Chen, X. Liang, and H. Wang, Priority-based constructive algorithms for scheduling agile earth observation satellites with total priority maximization, Expert Syst. Appl., vol. 51, pp. 195–206, 2016.

[6]

L. Barbulescu, J. P. Watson, L. D. Whitley, and A. E. Howe, Scheduling space-ground communications for the air force satellite control network, J. Schedul., vol. 7, no. 1, pp. 7–34, 2004.

[7]

J. Wang, E. Demeulemeester, X. Hu, D. Qiu, and J. Liu, Exact and heuristic scheduling algorithms for multiple earth observation satellites under uncertainties of clouds, IEEE Syst. J., vol. 13, no. 3, pp. 3556–3567, 2019.

[8]

M. Vasquez and J. K. Hao, Upper bounds for the spot 5 daily photograph scheduling problem, J. Comb. Optim., vol. 7, no. 1, pp. 87–103, 2003.

[9]

X. Chen, G. Reinelt, G. Dai, and A. Spitz, A mixed integer linear programming model for multi-satellite scheduling, Eur. J. Oper. Res., vol. 275, no. 2, pp. 694–707, 2019.

[10]

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

[11]

G. Peng, R. Dewil, C. Verbeeck, A. Gunawan, L. Xing, and P. Vansteenwegen, Agile earth observation satellite scheduling: An orienteering problem with time-dependent profits and travel times, Comput. Oper. Res., vol. 111, pp. 84–98, 2019.

[12]

X. Niu, H. Tang, L. Wu, R. Deng, and X. Zhai, Imaging-duration embedded dynamic scheduling of earth observation satellites for emergent events, Math. Probl. Eng., vol. 2015, pp. 731–734, 2015.

[13]

J. Berger, N. Lo, and M. Barkaoui, QUEST–a new quadratic decision model for the multi-satellite scheduling problem, Comput. Oper. Res., vol. 115, p. 104822, 2020.

[14]

Z. E, R. Shi, L. Gan, H. Baoyin, and J. Li, Multi-satellites imaging scheduling using individual reconfiguration based integer coding genetic algorithm, Acta Astronaut., vol. 178, pp. 645–657, 2021.

[15]

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

[16]

A. Sarkheyli, A. Bagheri, B. Ghorbani-Vaghei, and R. Askari-Moghadam, Using an effective tabu search in interactive resources scheduling problem for LEO satellites missions, Aerosp. Sci. Technol., vol. 29, no. 1, pp. 287–295, 2013.

[17]

X. Wang, H. Zhang, S. Bai, and Y. Yue, Design of agile satellite constellation based on hybrid-resampling particle swarm optimization method, Acta Astronaut., vol. 178, pp. 595–605, 2021.

[18]

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

[19]

C. Li and B. Xu, Optimal scheduling of multiple sun-synchronous orbit satellites refueling, Adv. Space Res., vol. 66, no. 2, pp. 345–358, 2020.

[20]

D. Madakat, J. Morio, and D. Vanderpooten, A biobjective branch and bound procedure for planning spatial missions, Aerosp. Sci. Technol., vol. 73, pp. 269–277, 2018.

[21]

E. Pellegrini and R. P. Russell, A multiple-shooting differential dynamic programming algorithm, Part 2: Applications, Acta Astronaut., vol. 173, pp. 460–472, 2020.

[22]

J. Wang, G. Song, Z. Liang, E. Demeulemeester, X. Hu, and J. Liu, Unrelated parallel machine scheduling with multiple time windows: An application to earth observation satellite scheduling, Comput. Oper. Res., vol. 149, p. 106010, 2023.

[23]

H. Chen, Z. Lou, S. Peng, J. Wu, and J. Li, HiPGen: An approach for fast generation of multi-satellite observation plans via a hierarchical multi-channel transformer network, Adv. Space Res., vol. 69, no. 8, pp. 3103–3116, 2022.

[24]

G. Wu, J. Liu, M. Ma, and D. Qiu, A two-phase scheduling method with the consideration of task clustering for earth observing satellites, Comput. Oper. Res., vol. 40, no. 7, pp. 1884–1894, 2013.

[25]

J. Wang, X. Zhu, L. T. Yang, J. Zhu, and M. Ma, Towards dynamic real-time scheduling for multiple earth observation satellites, J. Comput. Syst. Sci., vol. 81, no. 1, pp. 110–124, 2015.

[26]

X. Hu, W. Zhu, B. An, P. Jin, and W. Xia, A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem, Comput. Oper. Res., vol. 104, pp. 74–89, 2019.

[27]

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

[28]

J. Zhang and L. Xing, An improved genetic algorithm for the integrated satellite imaging and data transmission scheduling problem, Comput. Oper. Res., vol. 139, p. 105626, 2022.

[29]

H. Chen, J. Wu, W. Shi, J. Li, and Z. Zhong, Coordinate scheduling approach for EDS observation tasks and data transmission jobs, J. Syst. Eng. Electron., vol. 27, no. 4, pp. 822–835, 2016.

[30]

W. Zhu, X. Hu, W. Xia, and P. Jin, A two-phase genetic annealing method for integrated earth observation satellite scheduling problems, Soft Comput., vol. 23, no. 1, pp. 181–196, 2019.

[31]
A. K. Kennedy, Planning and scheduling for earth-observing small satellite constellations, PhD dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 2018.
[32]

T. Benoist and B. Rottembourg, Upper bounds for revenue maximization in a satellite scheduling problem, Q. J. Belg., French Italian Oper. Res. Soc., vol. 2, no. 3, pp. 235–249, 2004.

[33]

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

[34]

H. Zhou, H. Qin, Z. Zhang, and J. Li, Two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery, Soft Comput., vol. 26, no. 7, pp. 3345–3360, 2022.

[35]
M. J. Pinto, A. I. Barros, R. Noomen, P. H. A. J. M. van Gelder, and T. L. Tessensohn, A new model proposal for integrated satellite constellation scheduling within a planning horizon given operational constraints, in Proc. 7 th Int. Conf. on Operations Research and Enterprise Systems, Funchal, Portugal, 2018, pp. 312–319.
DOI
[36]

C. Verbeeck, P. Vansteenwegen, and E. H. Aghezzaf, The time-dependent orienteering problem with time windows: A fast ant colony system, Ann. Oper. Res., vol. 254, no. 1, pp. 481–505, 2017.

[37]
F. Glover, Tabu Search. Boulder, CO, USA: University of Colorado, 1988.
[38]

C. Yan, J. Ma, H. Luo, and J. Wang, A hybrid algorithm based on binary chemical reaction optimization and tabu search for feature selection of high-dimensional biomedical data, Tsinghua Science and Technology, vol. 23, no. 6, pp. 733–743, 2018.

[39]

G. Li, L. Xing, and Y. Chen, A hybrid online scheduling mechanism with revision and progressive techniques for autonomous earth observation satellite, Acta Astronaut., vol. 140, pp. 308–321, 2017.

[40]

X. Chen, G. Reinelt, G. Dai, and M. Wang, Priority-based and conflict-avoidance heuristics for multi-satellite scheduling, Appl. Soft Comput., vol. 69, pp. 177–191, 2018.

[41]

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

[42]

L. He, A. Guijt, M. de Weerdt, L. Xing, and N. Yorke-Smith, Order acceptance and scheduling with sequence-dependent setup times: A new memetic algorithm and benchmark of the state of the art, Comput. Ind. Eng., vol. 138, p. 106102, 2019.

[43]
A. Sarkheyli, B. G. Vaghei, and A. Bagheri, New tabu search heuristic in scheduling earth observation satellites, in Proc. 2 nd Int. Conf. on Software Technology and Engineering, San Juan, PR, USA, 2010, pp. V2-199−V2-203.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 06 March 2023
Revised: 11 June 2023
Accepted: 13 June 2023
Published: 04 December 2023
Issue date: June 2024

Copyright

© The Author(s) 2024.

Acknowledgements

Acknowledgment

This research was supported by the National Natural Science Foundation of China (No. 72001212) and the Hunan Provincial Innovation Foundation for Postgraduate (No. CX20200022).

Rights and permissions

The articles published in this open access journal are distributed under the terms of theCreative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return