< Terug naar vorige pagina

Publicatie

Agile Earth Observation Satellite Scheduling: an Orienteering Problem with Time-Dependent Pro fits and Travel Times

Tijdschriftbijdrage - Tijdschriftartikel

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 pro fit 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.
Tijdschrift: Computers & Operations Research
ISSN: 0305-0548
Volume: 111
Pagina's: 84 - 98
Jaar van publicatie:2019
BOF-keylabel:ja
IOF-keylabel:ja
BOF-publication weight:3
CSS-citation score:2
Auteurs:International
Authors from:Higher Education
Toegankelijkheid:Open