Designing and Expanding Electrical Networks – Complexity and Combinatorial Algorithms

The transition from conventional to renewable power generation has a large impact on when and where electricity is generated. To deal with this change the electric transmission network needs to be adapted and expanded.
Expanding the network has two benefits. Electricity can be generated at locations with high renewable energy potentials and then transmitted to the consumers via the transmission network.
Without the expansion the existing transmission network may be unable to cope with the transmission needs, thus requiring power generation at locations closer to the energy demand, but at less well-suited locations. Second, renewable energy generation (e.g., from wind or solar irradiation) is typically volatile. Having strong interconnections between regions within a large geographical area allows to the smooth the generation and demand over that area. This smoothing makes them more predictable and the volatility of the generation easier to handle.

In this thesis we consider problems that arise when designing and expanding electric transmission networks. As the first step we formalize them such that we have a precise mathematical problem formulation. ... mehrAfterwards, we pursue two goals: first, improve the theoretical understanding of these problems by determining their computational complexity under various restrictions, and second, develop algorithms that can solve these problems.

A basic formulation of the expansion planning problem models the network as a graph and potential new transmission lines as edges that may be added to the graph. We formalize this formulation as the problems Flow Expansion and Electrical Flow Expansion, which differ in the flow model (graph-theoretical vs. electrical flow). We prove that in general the decision variants of these problems are $\mathcal{NP}$-complete, even if the network structure is already very simple, e.g., a star. For certain restrictions, we give polynomial-time algorithms as well. Our results delineate the boundary between the $\mathcal{NP}$-complete cases and the cases that can be solved in polynomial time.

The basic expansion planning problems mentioned above ignore that real transmission networks should still be able to operate if a small part of the transmission equipment fails. We employ a criticality measure from the literature, which measures the dynamic effects of the failure of a single transmission line on the whole transmission network. In a first step, we compare this criticality measure to the well-used $N-1$ criterion.
Moreover, we formulate this criticality measure as a set of linear inequalities, which may be added to any formulation of a network design problem as a mathematical program. To exemplify this usage, we introduce the criticality criterion in two transmission network expansion planning problems, which can be formulated as mixed-integer linear programs (MILPs). We then evaluate the performance of solving the MILPs. Finally, we develop a greedy heuristic for one of the two problems, and compare its performance to solving the MILP.

Microgrids play an important role in the electrification of rural areas. We formalize the design of the cable layout of a microgrid as a geometric optimization problem, which we call Microgrid Cable Layout. A key difference to the network design problems above is that there is no graph with candidate edges given. Instead, edges and new vertices may be placed anywhere in the plane. We present a hybrid genetic algorithm for Microgrid Cable Layout and evaluate it on a set of benchmark instances, which include a real microgrid in the Democratic Republic of the Congo.

Finally, instead of expanding electrical networks one may place electric equipment such as FACTS (flexible AC transmission system). These influence the properties of the transmission lines such that the network can be used more efficiently. We apply a model of FACTS from the literature and study the problem whether a given network with given positions and properties of the FACTS admits an electrical flow provided that FACTS are set appropriately.
We call such a flow a FACTS flow. In this thesis we prove that in general it is $\mathcal{NP}$-complete to determine
whether a network admits a FACTS flow, and we present polynomial-time algorithms for two restricted cases.