Maximizing the value of an Earth observation satellite orbit

Earth observation satellites are platforms equipped with optical instruments that orbit the planet. During the course of an orbit, they take photographs of some regions of the Earth at the request of customers. Each photograph generates a profit but, due to the presence of several constraints, not all requests can be satisfied. The problem is to select a subset of requests of maximal profit for a given orbit. The problem is solved by means of a tabu search heuristic and computational results are reported. This work was initiated as part of a challenge organized by the French Operational Research Society. The algorithm won the second prize in the final round of the competition.