IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v245y2015i2p542-554.html
   My bibliography  Save this article

A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite

Author

Listed:
  • Tangpattanakul, Panwadee
  • Jozefowiez, Nicolas
  • Lopez, Pierre

Abstract

This paper presents an indicator-based multi-objective local search (IBMOLS) to solve a multi-objective optimization problem. The problem concerns the selection and scheduling of observations for an agile Earth observing satellite. The mission of an Earth observing satellite is to obtain photographs of the Earth surface to satisfy user requirements. Requests from several users have to be managed before transmitting an order, which is a sequence of selected acquisitions, to the satellite. The obtained sequence has to optimize two objectives under operation constraints. The objectives are to maximize the total profit of the selected acquisitions and simultaneously to ensure the fairness of resource sharing by minimizing the maximum profit difference between users. Experiments are conducted on realistic instances. Hypervolumes of the approximate Pareto fronts are computed and the results from IBMOLS are compared with the results from the biased random-key genetic algorithm (BRKGA).

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:245:y:2015:i:2:p:542-554
    DOI: 10.1016/j.ejor.2015.03.011
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715002040
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.03.011?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. Beume, Nicola & Naujoks, Boris & Emmerich, Michael, 2007. "SMS-EMOA: Multiobjective selection based on dominated hypervolume," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1653-1669, September.
    2. J-F Cordeau & G Laporte, 2005. "Maximizing the value of an Earth observation satellite orbit," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(8), pages 962-968, August.
    3. 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.
    4. 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.
    5. Thiago Noronha & Mauricio Resende & Celso Ribeiro, 2011. "A biased random-key genetic algorithm for routing and wavelength assignment," Journal of Global Optimization, Springer, vol. 50(3), pages 503-518, July.
    6. 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.
    7. James C. Bean, 1994. "Genetic Algorithms and Random Keys for Sequencing and Optimization," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 154-160, May.
    8. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    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. Bernhard, Pierre & Deschamps, Marc & Zaccour, Georges, 2023. "Large satellite constellations and space debris: Exploratory analysis of strategic management of the space commons," European Journal of Operational Research, Elsevier, vol. 304(3), pages 1140-1157.
    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. 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.
    4. 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.
    5. 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.
    6. 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.

    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. 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.
    2. 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.
    3. 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.
    4. Lei He & Mathijs Weerdt & Neil Yorke-Smith, 2020. "Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm," Journal of Intelligent Manufacturing, Springer, vol. 31(4), pages 1051-1078, April.
    5. 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.
    6. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    7. Gonçalves, José Fernando & Resende, Mauricio G.C., 2015. "A biased random-key genetic algorithm for the unequal area facility layout problem," European Journal of Operational Research, Elsevier, vol. 246(1), pages 86-107.
    8. F. Stefanello & L. S. Buriol & M. J. Hirsch & P. M. Pardalos & T. Querido & M. G. C. Resende & M. Ritt, 2017. "On the minimization of traffic congestion in road networks with tolls," Annals of Operations Research, Springer, vol. 249(1), pages 119-139, February.
    9. Soares, Leonardo Cabral R. & Carvalho, Marco Antonio M., 2020. "Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 955-964.
    10. 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.
    11. Gonçalves, José Fernando & Wäscher, Gerhard, 2020. "A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects," European Journal of Operational Research, Elsevier, vol. 286(3), pages 867-882.
    12. Julliany S. Brandão & Thiago F. Noronha & Celso C. Ribeiro, 2016. "A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks," Journal of Global Optimization, Springer, vol. 65(4), pages 813-835, August.
    13. Geiza Silva & André Leite & Raydonal Ospina & Víctor Leiva & Jorge Figueroa-Zúñiga & Cecilia Castro, 2023. "Biased Random-Key Genetic Algorithm with Local Search Applied to the Maximum Diversity Problem," Mathematics, MDPI, vol. 11(14), pages 1-11, July.
    14. Pinto, Bruno Q. & Ribeiro, Celso C. & Rosseti, Isabel & Plastino, Alexandre, 2018. "A biased random-key genetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 271(3), pages 849-865.
    15. Caio César Freitas & Dario José Aloise & Fábio Francisco Costa Fontes & Andréa Cynthia Santos & Matheus Silva Menezes, 2023. "A biased random-key genetic algorithm for the two-level hub location routing problem with directed tours," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(3), pages 903-924, September.
    16. 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.
    17. Andrade, Carlos E. & Toso, Rodrigo F. & Gonçalves, José F. & Resende, Mauricio G.C., 2021. "The Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking and its real-world applications," European Journal of Operational Research, Elsevier, vol. 289(1), pages 17-30.
    18. Ghorashi Khalilabadi, S. M. & Roy, D. & de Koster, M.B.M., 2022. "A Data-driven Approach to Enhance Worker Productivity by Optimizing Facility Layout," ERIM Report Series Research in Management ERS-2022-003-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    19. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    20. Xiao, Yiyong & Zhang, Siyue & Yang, Pei & You, Meng & Huang, Jiaoying, 2019. "A two-stage flow-shop scheme for the multi-satellite observation and data-downlink scheduling problem considering weather uncertainties," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 263-275.

    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:ejores:v:245:y:2015:i:2:p:542-554. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.