A new hybrid genetic algorithm for the collection scheduling problem for a satellite constellation

M. Barkaoui and J. Berger

Journal of the Operational Research Society, 2020, vol. 71, issue 9, 1390-1410

Abstract: Many heuristics and meta-heuristics problem-solving methods have been proposed so far to solve the NP-hard multi-satellite collection scheduling problem (m-SatCSP). In particular, genetic algorithms (GAs), well-suited for large scale problems, its simplicity and low cost implementation have been pervasive. However, most contributions largely emphasise simple variant or basic GA principles promotion, overlooking prior problem structure exploitation or potential problem-solving benefits that may be conveyed from similar combinatorial optimisation problems such as the vehicle routing problem with time windows (VRPTW). In fact, despite some recognised similarity with VRPTW and early investigation on limited exact methods, few efforts have been successfully reported to adapt efficient advanced special-purpose problem-solving techniques to m-SatCSP. In this paper, a VRPTW-based hybrid genetic algorithm is proposed to tackle the single objective static m-SatCSP. The advocated approach combines and adapts well-known routing heuristics knowledge with standard genetic operator principles to efficiently explore promising search regions, manage constraint handling and improve solution quality. The hybrid strategy co-evolves two populations of solution plan individuals, maximising expected collection value while concurrently densifying collection paths to minimise orbit demand. Computational results show the approach to be cost-effective and competitive in comparison to some recent methods inspired from the best reported m-SatCSP heuristics.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1609891 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:71:y:2020:i:9:p:1390-1410

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1609891

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().