Agile earth observation satellite scheduling: An orienteering problem with time-dependent profits and travel times

Guansheng Peng, Reginald Dewil, Cédric Verbeeck, Aldy Gunawan, Lining Xing, Pieter Vansteenwegen

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

The scheduling problem of an Agile Earth Observation Satellite is to schedule a subset of weighted observation tasks with each a specific “profit” in order to maximize the total collected profit, under its operational constraints. The “time-dependent transition time” and the “time-dependent profit” are two crucial features of this problem. The former relates to the fact that each pair of consecutive tasks requires a transition time to maneuver the look angle of the camera from the previous task to the next task. The latter follows from the fact that a different look angle of an observation leads to a different image quality, i.e., the collected profit. Since the specific look angle of a task depends on its observation start time, both the transition time and the profit are “time-dependent”. We present a concept of “minimal transition time” to displace the transition time. On this basis, a bidirectional dynamic programming based iterated local search (BDP-ILS) algorithm is proposed, equipped with an insert procedure that avoids a full feasibility check. The bidirectional dynamic programming approach is integrated into the algorithm in order to efficiently evaluate a solution or an insert move when time-dependent profits are considered. Two types of experiments (with and without the time-dependent profits) are designed to evaluate the performance. The results without time-dependent profits show that our algorithm outperforms the state of the art in terms of solution quality and computational time. When time-dependent profits are considered, our BDP-ILS algorithm performs very well on smaller instances with a known optimal solution and on larger instances compared to four reference algorithms.

Original languageEnglish
Pages (from-to)84-98
Number of pages15
JournalComputers and Operations Research
Volume111
DOIs
Publication statusPublished - 1 Nov 2019

Fingerprint

Earth Observation
Travel Time
Travel time
Profit
Profitability
Earth (planet)
Scheduling
Satellites
Dynamic programming
Iterated Local Search
Dynamic Programming
Local Search Algorithm
Angle
Evaluate
Image Quality
Image quality
Scheduling Problem
Consecutive
Schedule
Optimal Solution

Keywords

  • Agile satellite scheduling
  • Iterated local search
  • Time-dependent profits
  • Time-dependent transition time

Cite this

Peng, Guansheng ; Dewil, Reginald ; Verbeeck, Cédric ; Gunawan, Aldy ; Xing, Lining ; Vansteenwegen, Pieter. / Agile earth observation satellite scheduling : An orienteering problem with time-dependent profits and travel times. In: Computers and Operations Research. 2019 ; Vol. 111. pp. 84-98.
@article{a189778aa6ba4b8db391a2b17dff6cbb,
title = "Agile earth observation satellite scheduling: An orienteering problem with time-dependent profits and travel times",
abstract = "The scheduling problem of an Agile Earth Observation Satellite is to schedule a subset of weighted observation tasks with each a specific “profit” in order to maximize the total collected profit, under its operational constraints. The “time-dependent transition time” and the “time-dependent profit” are two crucial features of this problem. The former relates to the fact that each pair of consecutive tasks requires a transition time to maneuver the look angle of the camera from the previous task to the next task. The latter follows from the fact that a different look angle of an observation leads to a different image quality, i.e., the collected profit. Since the specific look angle of a task depends on its observation start time, both the transition time and the profit are “time-dependent”. We present a concept of “minimal transition time” to displace the transition time. On this basis, a bidirectional dynamic programming based iterated local search (BDP-ILS) algorithm is proposed, equipped with an insert procedure that avoids a full feasibility check. The bidirectional dynamic programming approach is integrated into the algorithm in order to efficiently evaluate a solution or an insert move when time-dependent profits are considered. Two types of experiments (with and without the time-dependent profits) are designed to evaluate the performance. The results without time-dependent profits show that our algorithm outperforms the state of the art in terms of solution quality and computational time. When time-dependent profits are considered, our BDP-ILS algorithm performs very well on smaller instances with a known optimal solution and on larger instances compared to four reference algorithms.",
keywords = "Agile satellite scheduling, Iterated local search, Time-dependent profits, Time-dependent transition time",
author = "Guansheng Peng and Reginald Dewil and C{\'e}dric Verbeeck and Aldy Gunawan and Lining Xing and Pieter Vansteenwegen",
year = "2019",
month = "11",
day = "1",
doi = "10.1016/j.cor.2019.05.030",
language = "English",
volume = "111",
pages = "84--98",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Limited",

}

Agile earth observation satellite scheduling : An orienteering problem with time-dependent profits and travel times. / Peng, Guansheng; Dewil, Reginald; Verbeeck, Cédric; Gunawan, Aldy; Xing, Lining; Vansteenwegen, Pieter.

In: Computers and Operations Research, Vol. 111, 01.11.2019, p. 84-98.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Agile earth observation satellite scheduling

T2 - An orienteering problem with time-dependent profits and travel times

AU - Peng, Guansheng

AU - Dewil, Reginald

AU - Verbeeck, Cédric

AU - Gunawan, Aldy

AU - Xing, Lining

AU - Vansteenwegen, Pieter

PY - 2019/11/1

Y1 - 2019/11/1

N2 - The scheduling problem of an Agile Earth Observation Satellite is to schedule a subset of weighted observation tasks with each a specific “profit” in order to maximize the total collected profit, under its operational constraints. The “time-dependent transition time” and the “time-dependent profit” are two crucial features of this problem. The former relates to the fact that each pair of consecutive tasks requires a transition time to maneuver the look angle of the camera from the previous task to the next task. The latter follows from the fact that a different look angle of an observation leads to a different image quality, i.e., the collected profit. Since the specific look angle of a task depends on its observation start time, both the transition time and the profit are “time-dependent”. We present a concept of “minimal transition time” to displace the transition time. On this basis, a bidirectional dynamic programming based iterated local search (BDP-ILS) algorithm is proposed, equipped with an insert procedure that avoids a full feasibility check. The bidirectional dynamic programming approach is integrated into the algorithm in order to efficiently evaluate a solution or an insert move when time-dependent profits are considered. Two types of experiments (with and without the time-dependent profits) are designed to evaluate the performance. The results without time-dependent profits show that our algorithm outperforms the state of the art in terms of solution quality and computational time. When time-dependent profits are considered, our BDP-ILS algorithm performs very well on smaller instances with a known optimal solution and on larger instances compared to four reference algorithms.

AB - The scheduling problem of an Agile Earth Observation Satellite is to schedule a subset of weighted observation tasks with each a specific “profit” in order to maximize the total collected profit, under its operational constraints. The “time-dependent transition time” and the “time-dependent profit” are two crucial features of this problem. The former relates to the fact that each pair of consecutive tasks requires a transition time to maneuver the look angle of the camera from the previous task to the next task. The latter follows from the fact that a different look angle of an observation leads to a different image quality, i.e., the collected profit. Since the specific look angle of a task depends on its observation start time, both the transition time and the profit are “time-dependent”. We present a concept of “minimal transition time” to displace the transition time. On this basis, a bidirectional dynamic programming based iterated local search (BDP-ILS) algorithm is proposed, equipped with an insert procedure that avoids a full feasibility check. The bidirectional dynamic programming approach is integrated into the algorithm in order to efficiently evaluate a solution or an insert move when time-dependent profits are considered. Two types of experiments (with and without the time-dependent profits) are designed to evaluate the performance. The results without time-dependent profits show that our algorithm outperforms the state of the art in terms of solution quality and computational time. When time-dependent profits are considered, our BDP-ILS algorithm performs very well on smaller instances with a known optimal solution and on larger instances compared to four reference algorithms.

KW - Agile satellite scheduling

KW - Iterated local search

KW - Time-dependent profits

KW - Time-dependent transition time

UR - http://www.scopus.com/inward/record.url?scp=85067563090&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85067563090&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2019.05.030

DO - 10.1016/j.cor.2019.05.030

M3 - Article

VL - 111

SP - 84

EP - 98

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -