Optimisation de la conception d'un réseau de collecte d'énergie éolienne par recherche locale

Le problème de l'optimisation de la conception de réseaux, plus particulièrement d'un parc éolien, intervient lorsqu'une compagnie souhaite louer une partie des câbles de transmission d'un réseau appartenant à un tiers parti (l'État ou une autre compagnie) et construire/acheter l'autre partie manquante. Il est possible de reformuler ce problème comme le problème de l'arbre de Steiner en adaptant la fonction de coût des câbles de transmission. Une fois cette adaptation faite, une heuristique employant une méthode exacte est développée. L'heuristique développée se découpe en deux pans : 1) la construction d'une solution réalisable initiale itérativement en utilisant un algorithme de plus court chemin, et 2) l'amélioration de cette solution par une série de déconnexions de certaines parties de la solution et de leur reconnexion à l'autre partie restante non déconnectée de la solution en question. Les résultats montrent que la méthode de construction de la solution initiale échoue parfois à trouver une solution réalisable. Ils montrent également que pour de larges exemplaires, le prototype d'amélioration de la solution initiale s'avère très efficace et pourra vraisemblablement s'attaquer à de très gros problèmes, impensables à résoudre avec les méthodes actuelles, si quelques ajustements sont faits.