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

Conference paper (2018)

Authors

L. He Algorithmics - EEMCS , National University of Defense Technology
M.M. de Weerdt Algorithmics - EEMCS
N. Yorke-Smith Algorithmics - EEMCS
Xiaolu Liu National University of Defense Technology
Yingwu Chen National University of Defense Technology
Research Group
Algorithmics (EEMCS) (TU Delft)
Copyright: © 2018 L. He, M.M. de Weerdt, N. Yorke-Smith, Xiaolu Liu, Yingwu Chen
More Info
expand_more

Published Date

2018

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Technology

Research Group

Algorithmics

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

Files

W38.pdf
(pdf | 3.9 Mb)
- Embargo expired in 01-07-2019
Unknown license