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

AN - SCOPUS:85067563090

VL - 111

SP - 84

EP - 98

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -