Research On Branch-and-Price Based Multi-satellite Multi-station Integrated Scheduling Method

With the development of space remote sensing technology and the increase of the complexity and the number of space reconnaissance image requirements, jointly employing multiple reconnaissance satellites of different types to image ground targets of interest, and transfering the collected data back to ground data-receiving stations as soon as possible have been the inner requirement and the develop trend of related military applications. Therefore, the scheduling problem of reconnaissance satellites must comprehensively take into account of reconnaissance resources of multiple satellites and multiple ground stations, and must schedule imaging and data-downloading tasks as a whole. However, existing research has shortcomings in both model and algorithm aspects. Most exisiting models separate imaging and data-downloading, neglect or simplify the imaging and data-downloading joint constraints, such as the satellite onboard recorder capacity constraint, the corresponding constraint and the sequential constraint of the imaging task and the data-downloading task which belong to a same reconnaissance target, and the read-and-write type constraint of the onboard recorder. Most existing algorithms are heursitics and meta-heuristics with weak flexibility and weak expansibility. Therefore, the schedule results through the above models and algorithms cannot thoroughly exploit the whole performance of the reconnaissance satellites system including the ground stations, and a new method must be investigated to solve the complicated multi-satellite multi-station integrated scheduling problem.The multi-satellite multi-station integrated scheduling problem can be defined as follows: based on comprehensively consideration of reconnaissance satellite capacity, ground data-receiving station capacity and users'reconnaissance requirements, to assign resources to multiple imaging tasks and data-downloading tasks associated with multiple contending reconnaissance requirements, and to define each task's start time, in order to maximally satisfy users'reconnaissance requirements. Based on the understanding of the working principle and the reconnaissance requirements of the reconnaissance satellites application system, this thesis studies the multi-satellite multi-station integrated scheduling problem which comprehensively incorporates imaging and data-downloading tasks, attributes the problem to a class of heterogeneous multiple vehicle pickup and delivery problems with multiple time windows and renewable resource constraints, builds an integer programming model of the problem and designs branch-and-price algorithms for the problem for the first time. The main research content and contribution of the thesis are as follows:Firstly, this thesis analyses the working flow of the multi-satellite multi-station integrated scheduling problem, formulates the operational constraints associated with two types of disjunctive resources, i.e., the satellites and the data-receiving stations, studies the problem characteristics, such as resource over-subscription, multiple task processing modes, and non-monotonous storage level variation, and attributes the problem to a class of heterogeneous multiple vehicle pickup and delivery problems with multiple time windows and renewable resource constraints.Secondly, this thesis builds an integer programming model for the problem with the objective of maximizing the summed rewards of satisfied imaging requirements. The model simplifies the disjunctive constraints upon stations, partitions all the constraints into two types of constraints, i.e., coupled constraints among different satellites and separable constraints inside each satellite, breaks the model into a set covering master problem and a series of elementary longest path sub-problems with time windows and renewable resource constraints through Danzig-Wolfe decomposition principle, and designs a branch-and-price framework for the problem. The advantages of this framework lie in the hierarchy in which the master problem handles only the task assignment among different satellites through the coupled constraints, whereas the sub-problem handles the special constraints within each satellite in a divide-and-conquer manner. Therefore the framework distributes the problem difficulty embedded in the model to each satellite. Moreover, the framework algorithmically employs an incremental solving idea based on column generation, and it supports different sub-problem solving algorithms with the common aim of finding the sub-problem solutions which can iteratively improve the solution objective of the linear relaxation of the master problem. As to the fractional solutions for the master problem's linear relaxation, in order not to destroy the sub-problem's structure and not to impact the branch-and-bound's search efficiency, the framework employs the idea of branching on the flow variable associated with two consecutively processed imaging activities, and incorporates the heuristic information concerning the satellite workload in the branch variable selection, therefore accelerates the search process towards the integer optimal or near-optimal solutions for the original problem model.Thirdly, based on the stop condition for solving the linear relaxation of the master problem and based on the solution techniques for the sub-problem, the thesis provides an exact branch-and-price algorithm and an approximate branch-and-price algorithm respectively. The exact branch-and-price algorithm strictly respects the optimal condition for the linear relaxation of the master problem, and employs a dynamic programming algorithm to find the sub-problem's optimal solution based on label extending. In order to increase the search efficiency, the dynamic programming uses preliminarily reduction upon each satellite's activity digraph, forward and backward bidirectional label extending, and dominance relations among different labels for a same node in the digraph. Whereas the approximate branch-and-price does not require finding the optimal solution for the master problem's linear relaxation and it uses column generation-based heuristics to search for the satisfactory solutions for the sub-problem. The column generation-based heuristics take the columns in the optimal basis of the current iteration for the master problem solving procedure as the search starting point, and use a combination operation between two columns and an adjustment operation for single column. The combination and adjustment operations both use the idea of firstly ordering the activity sequence and then determining the start time for each activity. The decisions upon the imaging or data-downloading activity insertion and deletion in the operations are both based on the dual variable values in the master problem.Lastly, combined with the application instances, the thesis validates the correctness and validity of the proposed mathematical model and the designed algorithms, and makes comparative analysis between different branch-and-price algorithms and between branch-and-price algorithms and other problem solution methods. The results of the computational experiments make two-folded conclusions. First, the exact branch-and-price can solve the instances with middle or small sizes optimally in a short time. Second, compared with other heuristics, the approximate branch-and-price can achieve solution quality improvement at the cost of a certain amount of computational times. The conclusions show that the branch-and-price algorithms can effectively improve the performance of the whole satellites system, therefore will be of high theoretical and pratical value.