IDEAS home Printed from https://ideas.repec.org/a/eee/chsofr/v83y2016icp125-132.html
   My bibliography  Save this article

Scheduling for single agile satellite, redundant targets problem using complex networks theory

Author

Listed:
  • Wang, Xin-Wei
  • Chen, Zhen
  • Han, Chao

Abstract

Scheduling for the Earth observation satellites (EOSs) imaging mission is a complicated combinatorial optimization problem, especially for the agile EOSs (AEOSs). The increasing observation requirements and orbiting satellites have exacerbated the scheduling complexity in recent years. In this paper, the single agile satellite, redundant observation targets scheduling problem is studied. We introduce the theory of complex networks and find similarities between AEOS redundant targets scheduling problem and the node centrality ranking problem. Then we model this problem as a complex network, regarding each node as a possible observation opportunity, and define two factors, node importance factor and target importance factor, to describe the node/target importance. Based on the two factors, we propose a fast approximate scheduling algorithm (FASA) to obtain the effective scheduling results. Simulation results indicate the FASA is quite efficient and with broad suitability. Our work is helpful in the EOSs and AEOSs scheduling problems by using complex network knowledge.

Suggested Citation

  • Wang, Xin-Wei & Chen, Zhen & Han, Chao, 2016. "Scheduling for single agile satellite, redundant targets problem using complex networks theory," Chaos, Solitons & Fractals, Elsevier, vol. 83(C), pages 125-132.
    • Handle: RePEc:eee:chsofr:v:83:y:2016:i:c:p:125-132
    DOI: 10.1016/j.chaos.2015.12.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0960077915004129
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.chaos.2015.12.003?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dawei Zhao & Lianhai Wang & Shudong Li & Zhen Wang & Lin Wang & Bo Gao, 2014. "Immunization of Epidemics in Multiplex Networks," PLOS ONE, Public Library of Science, vol. 9(11), pages 1-5, November.
    2. Tangpattanakul, Panwadee & Jozefowiez, Nicolas & Lopez, Pierre, 2015. "A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite," European Journal of Operational Research, Elsevier, vol. 245(2), pages 542-554.
    3. Chen Liu & Wen-Bo Du & Wen-Xu Wang, 2014. "Particle Swarm Optimization with Scale-Free Interactions," PLOS ONE, Public Library of Science, vol. 9(5), pages 1-8, May.
    4. V. Kerry Smith & William H. Desvousges & Matthew P. McGivney, 1983. "The Opportunity Cost of Travel Time in Recreation Demand Models," Land Economics, University of Wisconsin Press, vol. 59(3), pages 259-278.
    5. Xia, Cheng-yi & Wang, Zhen & Sanz, Joaquin & Meloni, Sandro & Moreno, Yamir, 2013. "Effects of delayed recovery and nonuniform transmission on the spreading of diseases in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(7), pages 1577-1585.
    6. Du, Wen-Bo & Wu, Zhi-Xi & Cai, Kai-Quan, 2013. "Effective usage of shortest paths promotes transportation efficiency on scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(17), pages 3505-3512.
    7. Sergey V. Buldyrev & Roni Parshani & Gerald Paul & H. Eugene Stanley & Shlomo Havlin, 2010. "Catastrophic cascade of failures in interdependent networks," Nature, Nature, vol. 464(7291), pages 1025-1028, April.
    8. Iori, Giulia & De Masi, Giulia & Precup, Ovidiu Vasile & Gabbi, Giampaolo & Caldarelli, Guido, 2008. "A network analysis of the Italian overnight money market," Journal of Economic Dynamics and Control, Elsevier, vol. 32(1), pages 259-278, January.
    9. Djamal Habet & Michel Vasquez & Yannick Vimont, 2010. "Bounding the optimum for the problem of scheduling the photographs of an Agile Earth Observing Satellite," Computational Optimization and Applications, Springer, vol. 47(2), pages 307-333, October.
    10. Gabrel, Virginie & Vanderpooten, Daniel, 2002. "Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite," European Journal of Operational Research, Elsevier, vol. 139(3), pages 533-542, June.
    11. Alessandro Vespignani, 2010. "The fragility of interdependency," Nature, Nature, vol. 464(7291), pages 984-985, April.
    12. Hong, Chen, 2015. "Effective usage of global dynamic information for network traffic," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 424(C), pages 242-247.
    13. Virginie Gabrel & Alain Moulet & Cécile Murat & Vangelis Paschos, 1997. "A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts," Annals of Operations Research, Springer, vol. 69(0), pages 115-134, January.
    14. Bianchessi, Nicola & Cordeau, Jean-Francois & Desrosiers, Jacques & Laporte, Gilbert & Raymond, Vincent, 2007. "A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites," European Journal of Operational Research, Elsevier, vol. 177(2), pages 750-762, March.
    15. Du, Wen-Bo & Gao, Yang & Liu, Chen & Zheng, Zheng & Wang, Zhen, 2015. "Adequate is better: particle swarm optimization with limited-information," Applied Mathematics and Computation, Elsevier, vol. 268(C), pages 832-838.
    16. Zhen Chen & Jun Zhang & Wen-Bo Du & Oriol Lordan & Jiangjun Tang, 2015. "Optimal Allocation of Node Capacity in Cascade-Robustness Networks," PLOS ONE, Public Library of Science, vol. 10(10), pages 1-12, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jiawei Chen & Ming Chen & Jun Wen & Lei He & Xiaolu Liu, 2022. "A Heuristic Construction Neural Network Method for the Time-Dependent Agile Earth Observation Satellite Scheduling Problem," Mathematics, MDPI, vol. 10(19), pages 1-21, September.
    2. Aaron B. Hoskins & Hugh R. Medal & Eghbal Rashidi, 2017. "Satellite constellation design for forest fire monitoring via a stochastic programing approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 642-661, December.
    3. Ben-Loghfyry, Anouar & Charkaoui, Abderrahim, 2023. "Regularized Perona & Malik model involving Caputo time-fractional derivative with application to image denoising," Chaos, Solitons & Fractals, Elsevier, vol. 175(P1).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Xiao, Guanping & Zheng, Zheng & Wang, Haoqin, 2017. "Evolution of Linux operating system network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 466(C), pages 249-258.
    2. Zhang Ye & Hu Xiaoxuan & Zhu Waiming & Jin Peng, 2018. "Solving the Observing and Downloading Integrated Scheduling Problem of Earth Observation Satellite with a Quantum Genetic Algorithm," Journal of Systems Science and Information, De Gruyter, vol. 6(5), pages 399-420, October.
    3. Chen, Xiaoyu & Reinelt, Gerhard & Dai, Guangming & Spitz, Andreas, 2019. "A mixed integer linear programming model for multi-satellite scheduling," European Journal of Operational Research, Elsevier, vol. 275(2), pages 694-707.
    4. Zhang, Xue-Jun & Xu, Guo-Qiang & Zhu, Yan-Bo & Xia, Yong-Xiang, 2016. "Cascade-robustness optimization of coupling preference in interconnected networks," Chaos, Solitons & Fractals, Elsevier, vol. 92(C), pages 123-129.
    5. Jang, Jinbong & Choi, Jiwoong & Bae, Hee-Jin & Choi, In-Chan, 2013. "Image collection planning for KOrea Multi-Purpose SATellite-2," European Journal of Operational Research, Elsevier, vol. 230(1), pages 190-199.
    6. Wang, Haoqin & Chen, Zhen & Xiao, Guanping & Zheng, Zheng, 2016. "Network of networks in Linux operating system," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 447(C), pages 520-526.
    7. Xia, Yongxiang & Zhang, Wenping & Zhang, Xuejun, 2016. "The effect of capacity redundancy disparity on the robustness of interconnected networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 447(C), pages 561-568.
    8. Tangpattanakul, Panwadee & Jozefowiez, Nicolas & Lopez, Pierre, 2015. "A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite," European Journal of Operational Research, Elsevier, vol. 245(2), pages 542-554.
    9. Lordan, Oriol & Sallan, Jose M. & Escorihuela, Nuria & Gonzalez-Prieto, David, 2016. "Robustness of airline route networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 445(C), pages 18-26.
    10. Rigo, Cezar Antônio & Seman, Laio Oriel & Camponogara, Eduardo & Morsch Filho, Edemar & Bezerra, Eduardo Augusto & Munari, Pedro, 2022. "A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service," European Journal of Operational Research, Elsevier, vol. 303(1), pages 168-183.
    11. Alex Elkjær Vasegaard & Ilkyeong Moon & Peter Nielsen & Subrata Saha, 2023. "Determining the pricing strategy for different preference structures for the earth observation satellite scheduling problem through simulation and VIKOR," Flexible Services and Manufacturing Journal, Springer, vol. 35(3), pages 945-973, September.
    12. Shekhtman, Louis M. & Danziger, Michael M. & Havlin, Shlomo, 2016. "Recent advances on failure and recovery in networks of networks," Chaos, Solitons & Fractals, Elsevier, vol. 90(C), pages 28-36.
    13. Chen, Jie & Wu, Chao-Yun & Li, Ming & Hu, Mao-Bin, 2019. "Hybrid traffic dynamics on coupled networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 98-104.
    14. Tabak, Benjamin M. & Takami, Marcelo & Rocha, Jadson M.C. & Cajueiro, Daniel O. & Souza, Sergio R.S., 2014. "Directed clustering coefficient as a measure of systemic risk in complex banking networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 394(C), pages 211-216.
    15. L. Bargigli & G. di Iasio & L. Infante & F. Lillo & F. Pierobon, 2015. "The multiplex structure of interbank networks," Quantitative Finance, Taylor & Francis Journals, vol. 15(4), pages 673-691, April.
    16. Ji, Xingpei & Wang, Bo & Liu, Dichen & Dong, Zhaoyang & Chen, Guo & Zhu, Zhenshan & Zhu, Xuedong & Wang, Xunting, 2016. "Will electrical cyber–physical interdependent networks undergo first-order transition under random attacks?," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 235-245.
    17. Yuchen Pan & Shuai Ding & Wenjuan Fan & Jing Li & Shanlin Yang, 2015. "Trust-Enhanced Cloud Service Selection Model Based on QoS Analysis," PLOS ONE, Public Library of Science, vol. 10(11), pages 1-19, November.
    18. Wang, Jianwei & Jiang, Chen & Qian, Jianfei, 2014. "Robustness of interdependent networks with different link patterns against cascading failures," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 393(C), pages 535-541.
    19. Jiang, Zhongzhou & Liu, Jing & Wang, Shuai, 2016. "Traveling salesman problems with PageRank Distance on complex networks reveal community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 463(C), pages 293-302.
    20. Wang, Juan & Li, Chao & Xia, Chengyi, 2018. "Improved centrality indicators to characterize the nodal spreading capability in complex networks," Applied Mathematics and Computation, Elsevier, vol. 334(C), pages 388-400.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:chsofr:v:83:y:2016:i:c:p:125-132. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Thayer, Thomas R. (email available below). General contact details of provider: https://www.journals.elsevier.com/chaos-solitons-and-fractals .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.