Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959045 | Computers & Operations Research | 2017 | 39 Pages |
Abstract
Agile satellites belong to the new generation of satellites with three degrees of freedom for acquiring images on the Earth. As a result, they have longer visible time windows for the requested targets. An image shot can be conducted at any time in the window if and only if the time left is sufficient for the fulfillment of the imaging process. For an agile satellite, a different observation time means a different image angle, thus defining a different transition time from its neighboring tasks. Therefore, the setup time for each imaging process depends on the selection of its observation start time, making the problem a time-dependent scheduling problem. To solve it, we develop a metaheuristic, called adaptive large neighborhood search (ALNS), thus creating a conflict-free observational timeline. ALNS is a local search framework in which a number of simple operators compete to modify the current solution. In our ALNS implementation, we define six removal operators and three insertion operators. At each iteration, a pair of operators is selected to destroy the current solution and generate a new solution with a large collection of variables modified. Time slacks are introduced to confine the propagation of the time-dependent constraint of transition time. Computational experiments show that the ALNS metaheuristic performs effectively, fulfilling more tasks with a good robustness.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Xiaolu Liu, Gilbert Laporte, Yingwu Chen, Renjie He,