Volume 49, Number 1, January-March 2015
Special ROADEF 2013. Guest editors: Andréa Cynthia Santos, Christian Prins, Alice Yalaoui
|Page(s)||99 - 121|
|Published online||17 December 2014|
A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems
1 Geneva School of Economics and Management, GSEM – University
of Geneva, Uni-Mail, 1211 Geneva 4, Switzerland.
2 École des Mines d’Alès, LGI2P Research Center, Site EERIE, Parc scientifique Georges Besse, 30035 Nimes Cedex 01, France.
Accepted: 5 May 2014
Many optimization problems require the use of a local search to find a satisfying solution in a reasonable amount of time, even if the optimality is not guaranteed. Usually, local search algorithms operate in a search space which contains complete solutions (feasible or not) to the problem. In contrast, in Consistent Neighborhood Search (CNS), after each variable assignment, the conflicting variables are deleted to keep the partial solution feasible, and the search can stop when all the variables have a value. In this paper, we propose a generalized version of CNS, discuss its performance according to various criteria, and present successful adaptations of CNS to three types of satellite range scheduling problems. Such problems are motivated by applications encountered by the French National Space and Aeronautic Agencies and the US Air Force Satellite Control Network. The described numerical experiments will demonstrate that CNS is a powerful and flexible method, which can be easily combined with efficient ingredients.
Mathematics Subject Classification: 9008
Key words: Metaheuristics / combinatorial optimization / satellite scheduling / consistent neighborhood search
© EDP Sciences, ROADEF, SMAI 2014
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.