Multiple Earth Observation Satellites Cooperative Observing Area Covering Optimization Method

The engineers who made plans for the Earth observation satellite(EOS)usually encountered such a situation where the users need the image of a large region during a short time horizon.To please the users,they have to use multiple EOSs to observe the region in a cooperative manner.The problem of making plans for the EOSs in this situation is studied in this dissertation.There are a large region R and several EOSs,each of which can image a strip area in a single shot(the strip is smaller than R).With fixed viewing angle,the camera of an EOS can perform rolling maneuver when imaging.As a result,the imaged strip will have different locations and widths if the EOS rolls its camera.Moreover,imaging at different start or stop times will get strips with different locations and lengths,too.This means the location,the length and the width of imaged strip of an EOS is variable.The problem is to make a “good” schedule which details the imaging actions of each EOS such that the locations,the lengths and the widths of all image strips are determined and some objectives are optimized.The problem is a combinotrial optimization problem in continuous space,highly coupled with computational geometry.It is not easy to solve such a problem in a straitforward manner.This dissertation provided a dedicated study and put forward solution methods for it.The main contributions are as follows:(1)Three variant problems are put forward and researched,namely maximizing the total covered area when covering opportunities are insufficient;minimizing the makespan of covering the whole region when covering opportunities are sufficient;minimizing the cost of covering the whole region when covering opportunities are sufficient.The features of the three problems are analyzed and corresponding integer linear programming formulations are modeled based on the grid discretization method.(2)An efficient heuristic with polynomial complexity is developed for the first problem,and a Lagrangian relaxation upper bound is computed to evaluate the solutions that found.The simulated experiments show that the heuristic can find near-optimal(optimal gap < 1%)solutions for small scale instances.A two-pahse heuristic with polynomial complexity is put forward for the second problem and the simulated experiments show that this method can find high quality solutions at a low computational cost.An implicit-based branch and price(IE-BP)algorithm is developed for the third problem,on the proposing and proof of a dominace rule which can be used to reduce the magnitude of price problems' solution spaces.As a result,a lot of columns can be dominated in advance and the solution process can be accelerated.The simulated experiments show that the proposed dominace rule can reduce about 68% columns averagely.For some instances,near-optimal solutions are found and it runs faster than well-known commercial solver Gurobi on finding comparable solutions.(3)A nested-grids based approximating strategy is put forward.Firstly,a solution on a grid whose cells have a big size(denoted as father grid)is computed by the heuristic,the two-phase heuristic or the IE-BP algorithm.Secondly,a nested grid with small sized cells(denoted as son grid)is established on father grid and the found solution is mapped to the son grid.Thirdly,a further search among the “around” of the mapped solution on the son grid is performed to improve the solutions quality.As the further search is carried out based on the found solution,it comsumes comsiderable few computational costs.These three steps are called approximating strategy and it can be re-used several times such that the ultimate cells' size is small enough.The simulated experiments show that this strategy is stable and efficient.(4)For large scalled instances,a clique-based solution strategy is put forward according to the idea of “divide and conque”.The large region will be divided into several small cliques and the covering opportunities are allocated to the cliques.Each clique will be solved independently and their covering plans together formed the solution for the large region.Different allocation of covering opportunities will lead to different covering plans for the cliques and the ultimate solution will be different accordingly.Therefore,a simulated annealing(SA)meta-heuristic is employed to search for the good assignment of covering opportunities.The simulated experiments show that for some large scaled instances,it takes considerable computational costs when solving it directly.What's more,some instances are even not solvable in this manner.While when the clique-based strategy is used,high quality solutions are often acquired in acceptable CPU times.