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

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

Algorithmics

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

43 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 language	English
Title of host publication	SPARK 2018
Subtitle of host publication	Proceedings of the 11th International Workshop on Scheduling and Planning Applications (SPARK)
Editors	S. Bernardini, S, Parkinson, K. Talamadupula
Pages	45-52
Number of pages	8
Publication status	Published - 2018
Event	SPARK 2018: The 11th International Workshop on Scheduling and > Planning Applications - Delft, Netherlands Duration: 24 Jun 2019 → 29 Jun 2019 Conference number: 11th

Conference

Conference	SPARK 2018
Country/Territory	Netherlands
City	Delft
Period	24/06/19 → 29/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.

Access to Document

w38Final published version, 3.81 MB

Cite this

@inproceedings{28c63d1406fa431c9d91b43fd435831d,

title = "Tabu-Based Large Neighbourhood Search for Time-Dependent Multi-Orbit Agile Satellite Scheduling",

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",

author = "Lei He and {de Weerdt}, Mathijs and Neil Yorke-Smith and Xiaolu Liu and Yingwu Chen",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – 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.; SPARK 2018 : The 11th International Workshop on Scheduling and > Planning Applications ; Conference date: 24-06-2019 Through 29-06-2019",

year = "2018",

language = "English",

pages = "45--52",

editor = "S. Bernardini and S, Parkinson and K. Talamadupula",

booktitle = "SPARK 2018",

}

He, L, de Weerdt, M , Yorke-Smith, N, Liu, X & Chen, Y 2018, Tabu-Based Large Neighbourhood Search for Time-Dependent Multi-Orbit Agile Satellite Scheduling. in S Bernardini, S Parkinson & K Talamadupula (eds), SPARK 2018: Proceedings of the 11th International Workshop on Scheduling and Planning Applications (SPARK). pp. 45-52, SPARK 2018, Delft, Netherlands, 24/06/19.

Tabu-Based Large Neighbourhood Search for Time-Dependent Multi-Orbit Agile Satellite Scheduling. / He, Lei; de Weerdt, Mathijs ; Yorke-Smith, Neil et al.
SPARK 2018: Proceedings of the 11th International Workshop on Scheduling and Planning Applications (SPARK). ed. / S. Bernardini; S, Parkinson; K. Talamadupula. 2018. p. 45-52.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

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

AU - He, Lei

AU - de Weerdt, Mathijs

AU - Yorke-Smith, Neil

AU - Liu, Xiaolu

AU - Chen, Yingwu

N1 - Conference code: 11th

PY - 2018

Y1 - 2018

N2 - 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

AB - 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

M3 - Conference contribution

SP - 45

EP - 52

BT - SPARK 2018

A2 - Bernardini, S.

A2 - Parkinson, S,

A2 - Talamadupula, K.

T2 - SPARK 2018

Y2 - 24 June 2019 through 29 June 2019

ER -

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

Abstract

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this