Name
Title | ||
|---|---|---|
Distance Preserving Recombination Operator for Earth Observation Satellites Operations Scheduling |
Abstract | ||
|---|---|---|
As was mentioned above the problem is a simplification of real problems appearing in the management of Earth observation satellites. In particular, we consider just a single revolution of the satellite. Below, we define it briefly. Given: • a number Nr of requests for satellite pictures that may be satisfied fully or partially (a request defines an area to be photographed), • a number Ns of strips on the Earth that can be used to acquire the requests, • a number Npa = 2Ns of possible strips acquisitions (each strip can be acquired in two directions of the camera movement), find a subset of acquisitions and their feasible schedule that maximizes the gain of the satellite operator. The satellite may acquire one strip at a time. The acquisitions have durations and time windows in which they are physically possible. Furthermore, a switching time may be calculated for each pair of acquisitions. The gain corresponding to a given request is a nonlinear function of the percentage of the request realized. The total gain is the sum of gains for particular requests. Some of the requests require stereoscopic pictures. In this case, pairs of twin strips are defined. The twin strips have to be either both realized or not realized at all. 3. Genetic local search for Earth observation satellites operations scheduling 3.1. Generation of initial solutions The initial solutions are generated by a greedy insertion heuristic. In each iteration the heuristics inserts a single acquisition to the solution. All acquisitions that can be inserted without violating constraints are evaluated. For each acquisition all feasible insertion positions in the current sequence of selected acquisitions are evaluated. Insertion of an acquisition increases the gain objective at the cost of the satellite's time. The satellite's time (including switching time) may be different depending on the insertion position. Thus, the insertion of an acquisition at a given position is evaluated by the ratio of the gain change over the satellite's time change. In each iteration the greedy insertion heuristic selects the acquisition and insertion position with the highest evaluation. In order to obtain a dispersed sample of initial solution the greedy insertion heuristic is not started from the empty solution but at the beginning a number of randomly selected acquisitions are inserted at randomly selected feasible positions. An effort was made to efficiently identify feasible insertion position by exploiting time constraints. This allowed for a significant improvement of the efficiency of this method. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s10852-007-9071-8 | J. Math. Model. Algorithms |
Keywords | Field | DocType |
hybrid evolutionary algorithms · recombination operators,local search,earth observation,satisfiability,genetics,time change | Memetic algorithm,Mathematical optimization,Scheduling (computing),Recombination operators,Artificial intelligence,Earth observation satellite,Mathematics,Machine learning | Journal |
Volume | Issue | ISSN |
7 | 1 | 1572-9214 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Jaszkiewicz | 1 | 660 | 50.68 |