A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems

Zufferey, Nicolas; Vasquez, Michel

RAIRO - Operations Research - Recherche Opérationnelle, Tome 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.

Classification : 9008
Mots clés : Metaheuristics, combinatorial optimization, satellite scheduling, consistent neighborhood search

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