| Imagery satellites have served many purposes ranging from national security missions to agricultural and environmental monitoring. The need to schedule imagery collections for satellites has been important since their inception; however, the constellations have only included a few satellites. The full constellation of the satellites represented in this research will be a leap in capacity that has only recently been considered. The fundamental question for the multi-satellite collection scheduling problem involves three inter-related considerations: 1) which targets should be imaged; 2) which satellite should image each target; and 3) when should each imaging task begin.;Numerous methods have been used to address the current collection scheduling problem, including simulated annealing, genetic algorithms, tabu search, variations of greedy algorithms, and constraint programming, with the general consensus being that pure integer programming is not practical for realistically-sized problems due to their highly combinatorial nature.;The methodology used in this research is a unique approach to the large multi-satellite collection scheduling problem that had not been previously investigated. This novel approach involves three sequential steps, "cluster-route-schedule". The first step, "cluster", groups imaging targets into clusters using a statistical method, based on a variety of parameters. The second step, "route", uses the decomposition method of column generation to determine which clusters each of the satellites should image throughout its orbital revolution, and when. The third step, "schedule", schedules the individual imaging targets within each cluster, using time-space networks and heuristics.;This research provides an integer programming-based method for scheduling imagery collection for large multi-satellite constellations that employ innovative technological advances in satellite maneuverability. The methodology is extendable to other types of satellite constellations (including fewer or more satellites), and possibly to some scheduling and routing problems in general. |
