AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

College of Systems Engineering, National University of Defense Technology, Changsha 410000, China
Beijing Institude of Tranking and Telecommunication Technology, Beijing 100000, China
Show Author Information

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 schedulingtabu search heuristicdata transmission and downloadmixed integer programming model

References

[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
Tsinghua Science and Technology
Volume 29 Issue 3,
June 2024
Pages 843-862
DOI: 10.26599/TST.2023.9010064
Cite this article:
Yang W, He L, Liu X, et al. A Fast Insertion Tabu Search with Conflict-Avoidance Heuristic for the Multisatellite Multimode Crosslink Scheduling Problem. Tsinghua Science and Technology, 2024, 29(3): 843-862. https://doi.org/10.26599/TST.2023.9010064

381

Views

35

Downloads

2

Crossref

0

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 06 March 2023
Revised: 11 June 2023
Accepted: 13 June 2023
Published: 04 December 2023
© The Author(s) 2024.

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