Time-window optimization for a constellation of earth observation satellite

Abstract

Satellite Scheduling Problems (SSP) are NP-hard and constraint programming and metaheuristics solution methods yield mixed results. This study investigates a new version of the SSP, the Satellite Constellation Time-Window Optimization Problem (SCoTWOP), involving commercial satellite constellations that provide frequent earth coverage. The SCoTWOP is related to the dual of the Vehicle Routing Problem with Multiple Timewindows, suggesting binary solution vectors representing an activation of time-windows. This representation fitted well with the MatLab® Genetic Algorithm and Direct Search Toolbox subsequently used to experiment with genetic algorithms, tabu search, and simulated annealing as SCoTWOP solution methods. The genetic algorithm was most successful and in some instances activated all 250 imaging time-windows, a number that is typical for a constellation of six satellites.