Tabu-Based Large Neighbourhood Search for Time-Dependent Multi-Orbit Agile Satellite Scheduling

Lei He, Mathijs de Weerdt, Neil Yorke-Smith, Xiaolu Liu, Yingwu Chen

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

21 Downloads (Pure)

Abstract

Agile Earth observation satellite (AEOS) scheduling is complex, due to long visible time windows and time-dependent transitions between observations. We introduce a generic approach suited for scheduling problems characterised by time-dependency and/or sequence-dependency. Our approach is a novel hybridization of adaptive large neighbourhood search (ALNS) and tabu search. We further introduce partial sequence dominance and insertion position ordering operators to the ALNS. Extensive computational results on a real-world multi-orbit AEOS observation scheduling benchmark show that the hybrid ALNS robustly outperforms an improved mixed integer programming model and two recent state-of-the-art metaheuristic methods. The proposed method increases solution quality by more than 10% and reduces calculation time by more than 70% on average
Original languageEnglish
Title of host publicationSPARK 2018
Subtitle of host publicationProceedings of the 11th International Workshop on Scheduling and Planning Applications (SPARK)
EditorsS. Bernardini, S, Parkinson, K. Talamadupula
Pages45-52
Number of pages8
Publication statusPublished - 2018
EventSPARK 2018: The 11th International Workshop on Scheduling and > Planning Applications - Delft, Netherlands
Duration: 24 Jun 201929 Jun 2019
Conference number: 11th

Conference

ConferenceSPARK 2018
CountryNetherlands
CityDelft
Period24/06/1929/06/19

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Fingerprint

Dive into the research topics of 'Tabu-Based Large Neighbourhood Search for Time-Dependent Multi-Orbit Agile Satellite Scheduling'. Together they form a unique fingerprint.

Cite this