A Conflict-Priority-Based Variable Neighborhood Tabu Search Method for Multi-Satellite Scheduling

With the increasing number and capabilities of orbital satellites and their onboard sensors, satellites scheduling plays an important role in growing demands for Earth observation tasks. A conflict-priority-based variable neighborhood tabu search method is proposed in this paper. By analyzing the flexibility of resources, the conflict-priority of tasks, and the visible time window features, the indicators of the impact, the conflict, the flexibility, and the bad impact are first established. On this basis, a first-come first-served greedy algorithm and a minimum bad impact greedy algorithm are designed for the generation of the initial solution. some rule-based heuristic strategies are also adopted for optimizing. Additionally, the algorithm incorporates three types of neighborhood structures including insertion, swapping and rearrangement, and deletion, using a tabu list to avoid local optima. Experimental results indicate the validity and efficiency of the proposed method. All solutions are within 10% of the optimal solution, with some even within 5%.The proposed method is effective for obtaining optimum solutions or solutions with a very good quality in various multi-satellite scheduling scenarios of realistic planning.