Branch-and-cut-and-price for agile earth observation satellite scheduling

The Agile Earth Observation Satellite scheduling selects and sequences satellite observations of possible targets on the Earth’s surface, each with a specific profit and multiple time windows. The objective is to maximize the collected profit of all observations completed under some operational constraints. The problem can be modeled as a variant of the Team Orienteering Problem with Time Windows (TOPTW). The key differences with the regular TOPTW are twofold: first, a time-dependent transition time is required for each pair of consecutive observations to adjust the camera’s look angles. Second, the time windows of each target vary during different observation cycles, called “orbits”. Some targets are invisible during certain orbits. We call this variant the Time-dependent Team Orienteering Problem with Variable Time Windows. In this paper, we present an efficient branch-and-cut-and-price (BCP) algorithm that exploits the problem’s characteristics to solve it to optimality. Some algorithmic enhancements have been implemented, such as a Lagrangian bound, an ng-path relaxation, a primal heuristic, and subset-row inequalities. Extensive experiments on different configurations of benchmark instances demonstrate the superior performance of the proposed BCP algorithm and its algorithmic enhancements. Moreover, the primal heuristic yields a high-quality lower bound and outperforms state-of-the-art heuristics. Finally, we adopt our framework to solve the well-known TOPTW, and our algorithm is much faster than state-of-the-art exact algorithms.