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

The problem of optimizing the design of network, in particular wind farm network, occurs when a company wishes to rent cables from a part of an existing transmission network owned by a third party (the government or another company) and construct or buy cables from the other part missing. It is possible to reformulate this problem as the Steiner tree problem in graph by adjusting the cost function of the transmission cables. Once this adaptation made, a heuristic using an exact method is developed. The heuristic developed is divided into two sections: 1) the construction of an initial feasible solution iteratively using the shortest path algorithm, and 2) improving this solution by a series of disconnection of parts of the solution and their connection to the other remaining portion not disconnected from the solution at hand. The results show that the method of construction of the initial solution sometimes fails to find a feasible solution. They also show that for large instances, the heuristic is very effective and will probably find good solutions also for very large problems, unthinkable to solve with current methods, if some adjustments are made.

Résumé

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.