Cabling optimization of a windfarm and capacitated K-Steiner tree

Cédric Bentz, Marie-Christine Costa, Alain Hertz and 
Pierre-Louis Poirion
october, 2014
Publication type:
International conference with proceedings
Conference:
PGMO-COPI'14 Gaspard Monge Program for Optimization - Conference on Optimization & Practices in Industry, Palaiseau, France
Keywords :
Steiner tree, graph, wind-farm optimization, mathematical programming.
Abstract:
A wind farm is composed of wind turbines producing energy and cables used to collect this energy and send it to a specific sub-station which then distributes power to customers. The cables laid between given connecting nodes. Engineering constraints impose that the energy flowing through a cable is unsplittable, i.e. the energy routed from turbines to a connecting node through different cables is then routed through a unique cable path from this node to the root. Knowing the location and production of turbines and the location, capacity and cost of all possible cables with their connecting nodes, the wind farm network design problem is to optimize the total length of required cables to install. A version of the problem including the possibility of parallel cables between connecting nodes and other constraints is studied in [4] where an approach based on integer linear programming is proposed to solve real-world instances. The problem is in closed relation with the well-know Steiner tree problem: given a weighted graph G, the K-Steiner tree problem is to find in G a minimum length tree S spanning a specified set T of K vertices called terminals. More precisely, the basic network design problem corresponds to the capacitated rooted K-Steiner tree problem. In our problem, the sub-station is the root of the graph and the wind turbines are the terminals. The possible cables are the edges of the graph and the connecting nodes are the Steiner nodes. Any solution of the network design problem corresponds to an anti-rooted Steiner tree. We pesent some complexity results, algorithms solving special cases and a solution based on mathematical programming to solve the general problem.
BibTeX:
@inproceedings{Ben-Cos-Her-Poi-2014,
    author={Cédric Bentz and Marie-Christine Costa and Alain Hertz and 
           Pierre-Louis Poirion },
    title={Cabling optimization of a windfarm and capacitated K-Steiner 
           tree },
    organization={PGMO-COPI'14 Gaspard Monge Program for Optimization - 
           Conference on Optimization & Practices in Industry, Palaiseau, 
           France },
    year={2014 },
    month={10},
    pages={4 pages},
}