Time-dependent Agile Earth Observation Satellite Scheduling Models And Methods

Earth Observation Satellites(EOSs)become one of the most crucial space platforms for acquiring the images of the Earth surface.Due to the advantages of long imaging time,wide coverage and the boundaryless range,EOSs have played an important role in natural disaster monitoring,weather monitoring,military reconnaissance and so on.As the development of economy and technology,a increasing number of imaging demand are emerging.Thus,optimizing the efficiency of the satellite systems with the limited number of satellite resources has become a key subject worthy of study.As the new generation of the EOSs,Agile Earth Observation Satellites(AEOSs)can mobile on three axes(roll,pitch and yaw).Thus,AEOS has stronger observing capacity.However,the scheduling of AEOSs are more challenging due to the complexity of its constraints and giant solution space.Our work focuses on the AEOS scheduling problem with time-dependent transition times and the problem with time-dependent profits.The former refers to the situation where the transition time for each angle attitude maneuver depends on the observation start time,while the latter means that the actual profit of each observation also depends on its start time.We present a high-efficiency heuristic method and an exact method for both two problems.The principle of designing the heuristics is simple but efficient,thus allowing to be applied in engineering and applications.The exact methods are designed sophisticatedly,coupling with a variety of advanced techniques.The optimality of the exact solutions are guaranteed by several mathematical propositions.The main contributions of our work are listed as follows:(1)We are the first to model and analyze the time-dependency of the transition time in the AEOS scheduling.We prove that it satisfies the First-In-First-Out rule and the triangle inequalities rule,which provide a novel thought of solving the problem.Based on these rules,we propose a concept of ”minimal transition time” to replace the actual transition time in order to reduce the complexity.A pre-process method of calculating the minimal transition time is proposed to reduce the computational time.The numerical results show that when the time-dependence of the transition time is considered,the total collected profits are increased by 40%.By means of the pre-processing method,the computational time is reduced by 50%.Besides,our work describe and model the time-dependent profit with a non-monotonic function according to the practical need of satellite images.A integer linear programming model is built based on the time-index decision variables.(2)We design a heuristic for the AEOS scheduling with time-dependent transition times.The heuristic is based on a Greedy Randomized Iterated Local Search(GRILS)framework,which tunes the algorithmic parameters adaptively.To reduce the influence of the time windows constraints,we present an insert operator with fast feasibility check,allowing more observations by moving the scheduled observations in the solution forward or backward.The comparative results show that our heuristic performs much better than the state-of-the-art algorithms(50% on single satellite scheduling and 30% multiple satellite scheduling).(3)We present a heuristic for the AEOS scheduling with time-dependent profits.The framework of the heuristic is a so-called Bidirectional Dynamic Programming based Iterated Local Search algorithm,which embeds the bidirectional dynamic programming into the insert operator to guide the direction of search.The algorithm mainly addresses two subproblems: 1)given a sequence of observations,how to optimize the observation start times and evaluate the actual total profits of the sequence? 2)inserting a new observation may influence the start times of other scheduled observations,and thus influence the total profits.Therefore,an evaluation method is required to obtain the variation of the insertion to estimate its effectiveness.However,it inevitably increases the computational time.For the first subproblem,we present its optimal substructure,and use a dynamic programming method to evaluate the actual total profits within polynomial time.For the second subproblem,we embed the bidirectional dynamic programming into the insert operator to implement the fast evaluation of the insertion.The results show that compared with several different evaluation methods,our bidirectional dynamic programming can guide the search,and greatly reduce the computational time caused by the evaluation.(4)we creatively propose the first exact algorithm for the AEOS scheduling with time-dependent transition time.Due to the block diagonal matrix of the model,we employ a branch-and-price-and-cut framework to solve this problem.Valid inequalities are introduced into a branch-and-price algorithm to form this framework in order to optimize the integrity gap.At each node of the branching search,a column generation method is applied to solve the linear relaxation model of the problem.Firstly,the primal problem is transferred into a set-packing master problem and several identical pricing subproblems based on the Dantzig-Wolfe decomposition.The pricing subproblem corresponds to the Resource Constrained Elementary Shortest Path Problem(RCESPP),which can be solved by a labeling-based bidirectional dynamic programming.Since the complexity of the subproblem mainly comes from the elementary constraint,we introduce two relaxation techniques.According to the feature of the master problem,we present a novel branching strategy and prove its effectiveness and feasibility.To accelerate the column generation,we derive the Lagrangian upper bound of the model to set a new termination condition.To reduce the size of branching tree,we present a primal heuristic to construct a high-quality initial solution.The numerical results demonstrate the efficiency of the proposed algorithmic mechanism.For the Chinese instances with 200 targets,our exact algorithm only requires hundreds of seconds.(5)We present an exact algorithm for the AEOS scheduling with time-dependent profits.The algorithm is based on branch-and-price framework.Its pricing subproblem is a special RCESPP where the reduced cost only only depends on the selected observations,but also depends on their start times.This special RCESPP has not been studied in the literature.Based on the above-mentioned bidirectional dynamic programming,we define an accumulated weighted function for each label(subpath),where each data point in the function corresponds to a ”state”.Each state is a feasible solution for the proposed RCESPP.Afterwards,the label extend functions and the dominance rules are applied on the states.In this way,the proposed RCESPP can be solved to optimality.However,its efficiency cannot satisfy the requirement of column generation.Therefore,we define a novel ”partial dominance rule”,which prunes more unpromising labels by sharping the rule.Second,we merge the labels as much as possible to reduce the numbers of extension.Third,we propose a detour pruning strategy and prove its effectiveness.Last,we found that different directions of extension may highly affect the efficiency.Thus,we propose a heuristic to obtain the best direction.The results have proved the effectiveness of the four proposed improvements.The exact algorithm can solve most of the median size of Chinese instance within hundreds of seconds.