Journal
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
Volume 20, Issue 2, Pages 137-157Publisher
KLUWER ACADEMIC PUBL
DOI: 10.1023/A:1011203002719
Keywords
tabu search; heuristics; satellite photograph scheduling; multidimensional knapsack; constrained combinatorial optimization
Ask authors/readers for more resources
The daily photograph scheduling problem of earth observation satellites such as Spot 5 consists of scheduling a subset of mono or stereo photographs from a given set of candidates to different cameras. The scheduling must maximize a profit function while satisfying a large number of constraints. In this paper, we first present a formulation of the problem as a generalized version of the well-known knapsack model, which includes large numbers of binary and ternary logical constraints. We then develop a tabu search algorithm which integrates some important features including an efficient neighborhood, a dynamic tabu tenure mechanism, techniques for constraint handling, intensification and diversification. Extensive experiments on a set of large and realistic benchmark instances show the effectiveness of this approach.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available