Rechercher

Câblage dans les smart-grids et Problème de Steiner

Début: 02-01-2014
Fin: 31-12-2015
Convention: PGMO

Le développement des nouvelles énergies (éolienne, solaire, etc.) fait surgir de nombreux problèmes complexes d'optimisation. Quel type d'éoliennes faut-il utiliser et où les placer de façon à être le plus efficace possible tout en ayant un coût minimal ? Comment répartir des capteurs photovoltaïques? Comment organiser le routage des câbles utilisés pour la collecte et la distribution de l'énergie ? Etc.

 

Les études qui sont menées actuellement sur l'optimisation des smart grids considèrent le plus souvent des modèles continus ou utilisent une approche de résolution par simulation. Or, la plupart des problèmes ont des composantes entières: on n'installe pas un "morceau" d'éolienne ou de capteurs, on ne route pas une fraction de câbles. Cet aspect discret a été peu étudié malgré les importants enjeux économiques et écologiques.

 

Nous nous intéressons ici au routage des câbles permettant de collecter l'énergie produite dans un parc de production d'électricité hybride : il s'agit de déterminer le type de câbles à utiliser, le placement des équipements intermédiaires de raccordement et le routage des câbles, permettant de minimiser le coût total de l'installation de collecte. Le problème considéré est alors un problème de Steiner généralisé (détaillé plus bas). La solution proposée devra prendre en compte la durée de vie et la maintenance du réseau. L'un des objectifs de l'étude est en particulier de montrer, d'une part, que les modèles proposés pour un problème concret donné peuvent avoir des aspects génériques pour la Recherche Opérationnelle et, d'autre part, que des techniques modernes de RO, non utilisées actuellement pour ce type de problèmes, peuvent aider à la gestion des énergies nouvelles (ou pour d'autres applications liées au problème de Steiner généralisé).

 

 

Participants

CEDRIC

Marie-Christine Costa
Responsable
Cédric Bentz

Alain Hertz

Description

On commencera par s'intéresser à la collecte de l'électricité produite par un parc d'éoliennes. Comme cela a déjà été mentionné, le problème à résoudre est en fait la généralisation d'un problème bien connu en théorie des graphes : le problème de l'arbre de Steiner. Etant donné un graphe muni d'une fonction de coût sur les arêtes et un sous-ensemble V de sommets de ce graphe, il s'agit de déterminer le sous-graphe permettant de relier les sommets de V pour un coût minimal. Ce problème, qui généralise le problème de l'arbre couvrant, a de nombreuses applications, en particulier dans les problèmes de transport et de localisation. Il a été beaucoup étudié, sans toutefois prendre en compte divers aspects spécifiques à notre problème. C'est un problème NP-difficile qui, bien qu'étant moins général que le problème qu'on se propose d'étudier, est déjà connu comme étant difficile à résoudre de façon efficace.

 

Plus précisément, le problème qui se pose est le suivant. Soit un graphe orienté avec des sommets imposés et un sommet considéré comme racine r. Chaque arc a un coût et une capacité. On recherche une arborescence de racine r qui contienne tous les sommets imposés, qui soit de coût minimum, et telle que pour chaque arc de l'arborescence, le nombre de feuilles qui précèdent cet arc ne dépasse pas la capacité de l'arc.

 

La première étape du travail consistera à étudier en détail la complexité du problème, et à cerner les cas "faciles" (c'est-à-dire polynomiaux) et les cas "difficiles" (c'est-à-dire au moins NP-difficiles). On s'attachera également à concevoir une ou des heuristique(s) pour ce problème (avec ou sans garantie de performance a priori), de façon à pouvoir le résoudre le plus rapidement possible, au moins de façon approchée.

 

On s'intéressera ensuite à proposer et implémenter un modèle de programmation mathématique en nombres entiers permettant de résoudre ce problème difficile de façon exacte dans le cas général. Pour accélérer la résolution de ce modèle, on pourra utiliser des méthodes basées sur des progrès récents en optimisation combinatoire, telles l'introduction de coupes ou différentes méthodes de convexification, ainsi que sur l’utilisation de logiciels de programmation mathématique standard et très efficaces, tels que CPLEX ou XPRESS. Si le temps le permet, on essayera dans un deuxième temps de concevoir d'autres modèles alternatifs pour résoudre le problème de façon exacte. Quoi qu'il en soit, pour chacun des modèles ainsi proposés, on essayera de le rendre le plus réaliste possible, tout en restant capable de le traiter efficacement. En effet, de façon générale, il y aura souvent un compromis à trouver entre la fidélité du modèle considéré par rapport au problème initial, et le temps de calcul nécessaire pour déterminer une solution optimale d'un tel modèle.

Enfin, il serait intéressant, dans un dernier temps, de chercher à résoudre, à l'aide du ou des modèles et méthodes proposés, le problème d'optimisation de routage de câbles d'un parc éolien sur des données réelles. Ces données pourront être fournies, par exemple, par la société canadienne Hatch, spécialiste de l'éolien, ou par EDF.

2016

2014