A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems
| Autor: | Michel Vasquez, Nicolas Zufferey |
|---|---|
| Přispěvatelé: | University of Geneva, University of Geneva [Switzerland], Laboratoire de Génie Informatique et Ingénierie de Production (LGI2P), IMT - MINES ALES (IMT - MINES ALES), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT) |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
Mathematical optimization
021103 operations research Optimization problem Combinatorial optimization Computer science 0211 other engineering and technologies Neighborhood search 02 engineering and technology Metaheuristics [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Management Science and Operations Research Satellite scheduling Computer Science Applications Theoretical Computer Science Scheduling (computing) Partial solution ddc:650 0202 electrical engineering electronic engineering information engineering Beam search 020201 artificial intelligence & image processing Consistent neighborhood search Air Force Satellite Control Network Metaheuristic ComputingMilieux_MISCELLANEOUS |
| Zdroj: | RAIRO-Operations Research RAIRO-Operations Research, EDP Sciences, 2015, 49 (1), pp.99-121. ⟨10.1051/ro/2014027⟩ RAIRO-Operations Research, Vol. 49, No 1 (2015) pp. 99-121 |
| ISSN: | 0399-0559 1290-3868 |
| DOI: | 10.1051/ro/2014027⟩ |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|