Friday 28
Heuristics and meta-heuristics
Alexandre Gondran
› 11:30 - 12:00 (30min)
› Bât. C - Sigalas
Optimisation du placement des faisceaux d'un satellite de télécommunications
Jean-Thomas Camino  1@  
1 : Laboratoire d'analyse et d'architecture des systèmes [Toulouse]  (LAAS)  -  Website
Institut National Polytechnique de Toulouse - INPT, Université Paul Sabatier (UPS) - Toulouse III, CNRS : UPR8001, Institut National des Sciences Appliquées [INSA] - Toulouse
7 Av du colonel Roche 31077 TOULOUSE CEDEX 4 -  France

Les satellites de télécommunications multifaisceaux ont la particularité de proposer des couvertures à partir d'une pluralité de faisceaux étroits qui permettent de profiter de meilleurs gains antenne et de la possibilité de réutiliser la ressource fréquentielle qui est chère et donc limitée. Le placement des différents faisceaux sur la zone à couvrir est un problème complexe qui doit être résolu sous différentes contraintes technologiques liées à l'architecture des antennes, tout en optimisant plusieurs critères liés au coût du satellite et à la mission télécom à assurer. La discrétisation de l'espace continu des possibles pour les centres de ces faisceaux positionne le problème dans le monde de l'optimisation combinatoire. Le lien avec le problème du k-centre métrique et une modélisation faisant appel à la théorie des graphes seront présentés. Cette dernière permet d'interpréter le problème comme étant celui de la recherche d'un sous-graphe 4-colorable optimal au sens d'une certaine fonction objectif. L'heuristique de résolution proposée construit la solution faisceau par faisceau selon une approche gloutonne multi-start randomisée. Pour chaque nouveau faisceau "difficile" en termes de coloration, une heuristique de réparation faisant appel à un recuit simulé est appliquée.


Online user: 2