Distribution network optimization: predicting computation times to design scenario analysis for network operators

To present the literature, we use the taxonomy of Georgilakis and Hatziargyriou [20], who classify studies according to their objective, the problem type, the planning period, and distribution levels. The distinction according to the objective indicates the optimization goals. The problem type can either design a new distribution network or expand an existing one and adapt it to future needs. The planning period can be a static single-stage period, where a solution is determined for a certain demand. A dynamic planning period designs a successive expansion plan for the distribution network, divided into multiple stages. The distribution level indicates whether a primary or secondary distribution network is considered, which maintains medium and low voltage, respectively.

To better address the need for further research, we add the categories of uncertainty management and the network size, that are part of the taxonomy of Saboori et al. [46]. In the area of uncertainty management, we distinguish between reliability and demand forecasting. The reliability indicates whether the distribution network design takes supply interruptions (e.g., due to damaged lines) into account. The demand forecast describes whether the model considers unknown future demand. The network size highlights the number of nodes, that are used for the evaluation in the respective studies. Table 1 summarizes the considered literature.

Distribution network optimization pursues various objectives like minimizing investment and operation cost, decreasing energy losses and emissions, and increasing reliability and social benefit. However, multi-criteria decision-making is not necessary since the different goals can be valued monetarily. All studies reviewed in Table 1 consider investment costs. Operational costs are sometimes neglected [17, 26, 44, 52] or included in the investment costs [3, 29]. Asensio et al. [4], El-Fouly et al. [17], Haffner et al. [22], Jabr [26], Jooshaki et al. [27], Santos et al. [47] and Shen et al. [51] pay special attention to energy production and loss costs. Energy production and loss costs refer to the conversion of energy, e.g., when substations change the voltage level, or generators and storages feed in energy. Asensio et al. [4], Haffner et al. [22], Jooshaki et al. [27], Lotero and Contreras [33], Santos et al. [47] and Shen et al. [51] also consider the cost of unserved energy. These costs are also called value of lost load and refer to expenses associated with a disruption of supply. Santos et al. [47], Wong et al. [57] and Zidan et al. [63] price CO\(_2\)-emissions and consider them to penalize investments in polluting generators. Asensio et al. [4] pay special attention to the social benefit of a solution in relation to the network’s consumers. They design their objective function to consider the consumer’s present costs as an available budget for investment and operative costs. The unused budget is maximized to prevent additional costs for consumers.

While few papers in the past newly construct distribution networks [17, 29, 30, 36, 37], most studies extend existing infrastructure. Arias et al. [3] keep a given initial solution and extend the distribution network. In addition to the expansion, Asensio et al. [4] allow the model to upgrade existing substations. Shen et al. [51] consider substations and lines and allow the replacement of existing parts of the distribution. This makes it possible to also scale back the distribution network and to better adapt it to the requirements.

Jabr [26], Li et al. [32], Paiva et al. [40], Santos et al. [47], Shen et al. [51] and Shu et al. [52] perform a static optimization. They calculate a distribution network for one certain time in the future. Prioritization and order of the expansion are left to the decision maker. Approaches with multiple time stages are more complex but offer the advantage of creating a more detailed expansion plan [3, 4, 17, 22, 27, 33].

Mendoza et al. [36], Nazar et al. [38] and Paiva et al. [40] state that the design of the secondary distribution network has an effect on the optimality of the overall design. Synergy effects between the two networks have a strong impact on investment costs. Thus, they consider an integral planning of the primary and secondary network. Cossi et al. [12] and Mendoza et al. [37] focus their work on the secondary distribution network. All other studies in Table 1 evaluate their approaches with primary network instances only and neglect the secondary network.

Another issue of distribution network optimization is the design of a reliable distribution network to prevent supply interruptions. To consider the reliability of the distribution network, the cost of unserved energy can be penalized to prevent unreliable networks [4, 18, 29, 30, 37, 38, 42, 44, 47, 49, 62]. Jooshaki et al. [27] and Lotero and Contreras [33] calculate a system average interruption frequency index to measure reliability and assign an objective coefficient. Instead of ensuring low supply interruptions, reliability can also be ensured by a flexible topology. A flexible topology is characterized by a redundant supply routes: if an interruption of supply occurs in a part of the network, it can be bypassed by changing the circuit and supplying the affected area via other feeders. For example, if one transformer of the network fails, the circuit of the network can be changed and affected customers can be supplied via other transformers. Shen et al. [51] formulate constraints to allow such a flexible topology. In the event of a supply interruption in the network, the topology can thus be flexibly switched and sections affected by supply interruptions can be covered via other routes. However, aforementioned approaches encourage reliability but not enforce it. Failures in the network do not receive sufficient attention, if the predicted costs of interruptions are too low. For this reason, they only partially meet the reliability criterion (cf. Table 1).

To account for different future situations, Asensio et al. [4] formulate their model as a scenario-based stochastic programming model. Arias et al. [3] introduce chance constraints to model uncertain conventional loads and the demand for electric vehicles. Koutsoukis et al. [29], Santos et al. [47], Shen et al. [51] and Shu et al. [52] use scenarios to map different cases of the future. The solutions of the future scenarios are collected into a solution pool. Experts can analyze this pool to make a selection for a final expansion strategy. Lotero and Contreras [33] calculate a solution for each year of the planning period to also provide an orientation in time. However, they provide no distinctive support for the decision maker.

Many studies choose a nonlinear model (QP/NLP) as formulation to model current flows with physical precision [12, 18, 42, 49, 62, 63]. A nonlinear model formulation results in a high problem complexity [55]. Therefore, heuristic methods are applied predominately to networks with a large number of load nodes. For example, Mendoza et al. [37], Nazar et al. [38] and Ziari et al. [62] use heuristic approaches to evaluate distribution networks with 812, 5000, and 205 load nodes, respectively. In the work in Table 1, exact methods are applied only on smaller networks with 136 load nodes or less [26].

Recent research places various emphases in the area of distribution network optimization (cf. Sect. 2.1). We identify three research gaps that we address in our work: (1) solving large networks with exact optimization methods, (2) integrating the primary and secondary distribution network, and (3) designing flexible topologies for high reliability. (1) The presented studies focus on solving distribution networks with few load nodes exactly or apply heuristic methods when there are many load nodes. However, there are no model formulations that are solved with exact methods for networks with a high number of load nodes. (2) Considering networks with a high number of load nodes is important to also model the secondary network and enable integrated expansion planning. However, the secondary network is predominantly neglected, even though this is just as important for transporting energy to network customers [12, 40]. (3) Previous work has evaluated reliability using costs of undelivered energy. However, no study requires the design of a flexible topology.

To the best of our knowledge, there is no linear formulation that considers the primary and secondary networks in an integrated way, imposes a flexible topology, and can be solved exactly. We wish to extend the research of network optimization and close this research gap by presenting a novel MILP formulation. Our goal is to minimize investment and operation costs of the primary and secondary distribution network using an exact solution approach. In addition to physical requirements, the constraints must also ensure a flexible topology in order to ensure practically applicable results. We want to focus on a static planning horizon; dealing with an uncertain future is still possible by computing multiple future scenarios and consolidating an expansion plan by experts, as shown in other studies.

We create a set of instances with different characteristics to investigate their effects on solvability and execution time. A direct choice of the model’s sets and parameters (cf. Table 3) is not suitable to create realistic distribution networks, since the underlying topology would be disregarded. Similarly, installation costs, utilization limits and other characteristics are dependent on selected line and transformer types. Therefore, we generate realistic distribution networks and describe them with network parameters in Sect. 5.1.1. In Sect. 5.1.2 we describe the correspondence between the network and model parameters.

As emphasized in the introduction, it is particularly important that solutions can be implemented in practice. To ensure the feasibility of solutions in practice, we simulate all solutions using the current flow simulation library pandapower, which is described by Thurner et al. [54]. During simulation, we consider the failure scenarios to verify the reliability of the solution: we successively deactivate the distribution network’s transformers to simulate their failure. In this case, the affected transformer cannot be used, and its load is redistributed to other transformers. Appendix E lists detailed simulation results. Overall, 3476 out of 4050 instances are solved, 3473 of them optimal with a gap of 0.5% or less. The power flow calculation converges for all solutions (\(100.00\%\)). When simulating the 3476 solutions, 0 load capacity violations (\(0.00\%\)) and 53 voltage violations (\(1.52\%\)) were detected. The 3423 successfully simulated networks contain 82,141 transformers, which failures were also simulated. The extended failure simulations detected load capacity violations in one case (\(< 0.01\%\)) and voltage violations in 280 (\(0.34\%\)) cases. These discrepancies can be explained by the fact that the optimization model designs the most cost-effective solution while exploiting the given bounds as much as possible. Since the simulation calculates current and voltage differently, few violations of the given bounds may occur in some cases. They are of no real consequence due to the fact that in practice, a decision maker could adjust the transformer settings, set the bounds for the optimization more narrowly or, if necessary, specifically strengthen the solution obtained at the affected network parts.

In this section, we present the results of our computational experiments. First, we provide an overview of the optimization’s computing time for the instances. Then, we consider the influence of the exogenous network characteristics on the computation time and solution quality using an ordinary least square regression. Finally, we investigate the effect size of the network size on the required computation time using a logistic regression.

Figure 3 presents a cactus plot of the optimization’s computing time (wall time) of the instances. The instances are divided into five groups of 810 instances each, according to their number of buses. The cactus plot provides an overview about how efficiently the instances were solved depending on their number of buses. The x-axis shows the computing time in minutes, while the y-axis indicates the number of instances solved optimally in the respective time. We consider an instance to be solved optimally if its gap is 0.5% or less.

To understand the influence of exogenous network characteristics on computing times and solution quality more precisely, we perform a sensitivity analysis using a logistic and an ordinary least square regression: first, for the logistic regression, we introduce the dependent variable solved, which is 1, if the solver could calculate an optimal solution during the specified solution time, and 0 otherwise. The logistic regression provides insights into which network characteristics caused an instance to be solved to optimality during a specified time window. We use the network characteristics bu, tr, lt and as as independent variables (cf. Table 5) and include the number of lines nl as well as the total demand td of the network. These values correspond with the mathematical model’s sets and parameters as described in Sect. 5.1.2.

To avoid multicollinearities, nl and td are set in relation to the number of buses. The probability of solved given bu, \(\frac{nl}{bu}\), tr, \(\frac{td}{bu}\), lt and as is stated in Equation (16) with \(\sigma (z)=\frac{1}{1+e^{-z}}\) as the sigmoid function:

Table 7 shows the results of the regression. To prevent distortion of the analysis, the instances were checked for outliers according to the Bonferroni correction (error \(< 5\%\)) and no outliers could be detected.

Second, we use 3473 of 4050 instances which could be solved optimally and perform an OLS regression on the logarithmically transformed computing time time as the dependent variable as shown in Eq. (17). Complementary to logistic regression, OLS regression examines the effect size of network characteristics of solved instances on time required. We excluded 11 outliers according to the Bonferroni correction (error \(< 5\%\)) to prevent distortion of the analysis.

Table 8 presents the results of the regression. Since the effect of transformers per 100 buses tr has no statistical significance, we refine the regression analysis and group the instances according to the distribution density of transformers. The regression models generated in this process can be found in Appendix D.¹ Appendix E provides detailed results for every instance.

In this section, we address our research question about how scenario characteristics do affect the model’s computation time. We discuss the results of the computation time analysis, the logistic regression and the OLS regression.

In terms of computation time, Fig. 3 shows that as the instance size increases, the average computation time increases and fewer instances can be solved. At the same time, it demonstrates that other network characteristics are also decisive for computing a solution. Within the given computation time limit and hardware resources, all instances with 1000 buses and almost every (98.3%) instance with 2000 buses were solved optimally. With more buses, the number of optimally solved instances decreases to 77.4% and 60.7% for instances with 4000 and 5000 nodes, respectively. These results indicate that networks with more buses tend to be computationally more challenging. However, looking at instances with a computation time of less than 6 h, some instances with 5000 buses were solved in less time than instances with lower bus count. This means that other characteristics besides the number of buses influence the computational complexity of the model.

We find that the logistic regression results are suitable to guide the decision of whether to consider an instance in a scenario analysis. For example, the decision maker can decide to include an instance that is expected to be solved close to optimality with an expected gap of 0.5% or less. On the other hand, they can decide to omit instances of an insufficiently expected solution quality. The regression results show statistically significant influences on the solvability of an instance for all considered independent variables. To evaluate the model’s quality, we calculated McFadden’s pseudo \(R^2\)-value. Analogous to the \(R^2\)-index in OLS regressions, McFadden’s pseudo \(R^2\) evaluates the predictive capacity of a logistic regression model [53]. A pseudo \(R^2\) of 0.4125 underlines the model’s quality, since values between 0.2 and 0.4 are considered as an indicator of an excellent model fit [34, p.54]. The coefficients of the regression model in Table 7 provide insights into the effects of network characteristics on the probability of obtaining an optimal result within 48 hours. When interpreting the coefficients, they need to be considered as a parameter of the sigmoid function \(\sigma (z)=\frac{1}{1+e^{-z}}\). For example, for a network with \(bu=5000\) buses, \(\frac{nl}{bu}=1\) line per bus, and an action scope of \(as=0.3\), the probability of solving the network within our experimental setting is \(\sigma (35.2395-0.002\cdot 5000 -17.811\cdot 1.0-19.5555\cdot 0.3)\approx 0.83\) (irrespective of the other network characteristics). If the number of lines per bus \(\frac{nl}{bu}\) increases to 1.2 or the action space as raises to 0.5, the probability reduces to 0.12 and 0.09, respectively. If both variables increase simultaneously, obtaining a solution is hardly expected with a probability of 0.002. Decreasing the network size to 2000 or 1000 would increase the probability to 0.52 and 0.89, respectively, and allows consideration of high line density and action scope again. This behavior can be explained by the fact that with a smaller number of lines, there are fewer options for reliably routing the current flows through the network. Similarly, a smaller action scope allows several variables to be fixed beforehand. Conversely, as the number of lines or action scope increases, the size of the solution space increases rapidly, requiring increased computation time and computing resources.

Looking at the OLS regression, we find that the combination of the number of buses bu, lines per bus \(\frac{nl}{bu}\), and the action scope as have a considerable impact on the computation time. The OLS regression in Table 8 evaluates the influence of network characteristics on the expected computation time and finds statistically significant effects. The \(R^2 = 0.773\) indicates, that the regression model explains 77.3% of the variation in the dependent variable [15, p.18]. Its coefficients show the expected logarithmic computation time depending on the variables. Therefore, the actual computation time is obtained by using the exponential function: For example, if we consider a network with \(bu=4000\) buses, \(\frac{nl}{bu}=1\) line per bus, \(tr=1\) transformer per 100 buses, a demand per bus of \(\frac{td}{bu}=0.8\), \(lt=4\) line and transformer types, and an action scope of \(as=0.4\), the expected computation time is \(time=e^{-16.3868+0.0017\cdot 4000+15.4091\cdot 1.0-0.2110\cdot 1.0+0.2621\cdot 0.8+0.1448\cdot 4+1.7801\cdot 0.4}\approx 1227\) s (\(\widehat{=}~0.34~\)h). If the action scope increases by 20% to \(as=0.6\), the expected computation time increases by a factor of 1.15 (\(time \approx 1415\) s \(\widehat{=}~0.39\) h). An increase of the number of buses bu to 4800 results in an increase of the computation time to a total of \(time=4780\) s (\(\widehat{=}~51.33\) h, an increase by the factor of 3.9). An increase of the lines per bus by 20% to \(\frac{nl}{bu}=1.2\) leads to an expected computation time of 26,743 s (\(\widehat{=}~7.42\) h, an increase by the factor of 21.8). Thus, the example illustrates that the choice and combination of individual parameters can greatly change the computation time. The increase in line and transformer types have only a weak effect on the computation time due to a small effect size and a low coefficient, which is why we do not go into detail on this network characteristic. We also neglect the density of the transformers and the load per bus due to their weak significance. The results confirm the logistic regression in the sense that the lines per bus, number of buses, number of lines and transformer types as well as the action space influence the optimization model’s complexity. However, for the share of transformers in the network and the load per bus, the OLS regression confirms only weakly significant influences.

Since the value \(P>|t|\) is least significant for transformers, we divided the data into instances with low, medium, and high density of transformers in the network and created three additional OLS regression models, which are presented in detail in Appendix D. These regression models show that no statistical significance can be found for the action scope when focusing on low transformer density (\(tr\le 0.9\)), while this feature significantly affects the computation time for instances with high density of transformers (\(tr>1.1\)). The opposite is found for the variable of the load per node, which is only weakly significant at low transformer densities and not significant otherwise. Compared to the OLS regression in Table 8, the coefficients reveal a higher effect size of the action scope (3.7135) and lines per bus (16.2187). The coefficients of the other variables do not change or show weaker effects. Overall, the results complement the logistic regression findings and provide further insight into the impact of individual network characteristics on computation time. Due to the high quality of the models and the statistical significance of their variables, we derive implications for practitioners in the following section.

Our optimization model enables practitioners to calculate optimal distribution networks that can be deployed in practice. The results of our computational experiments provide important insights into the design of scenario analyses for distribution network planning. The implications are summarized in Table 9 and discussed in this section.

We find that decomposition should divide distribution networks into small contiguous areas (cf. Implication P1). When infrastructure planners use decomposition techniques, they are guided by geographical contexts, e.g., cities, city districts or neighborhoods. Although the regression results for the number of buses show the smallest coefficients (0.0017), due to the large effect sizes with up to 5000 buses, this network characteristic has a considerable influence on the computation time. Figure 3 additionally illustrates the increase in complexity and shows that with increasing network size, fewer instances were solved to optimality. We recommend infrastructure planners to decompose the networks as far as possible into city districts or neighborhoods. These small, but connected network areas have the advantage that the complexity is kept low without neglecting dependencies and synergy effects between neighboring distribution areas of different transformers.

We find that the action scope has a great influence on the solvability of the distribution network’s model (cf. Implication P2). When infrastructure planners consider a scenario, they have to determine an action scope, which means that they need to decide which assets will be subject of expansion planning. Typically, ailing lines have to be replaced, while recent purchases are still being written off and therefore remain unchanged. For other assets, the infrastructure planners are free to decide whether they should be part of the action scope. According to the results, the action scope has the greatest influence on the solvability of a scenario. If the expected solvability is too improbable, we recommend reducing the scope of action if possible.

We find that the ratio of lines to buses is significant for the computation time and has the greatest influence on it (cf. Implication P3). For example, increasing the ratio of lines to buses by one percent would increase computation time by almost 17%. An increase in the ratio of 10% would result in an increase in computation time of almost 470%. Due to the strong effect size, the necessary computation time can quickly exceed the time budget. Since the lines per bus are given exogenously, the infrastructure planner cannot reduce the number of lines per bus. To avoid an unacceptably high computation time in case of a too high density of lines, infrastructure planners may choose a suitable decomposition or an appropriate scope for action (cf. Implications P1 and P2).

We find that a higher number of alternatives for transformers had a reciprocal relationship between the number of transformers and the expected solvability or computation time of the model (cf. Implication P4). Contrary to the expectation that an increase in the number of alternatives for transformers and the accompanying increase in the solution space create a more complex model, it is shown here that additional transformers are conducive to solvability. The foremost cause for this rather contradictory result is likely the fact that additional transformers prevent expensive expansion of the lines, so the solver can exclude uneconomical solutions more quickly. We recommend infrastructure planners to give extensive thought to possible uses for new transformers to benefit from the positive effects mentioned.

We find that the number of asset types and the load per bus is of less importance to ensure solvability or fast computation time (cf. Implication P5). When infrastructure planners consider which asset types for lines and transformers to use in the future, the results of the regression analyzes show that the effect sizes of the bus load and the number of alternatives for asset types have only a minor impact on solvability and computation time. Due to the disproportionately low ratio, it is recommendable to not restrict the number of asset types and bus load in the scenario design to reduce complexity.

This study addresses the challenge of planning future power distribution networks and designing scenario analyses in order to account for informational uncertainties subject to limited planning time and computing resources. We pursue the research question of how scenario characteristics affect the model’s computation time to analyze correlations between parameter values of scenarios with their computation times. Based on requirements from literature and discussions with infrastructure planners, we propose a linear model for the distribution network optimization problem. Using an exact state-of-the-art solver, we conduct extensive computational experiments on distribution network instances based on empirical data, varying several parameters to adjust different network characteristics. We perform a simulative validation to confirm the solution’s applicability in practice. We also examine the influence of network characteristics on the computation time in more detail with a sensitivity analysis. From the results, we derive implications for practitioners to guide them in how to design a scenario analysis with respect to limited time and computing resources. This enables infrastructure planners to consider the uncertain development of the future energy consumption and to determine a cost-effective expansion strategy for their distribution networks.

We are aware of the limitations of our work and advise avenues for future research. As a first research path, we recommend integrating electrical storage systems (ESS) into the model and thereby contribute to identify potentials for smart distribution network expansion. For example, the optimization of distribution networks including ESS is considered in the studies of Asensio et al. [4] or Mariut and Helerea [35]. Since our approach is tailored for German distribution system operators, who are not yet authorized to use flexible assets due to German legislation, we neglected ESS in this study. However, ESS could be integrated as controllable loads in our model with their charging and discharging as a new decision variable. Load losses and voltage behavior would have to be taken into account in the constraints.

A second research path may extend our approach to include planning periods, thus open up the possibility of designing transformation plans for distribution networks in temporal context. The integration of time intervals can be found in the work of Arias et al. [3] or Shen et al. [51]. To model the temporal intervals, the decision variables can be extended by a temporal dimension. Adding another dimension would increase the number of variables and thus the complexity of the model; on the other hand, adding another dimension could result in a better handling of the uncertain future: Considering planning periods, a rolling horizon approach could be applied so that the optimization problem is solved for a specified forecast period and a solution is implemented. A new optimization for the subsequent planning period can then be performed at a later point in time with adjusted demands based on better knowledge about the change in load demand.

A third research path may deal with the computing resources to be used. From an experimental point of view, our study was limited to the effects of network characteristics. Supplementary, further research can determine how varying computational resources, e.g., memory and threads, affect the solver’s performance. This approach would extend our computational experiments by varying not only the network characteristics, but also the resources available. An evaluation of solution times as well as solution quality in dependence on the computational resources could provide further information about which requirements should be placed on systems in order not to acquire expensive resources unnecessarily.

A fourth research path could shed light on the nonlinear current behavior. While we formulated a linear model and simulatively validated our results for it, other researchers like Wang et al. [56] or Aldarajee et al. [2] formulate nonlinear models. The nonlinear consideration accurately maps the current behavior, but worsens the performance of the solution calculation. More in-depth experiments can address the question to what extent the optimum of the linear model formulation deviates from the optimum of the nonlinear one and whether consequences for the decision recommendation arise from this.

Finally, as a fifth research path, our results should be further analyzed with real distribution networks. For example, in the work of Bagheri et al. [5] and Paiva et al. [40], a real distribution network is used for evaluation. In a case study, our approach could be used to analyze how an infrastructure decomposition can be used to enforce large distribution networks in a cost-minimizing way to meet the future needs. These insights can guide infrastructure planners on how to decompose their networks to enable coherent planning of different sub-networks that, when combined, represent the entire service area.