A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems
RAIRO - Operations Research - Recherche Opérationnelle, Volume 49 (2015) no. 1, pp. 99-121.

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.

Received:
Accepted:
DOI: 10.1051/ro/2014027
Classification: 9008
Keywords: Metaheuristics, combinatorial optimization, satellite scheduling, consistent neighborhood search
Zufferey, Nicolas 1; Vasquez, Michel 2

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.
@article{RO_2015__49_1_99_0,
     author = {Zufferey, Nicolas and Vasquez, Michel},
     title = {A {Generalized} {Consistent} {Neighborhood} {Search} for {Satellite} {Range} {Scheduling} {Problems}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {99--121},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {1},
     year = {2015},
     doi = {10.1051/ro/2014027},
     mrnumber = {3349119},
     zbl = {1310.90068},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2014027/}
}
TY  - JOUR
AU  - Zufferey, Nicolas
AU  - Vasquez, Michel
TI  - A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 99
EP  - 121
VL  - 49
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2014027/
DO  - 10.1051/ro/2014027
LA  - en
ID  - RO_2015__49_1_99_0
ER  - 
%0 Journal Article
%A Zufferey, Nicolas
%A Vasquez, Michel
%T A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 99-121
%V 49
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2014027/
%R 10.1051/ro/2014027
%G en
%F RO_2015__49_1_99_0
Zufferey, Nicolas; Vasquez, Michel. A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems. RAIRO - Operations Research - Recherche Opérationnelle, Volume 49 (2015) no. 1, pp. 99-121. doi : 10.1051/ro/2014027. http://archive.numdam.org/articles/10.1051/ro/2014027/

L. Barbulescu, J.-P. Watson, L.D. Whitley and A.E. Howe, Scheduling space-ground communications for the air force satellite control network. J. Sched. 7 (2004) 7–34. | DOI | Zbl

R.S. Barr, B.L. Golden, J.P. Kelly, M.G.C. Resende and W.R. Stewart, Designing and reporting on computational experiments with heuristic methods. J. Heuristics 1 (1995) 9–32. | DOI | Zbl

E. Bensana, M. Lemaitre and G. Verfaillie, Earth observation satellite management. Constraints 4 (1999) 293–299. | DOI | Zbl

I. Bloechliger and N. Zufferey, A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35 (2008) 960–975. | DOI | MR | Zbl

J.-F. Cordeau, G. Laporte and A. Mercier, A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52 (2001) 928–936. | DOI | Zbl

A. Dupont, E. Alverhne and M. Vasquez, Efficient filtering and tabu search on a consistent neighbourhood for the frequency assignment problem with polarisation. Ann. Oper. Res. 130 (2004) 179–198. | DOI | MR | Zbl

A. Dupont, A. Carneiro–Linhares, Ch. Artigues, D. Feillet, Ph. Michelon and M. Vasquez, The dynamic frequency assignment problem. Eur. J. Oper. Res. 195 (2009) 75–88. | DOI | MR | Zbl

M. Garey and D.S. Johnson, Computer and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco (1979). | MR | Zbl

M. Gendreau and J.-Y. Potvin, Handbook of metaheuristics, International Series in Operations Research & Management Science, vol. 146. Springer (2010). | Zbl

A. Globus, J. Crawford, J. Lohn and A. Pryor, A comparison of techniques for scheduling earth observing satellites. In Proceedings of the Sixteenth Innovative Applications of Artificial Intelligence Conference (IAAI-04), San Jose (2004).

F. Glover and M. Laguna, Tabu search. Kluwer Academic Publishers, Boston (1997). | MR | Zbl

D. Habet, M. Vasquez and Y. Vimont, Bounding the optimum for the problem of scheduling the photographs of an agile Earth observing satellite. Comput. Opt. Appl. 47 (2010) 307–333. | DOI | MR | Zbl

A. Hertz, D. Schindl and N. Zufferey, A solution method for a car fleet management problem with maintenance constraints. J. Heuristics 15 (2009) 425–450. | DOI | Zbl

D.S. Johnson, A theoretician’s guide to the experimental analysis of algorithms. DIMACS Ser. Discr. Math. Theor. Comput. Sci. 59 (2002) 215–259. | DOI | MR | Zbl

S. Lin, Computer solutions of the traveling salesman problem. Bell System Technical Journal 44 (1965) 2245–2269. | DOI | MR | Zbl

E. Malaguti, M. Monaci and P. Toth, A metaheuristic approach for the vertex coloring problem. INFORMS J. Comput. 20 (2008) 302–316. | DOI | MR | Zbl

C. Morgenstern, Distributed coloration neighborhood search. DIMACS Series in Discrete Math. Theor. Comput. Sci. 26 (1996) 335–357. | DOI | Zbl

D.A. Parish, A genetic algorithm approach to automating satellite range scheduling. Master’s thesis, Air Force Institute of Technology, USA (1994).

G.M. Ribeiro, M.F. Constantino and L.A.N. Lorena, Strong formulation for the spot 5 daily photograph scheduling problem. J. Combin. Opt. 20 (2010) 385–398. | DOI | MR | Zbl

Y. Rochat and E. Taillard, Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1 (1995) 147–167. | DOI | Zbl

M. Vasquez and J.-K. Hao, A heuristic approach for antenna positioning in cellular networks. J. Heuristics 7 (2001) 443–472. | DOI | Zbl

M. Vasquez and J.-K. Hao, A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite. Comput. Opt. Appl. 20 (2001) 137–157. | DOI | MR | Zbl

M. Vasquez and N. Zufferey, Consistent neighborhood search for combinatorial optimization. ISRN Comput. Math. (2012) 671423. | Zbl

M. Vasquez and N. Zufferey, Consistent neighborhood search for constrained assignment problems. In Proceedings of the 9th International Conference on Modeling, Opt. Simul. (MOSIM 2012), Bordeaux, France (2012).

G. Verfaillie, M. Lemaitre and T. Schiex, Russian doll search for solving constraint optimization problems. In 13th National Conference on Artificial Intelligence (AAAI-96), Portland, USA (1996) 181–187.

N. Zufferey, Metaheuristics: some Principles for an efficient design. Comput. Technol. Appl. 3 (2012) 446–462.

N. Zufferey, P. Amstutz and P. Giaccari, Graph colouring approaches for a satellite range scheduling problem. J. Sched. 11 (2008) 263–277. | DOI | MR | Zbl

Cited by Sources: