1 Introduction

The distribution system expansion planning (DSEP), is a topic widely detailed in the specialized literature, whose aims is propose the better expansion plan of the network to minimize the investment and operational cost, that satisfy the physical and operational constraints of the electrical system over the planning horizon [1]. The expansion plan determines the line routes and conductor type for circuits, the substations to be reinforced and those to be constructed, and the additional equipments required for proper operation [2]. The physical constrains of the distribution system are the Kirchhoff’s voltage and current laws, and the technical constraints such as bus voltage limits, line current-carrying capacity, power output in substations and the radial operate of the network.

The DSEP is a mixed-integer nonlinear optimization problem in which integer variables represent the decision in equipments for the network, and the continuous variables represents the operating state of the system [3]. Thus, with the passing of years several deterministic formulations and solution techniques to solve the DSEP has been presented, and the complexity of these formulations and techniques has been increasing in line with the computational resources. Several formulations using mixed-integer linear programming (MILP) has been used for the DSEP problem [4,5,6,7,8,9,10]. In other way, the mixed-integer quadratic programming (MIQP) has been less explored, being relevant exceptions [11,12,13].

In [11] firstly, a quadratic programming is solved treating all variables as continuous variables. Then, the values of integer variables are converted into integer values using round estimation. In [12] the author presented a conic programming model for the DSEP problem, for two formulations with single and parallel-circuit equivalent, besides of proposing a set of polyhedral constraints to reduce the computational effort. In [13] a mixed-integer quadratically-constraint (MIQC) model is presented. The formulations in [12] and [13] consider installation and reinforcement of substations, line routes and conductor type for circuits, and capacitor banks installation in a static planning.

An exact DSEP model considers nonlinear equations for a power flow constraints. In this way, meta-heuristic optimization techniques are a powerful alternative to solve large scale problems with nonlinear constraints like DSEP. To solve the DSEP problem by a nonlinear variable cost, genetics algorithm (GA) was used in [14], tabu search (TS) in [15], an ant colony in [16] and simulated annealing in [17]. Some researchers especially worked toward enhancing the computational efficiency of solution methodology or the problem modeling. A relevant approach is presented in [18], sensitivity indexes were used to develop a constructive heuristic algorithm for lines or substations allocation. These sensitivity indexes were calculated by solving a relaxed nonlinear optimization problem.

The reliability of the system is considered as multi-objective approach for the DSEP problem with meta-heuristics techniques to obtain a Pareto front that consider the investment costs and the reliability as two separate objectives [19,20,21]. Evolutionary algorithm is used in [19] incorporating system failure index. In [20] a multi-objective particle swarm optimization (PSO) incorporating distributed generation (DG) is used. A multi-objective TS using dynamic programming is presented in [21].

The aforementioned works did not consider the uncertainly behavior of the distribution systems, and only one operational condition were considered. Power system planners and operators show growing interests in the installation of DG taking into account uncertainty and the correlation with the electrical system to make better decisions for planning and operating problems [22,23,24,25,26].

In [23] the uncertainty in load and conventional DG is approach as multiple scenarios. Trough AG, the optimization process presents one expansion plan for each individual scenario considered. Then, a heuristic decision-making is used to select a unique expansion plan.

The installation of DG with renewable energy sources can have a significant impact on the network behavior, although the level of uncertainty in the behavior of the system increases. Scenario based approach is a simple and efficient tool to consider these. In [24], the author develops a scenario reduction technique using historical data of load and wind speed in time blocks to consider their uncertainty and correlation for the installation of wind turbines.

Recently various approaches and models for the DSEP problem have been developed to consider the uncertainty load behavior and the renewable energy, the elements of an efficient design, more economically operate a power system, and the fact of having power generation near to the operational limits [25, 26]. The authors in [25] proposed a stochastic two-stage and multi-period MILP model for optimal allocation and timing of renewable wind and solar DG and substation reinforced under uncertainty. These approach uses linearized power flow equations. A multi-period DSEP model with wind and solar DG have been developed in [26], using an iterative algorithm and stochastic scenario based in a MILP model to obtain a pool of hight-quality expansion plans. Subsequently, a reliability analysis for indices and cost is performed for each one solution proposed.

In this paper the DSEP model considers: (a) installing new substations and/or resizing the existing ones, (b) build branches for new bus loads and/or resizing the existing feeders, and (c) installation wind turbines in the candidate buses. A MICP model and a meta-heuristic optimization technique, TS, that uses a stochastic conic programming (SCP) as auxiliary technique, are used to solve the DSEP with uncertainty in the load, and wind speed behavior. Thus, a two-stage stochastic programming model is used to incorporate this uncertainty and represent the operational state of a radial distribution system. The MICP is a convex formulation that can find the global solution using optimization solvers. The TS technique allows the separation of integer and continuous variables, enabling the use of a solver for calculating the operational state of the system, while the integer variables are fixed. Comparing with the formulations proposed in [12] and [13], our proposed model considers DG installation with wind technology using stochastic scenario based programming. Unlike the works above, this paper does not use linear programming; it combines the strength of TS algorithm and an efficient solver to decompose the problem and obtain a good solution of MICP with a higher computational efficiency.

The main contributions of this paper are as follows:

  • Using a two-stage stochastic programming model scenario based to consider the uncertain and correlation between behaviors of load and wind speed in a MICP model for the DSEP problem. This model guarantees the global solution using optimization solvers or classical optimization techniques.

  • Joint a meta-heuristic technique with a commercial optimization solver to address a mixed-integer stochastic programming problem related to DSEP and compare the computational performance, solution quality, and robustness of the solutions obtained by meta-heuristic technique and the solution obtained for the MICP model through commercial optimization solver.

The rest of this paper are organized as follows. In Sect. 2 the wind turbine and the uncertainty models are characterized. Section 3 presents the mathematical model as optimization problem with objective function and constraints for the DSEP problem. In Sect. 4, the adapted meta-heuristic technique tabu search for DSEP problem is presented. Numerical studies and results are reported in Sect. 5. In Sect. 6, the discussion and comments are presented. Section 7 presents the concluding remarks.

2 Model development hypothesis

In this section, the hypotheses to develop the mathematical model for the DSEP problem are presented.

2.1 Wind power model

The wind energy production technologies transform the energy in the wind to produce electrical power. This methodology is usually a linear approximation of the wind energy curve of the turbine [25].

$$\begin{aligned} P^{W}= \left\{ \begin{array}{lll} 0, &{} \quad v< v_I \\ \\ \frac{P_R}{v_R - v_I}v + P_{R}(1-\frac{v_{R}}{v_{R}-v_{I}}), &{} \quad v_{I} \le v< v_{R} \\ \\ P_{R}, &{} \quad v_{R} \le v < v_{0} \\ 0, &{} \quad v \ge v_{0} \end{array} \right. \end{aligned}$$
(1)

where \(P^{W}\) is the output power of the wind turbine (kW); \(P_R\) is the rated electrical power (kW); v is the wind speed in (m/s); \(v_R\) is the rated wind speed in (m/s).; \(v_I\) is the cut-in wind speed in (m/s); and \(v_0\) is the cut-off wind speed in (m/s). This approach is used to calculate the wind power output factor levels \(f_W^{b}\).

2.2 Uncertainty model

The uncertainty in the behavior of the electric load has a great impact on the operating costs of the system, and consequently, on the decisions to be made in expansion plan. The output power by a wind turbine in a particular zone is subject to uncertainties, so a modeling in which the wind conditions are considered is necessary. To consider that, uncertainty model based on duration curves in which the stochasticity of electrical loads, wind speeds, and their correlations is considered. A stochastic set of scenarios can be used to describe the uncertainty and correlation between those variables [24].

Electric load and wind speed are estimated in blocks of time and levels for one year. This year is divided into pre-specifics segments to represent the system behavior [10]. The load and wind speed scenario contains information pairs \((\mu _D^b , \pi _D^b\)), \((\mu _W^b , \pi _W^b)\) of the average levels and their correspondent probabilities for the block of time b. Thus, each of the combined set of scenarios \(\varOmega _{d}^w\) are created as the combination of load and wind average scenarios that have the same time block, like this: \(\varOmega _{d}^w\) = (\(\varOmega _{d}^b\),\(\varOmega _{w}^b\)) \( \forall \) \((b \in \varOmega _{b})\). The probability \(\pi _\omega \) of scenario is calculated as a product of the probabilities like this: \(\pi _\omega =\pi _D^b\pi _W^b\). The correspondents average wind speeds \(\mu _W^b\) are converted into factor levels of power generation limits \(f_W^{b}\), depending on the turbine characteristics. Finally, the load factor levels \(f_\omega ^d\) and the wind output power factor levels \(f_\omega ^{wd}\) of each scenario are equal to correspondent average load levels \(\mu _D^b\) and wind output power factor levels \(f_W^{b}\).

2.3 Two-stage stochastic programming

A deterministic optimization model considers that there exists perfect information in the system data. Electric loads and wind speeds have a behavior that is not correct to be considered as deterministic. In order to incorporate them more correctly into the DSEP model, a two-stage stochastic programming model is used [27]. In the first stage, the decisions are made before the realization of the stochastic process. This stage determines the investment actions for substations, branches, and wind generators. In the second stage, the operational expected value of the system is calculated, when the scenarios and investment actions are known.

Figure 1 shows that how the investment action decisions of the first stage cover all operating scenarios \(\omega _n\) in the second stage.

Fig. 1
figure 1

Uncertainty tree

Full size image

3 Mixed integer conic programming model

The objective function (OF) (2) determines the investment cost and the operational expected value of the system. The investment cost contains the installation and resizing of circuits, build and resizing of substations, and the installation of wind-distributed generation based. The operational cost considers the power purchase in market and maintenance and operation of the wind generator installed in the system. In this approach, the wind turbines are owned by distribution company. Therefore it is possible to select a set of candidate buses for their installation.

3.1 Objective Function

$$\begin{aligned} \min { OF}= { CL} + { CSS} + { CWG} +\sum _{ \omega \in \varOmega _{d}^w}\pi _{\omega }( { OPCSS}_{\omega } + { OPCWG}_{\omega }) \end{aligned}$$
(2)

where: CL—investment cost of branch:

$$\begin{aligned} { CL}=\sum _{l\in \varOmega _{l}}\sum _{a\in \varOmega _{a}} k_{l,a}C_{a_0^l,a}^{l}L_{l} \end{aligned}$$
(3)

CSS—Investment cost of substations:

$$\begin{aligned} { CSS} = \sum _{s\in \varOmega _{ se}}\sum _{h \in 1..Tm_{s}}x_{s,h}hC_{s}^{se} \end{aligned}$$
(4)

CWG—Investment cost of wind generator:

$$\begin{aligned} { CWG} = \sum _{g\in \varOmega _{g}}y_{g}C^{g} \end{aligned}$$
(5)

OPCSS—Operating cost of the substations:

$$\begin{aligned} { OPCSS}_{\omega }= \sum _{s \in \varOmega _{s}}C^{e}_{\omega }T_{b}f(\tau ,\lambda )P_{s,\omega }^{SS} \;\;\forall (\omega ) \end{aligned}$$
(6)

OPCWG—Operating cost of the wind power generation:

$$\begin{aligned} { OPCWG}_{\omega }= \sum _{g \in \varOmega _{g}}C^{g}_{\omega }T_{b}f(\tau ,\lambda )P_{g,\omega }^{WD} \;\; \forall (\omega ) \end{aligned}$$
(7)

The annualized present value for operational cost, as a function of the interest rate \(\tau \) and the planning horizon in years \(\lambda \) (8).

$$\begin{aligned} f(\tau ,\lambda )=\frac{1-(1+\tau )^{-\lambda }}{\tau } \end{aligned}$$
(8)

3.2 Constraints

The physical and operational constraints should be considered in the mathematical model to guarantee a proper operational condition during the planning horizon.

3.2.1 Active and reactive power injection

Constraints (9) and (10) based on [28] stand for the active and reactive power balance respectively, and should be considered in each scenario.

$$\begin{aligned} \sum _{j\in N(i)}P_{ij,\omega }= & {} P_{i,\omega }^{SS} +P_{i,\omega }^{WD}-f_\omega ^d P_{i}^{D} \;\;\forall (i,\omega ) \end{aligned}$$
(9)
$$\begin{aligned} \sum _{j\in N(i)}Q_{ij,\omega }= & {} Q_{i,\omega }^{SS} +Q_{i,\omega }^{WD} -f_\omega ^d Q_{i}^{D}\;\;\forall (i,\omega ) \end{aligned}$$
(10)

where

$$\begin{aligned} P_{ij,\omega }= & {} \sum _{a \in \varOmega _{a}} (\sqrt{2}u_{i,a,\omega }^{l}g_{ij,a}-R_{ij,a,\omega }g_{ij,a}-T_{ij,a,\omega }b_{ij,a})\;\;\; \forall (ij,\omega ) \end{aligned}$$
(11)
$$\begin{aligned} Q_{ij,\omega }= & {} \sum _{a \in \varOmega _{a} } (-\sqrt{2}u_{i,a,\omega }^{l}b_{ij,a}+R_{ij,a,\omega }b_{ij,a}-T_{ij,a,\omega }g_{ij,a,\omega }) \;\;\; \forall (ij,\omega ) \end{aligned}$$
(12)

3.2.2 Power output of wind turbines

Equations (13) and (14) present the operational limits of the active and reactive powers injected in the buses by installed wind turbines.

$$\begin{aligned} 0 \le P_{g,\omega }^{WD}\le & {} f_{\omega }^{wd}\overline{P^{wd}}y_{g} \;\; \forall (g,\omega ) \end{aligned}$$
(13)
$$\begin{aligned} 0 \le Q_{g,\omega }^{WD}\le & {} P_{g,\omega }^{WD}\tan (\varphi ^{wd}) \;\; \forall (g,\omega ) \end{aligned}$$
(14)

3.2.3 Maximum permissible line current carrying capacity

Equation (15) stands for the operational current limit of the branches according to the installed conductor type .

$$\begin{aligned}&\sqrt{2}A_{ij,a}u_{i,a,\omega }^l+\sqrt{2}B_{ij,a}u_{j,a,\omega }^l \nonumber \\&\quad -2C_{ij,a}R_{ij,a,\omega }+2D_{ij,a}T_{ij,a,\omega } \le \overline{I}_{ij,a}^2 \quad \forall (ij, a, \omega ) \end{aligned}$$
(15)

where

$$\begin{aligned} A_{ij,a}= & {} g_{ij,a}^2+(b_{ij,a}+b_{ij,a}^{sh}/2)^2 \end{aligned}$$
(16)
$$\begin{aligned} B_{ij,a}= & {} g_{ij,a}^2+b_{ij,a}^2 \end{aligned}$$
(17)
$$\begin{aligned} C_{ij,a}= & {} g_{ij,c}^2+b_{ij,a}(b_{ij,a}+b_{ij,a}^{sh}/2) \end{aligned}$$
(18)
$$\begin{aligned} D_{ij,a}= & {} g_{ij,a}b_{ij,a}^{sh}/2 \quad \forall (ij,a) \end{aligned}$$
(19)

3.2.4 Voltage magnitudes limits

The upper and lower voltage magnitude are presented by constraints (20) and (21) where \(u_{i,a,\omega }^l\) and \(u_{j,a,\omega }^l\) are defined in each distinct branch l and conductor type a to represent the voltage in bus i, j and operating scenario \(\omega \).

$$\begin{aligned}&\frac{\underline{V}_{i}^2}{\sqrt{2}} k_{l,a}\le u_{i,a,\omega }^l \le \frac{\overline{V}_{i}^2}{\sqrt{2}} k_{l,a} \;\;\forall (a,l,\omega ) \end{aligned}$$
(20)
$$\begin{aligned}&\frac{\underline{{V}}_{j}^2}{\sqrt{2}} k_{l,a}\le u_{j,a,\omega }^l \le \frac{\overline{V}_{j}^2}{\sqrt{2}} k_{l,a} \;\;\forall (a,l,\omega ) \end{aligned}$$
(21)

Equations (22) and (23) limit the variable \(\delta _{i,\omega }^{l}\) in terms of the operational state of the branch l. The fictitious voltage variable \(\delta _{i,\omega }^l\) is used to maintain the feasibility of the problem when there is no installed circuit in the branch l. That is, if the branch l is connected, then \(\delta _{i,\omega }^{l}=0\) and \(\delta _{j,\omega }^{l}=0\), otherwise, \(\delta _{i,\omega }^{l}\) and \(\delta _{j,\omega }^{l}\) are limited according to the bus maximum voltage.

$$\begin{aligned}&\vert \delta _{i,\omega }^{l}\vert \le \frac{\overline{V}_{i}^{2}}{\sqrt{2}}(1-\sum _{a \in \varOmega _{a}}k_{l,a}) \;\;\; \forall (a,l,\omega ) \end{aligned}$$
(22)
$$\begin{aligned}&\sum _{a \in \varOmega _{a}}u_{i,a,\omega }^{l_{x}}-\sum _{a \in \varOmega _{a}}u_{i,a,\omega }^{l_{y}}+\delta _{i,\omega }^{l_{x}}-\delta _{i,\omega }^{l_{y}}=0\nonumber \\&\quad \forall (l_{x,y}\in \varOmega _{l}, \omega ) \end{aligned}$$
(23)

3.2.5 Operational limits of power supplied by the substations

The operational limit of supplied power by a substations is presented in (24). This constraint depends on the installed capacity in each substation.

$$\begin{aligned} (S_{s}^{o})^2 + 2S_{s}^{o}Sa_{s} +Sa_{s}^{sqr} \ge (P_{s,\omega }^{SS})^2+(Q_{s,\omega }^{SS})^2 \;\; \forall (s,\omega ). \end{aligned}$$
(24)

The number of transformers in parallel to be installed in the substations is a particular constraint of each bus \(s \in \varOmega _s\). This depends on the physical space available at the substation. The binary variable \( x_{s, h} \), is a vector of dimension h, whose positions indicate a number of transformers to be installed in substation s. By the constraint (27) only one of those positions can be considered.

$$\begin{aligned}&Sa_{s} = \sum _{h \in 1..Tm_{s}}x_{s,h}h S_{s^{'}} \;\;\;\forall (s) \end{aligned}$$
(25)
$$\begin{aligned}&Sa_{s}^{sqr} = \sum _{h \in 1..Tm_{s}}x_{s,h}h^2 S_{s^{'}}^{2} \;\;\;\forall (s) \end{aligned}$$
(26)
$$\begin{aligned}&\sum _{h \in 1..Tm_{s}}x_{s,h}\le 1 \;\;\;\forall (s). \end{aligned}$$
(27)

3.2.6 Conic rotation

The conic rotated constraints [28] relate the variables \(u_{i,a,\omega }^l\), \(u_{j,a,\omega }^l\), \(R_{ij,a,\omega }\) and \(T_{ij,a,\omega }\) on the power flow Eqs. (9) and (10).

$$\begin{aligned}&2u_{i,a,\omega }^lu_{j,a,\omega }^l\ge R_{ij,a,\omega }^2+T_{ij,a,\omega }^2 \;\; \forall (l,a,\omega ) \end{aligned}$$
(28)
$$\begin{aligned}&R_{ij,a,\omega }=R_{ji,a,\omega },\;\;\; R_{ij,a,\omega }\ge 0 \;\; \forall (ij,a,\omega ) \end{aligned}$$
(29)
$$\begin{aligned}&T_{ij,a,\omega }=-T_{ji,a,\omega } \;\; \forall (ij,a,\omega ). \end{aligned}$$
(30)

where \(R_{ij,a,\omega }\) and \(T_{ij,a,\omega }\) are subject to the operational state of network stand for the sin and cos functions existed in the traditional power flow equations and must be fulfilled for each branch; (31) and (32) present the limits of \(R_{ij,a,\omega }\) and \(T_{ij,a,\omega }\), the maximum voltage drop in the branch ij.

$$\begin{aligned} R_{ij,a,\omega }\le & {} \overline{V}_{i}\overline{V}_{j}k_{l,a}, \;\; \forall (ij,a,\omega ) \end{aligned}$$
(31)
$$\begin{aligned} \vert T_{ij,a,\omega } \vert\le & {} \overline{V}_{i}\overline{V}_{j}k_{l,a}\;\; \forall (ij,a,\omega ) \end{aligned}$$
(32)

In the DSEP problem, the radial nature of the distribution system should be preserved. Constraints (33)–(35) represent this problem like a spanning tree by introducing the binary variables \(\beta _{ij}\) and \(\beta _{ji}\) corresponding to each branch operating in the system

[29] while (35) guarantee the non-connection between substations buses s.

$$\begin{aligned}&\beta _{ij}+\beta _{ji} = \sum _{a \in \varOmega _{a}}k_{l,a}, \;\;\;\; \forall (ij) \end{aligned}$$
(33)
$$\begin{aligned}&\sum _{ij \in \varOmega _{l}}\beta _{ij} + \sum _{ji \in \varOmega _{l}}\beta _{ij} =1, \;\;\;\; \forall (i) \end{aligned}$$
(34)
$$\begin{aligned}&\beta _{sj} = 0, \;\;\;\; \forall (s, j \in N(s)) \end{aligned}$$
(35)

4 Solution technique

The two-stage stochastic MICP model shown in (2)–(35) is solved using two methodologies: (a) Through the CPLEX preprocessing and processing routines that directly solve mixed-integer conic problems; and (b) The problem is decomposed by relaxing the integrality condition of the variables, transforming the problem (2)–(35) into a CSP (36)–(47). The decision variables are the planning variables and represent the possible topologies of the distribution network; network which are determined through the TS metaheuristic. According to Fig. 2, for each investment proposal obtained by the TS algorithm, its quality is determined by solving the CSP problem.

Fig. 2
figure 2

Solution technique flowchart

Full size image

4.1 Tabu search

Meta-heuristic techniques are powerful tools for solving large-scale problems such as DSEP. The TS method consists in finding solutions through a repeating neighborhood search from a current solution [30]. This characteristic is adequate to preserve the radial nature of the network, and the non-connection between substations.

The initial solution is generated from a constructive heuristic, which consist of two stages. In the first stage, a random configuration for substations with the capacity to attend the full demand of the system is assigned. After construction of substations, in the second stage, the load nodes considering the radial configuration constraint are connected.

TS is a powerful technique to solve combinatorial problems, and their efficiency depends on the neighborhood criteria. These neighborhood criteria of the TS are adapted for the DSEP and defined by:

  1. i.

    Expansion of substation through repowering; only if the candidate substation has power reserve.

  2. ii.

    Constructing new substations; this neighborhood entails the construction of feeders connected to the new substation maintaining the radial nature of the system.

  3. iii.

    Exchanging conductor size of existing branches.

  4. iv.

    Disconnection or construction of new branches; considering the radial configuration of the obtained topology.

  5. v.

    Installation of DG in candidate buses.

The codification system, shown in Fig. 3, is easily adaptable to these neighborhood criteria. Consists of an integer vector divided into three parts. Part I indicates the number of transformers to be installed in the candidate buses s to install substations. Part II determines the operating state and the conductor type to use in the branch l. Part III indicates a binary to know which candidate buses g are selected to install a wind turbine.

Fig. 3
figure 3

Codification system

Full size image

The proposed methodology uses the codification vector to define the first stage of the stochastic programming problem by fixing the whole integer decision variables related to the investment in substations, branches, and wind turbines. In order to calculate the stochastic variables in the second stage, a SCP tool is used. Thus, a modification of the conic optimal power flow (COPF) proposed in [28] is implemented, with the inclusion of load and wind generation scenarios. The SCP model is shown by (36)–(47).

$$\begin{aligned} \min Z= & {} \sum _{ \omega \in \varOmega _{d}^w}\pi _{\omega }({ COPSE}_{\omega } + { COPGD}_{\omega }) \end{aligned}$$
(36)
$$\begin{aligned} \sum _{j\in N(i)}P_{ij,\omega }= & {} P_{i,\omega }^{SS} + P_{i,\omega }^{WD} -f_{\omega }^{d} P_{i}^{D} \;\;\forall (i,\omega ) \end{aligned}$$
(37)
$$\begin{aligned} \sum _{j\in N(i)}Q_{ij,\omega }= & {} Q_{i,\omega }^{SS} + Q_{i,\omega }^{WD}-f_{\omega }^{d}Q_{i,}^{D}\;\;\forall (i,\omega ) \end{aligned}$$
(38)
$$\begin{aligned} -\sum _{j \in N(i)}P_{ij,\omega }= & {} -\sqrt{2}u_{i,\omega }\sum _{j\in N(i)}G_{ij}+\sum _{j \in N(i)}(G_{ij}R_{ij,\omega }-B_{ij}T_{ij,\omega })\nonumber \\&\quad \forall (ij,\omega ) \end{aligned}$$
(39)
$$\begin{aligned} -\sum _{j \in N(i)}Q_{ij,\omega }= & {} -\sqrt{2}u_{i,\omega }\sum _{j\in N(i)}B_{ij}+\sum _{j \in N(i)}(B_{ij}R_{ij,\omega }+G_{ij}T_{ij,\omega }) \nonumber \\&\quad \forall (ij,\omega ) \end{aligned}$$
(40)
$$\begin{aligned} 2u_{i,\omega }u_{j,\omega }\ge & {} R_{ij,\omega }^2+T_{ij,\omega }^2 \;\; \forall (ij,\omega ) \end{aligned}$$
(41)
$$\begin{aligned} R_{ij,\omega }= & {} R_{ji,\omega } \;\;\; \forall (ij,\omega ) \end{aligned}$$
(42)
$$\begin{aligned} T_{ij,\omega }= & {} -T_{ji,\omega } \;\; \forall (ij,\omega ) \end{aligned}$$
(43)
$$\begin{aligned} 0 \le R_{ij,\omega }\le & {} \overline{V}_{i}\overline{V}_{j} \;\;\; \forall (ij,\omega ) \end{aligned}$$
(44)
$$\begin{aligned} \vert T_{ij,\omega } \vert\le & {} \overline{V}_{i}\overline{V}_{j}\;\; \forall (ij,\omega ) \end{aligned}$$
(45)
$$\begin{aligned} 0\le & {} P_{g,\omega }^{WD} \le f_{\omega }^{wd}\overline{P^{wd}} \;\; \forall (g,\omega ) \end{aligned}$$
(46)
$$\begin{aligned} 0\le & {} Q_{g,\omega }^{WD} \le P_{g,\omega }^{WD}\tan (\varphi ^{wd}) \;\; \forall (g,\omega ) \end{aligned}$$
(47)

The used codification system is convenient to represent a solution for the DSEP problem. Note that integer variables and index of conductor type are removed from the formulation, and the variables \(u_{i,\omega }\) and \(u_{j,\omega }\) do not need the index l. Equations (46), (47) only can be considered for buses with an installed wind turbine.

The characteristic to explore in the infeasible region of the search space allows greater efficiency in the process. Constraints regard to the current limits in conductors, voltage regulation, the maximum capacity of the substations are considered by TS via penalty factors in the OF of DSEP. Equation (48) shows the fitness function for DSEP.

$$\begin{aligned} \min {{ OF}}= & {} \{{ CL} + { CSE} + { CGW}S \nonumber \\&+\sum _{ \omega \in \varOmega _{d}^w}\pi _{\omega }( { COPSE}_{\omega } + { COPGD}_{\omega }) \nonumber \\&+Pi+Pv+Pse \} \end{aligned}$$
(48)

After the evaluation of a neighbor configuration, the operational conditions are verified with the operative limits. Thus, if an operational limit is violated the respective penalty is activated to quantify the violation. The TS convergence criterion is a maximum number of iterations without a worthless update of the OF incumbent.

5 Results

A modified 24-node system, derived from [9], is used to show the performance of the proposed formulation and methodology. The system consists of 20 load buses with a constant power behavior, 4 substations operating at 20 kV, and 34 branches. Two types of conductors are considered for branches. Only two wind generators with capacity 3 MVA and installation cost kUS$100 can be installed in the system. The parameters of the wind turbine are \(v_I\) = 3.5 m/s, \(v_R\) = 15 m/s, \(v_0\) = 25 m/s. The planning horizon is 15 years. The upper and lower voltage limits are 1.00 and 0.95 p.u., respectively. The annual interest rate for operating costs is 10%. The price per purchase of energy in the substation is 0.1 US$/kWh, the operation cost of DG is 0.04 US$/kWh, and the system power factor is set to 0.9 and 0.9 for DGs.

The system before planning is illustrated in the Fig. 4, in which the continuous rectangles denotes existing substations, the dashed rectangles denotes candidates for new substations, the continuous lines denote the existent topology, and the dashed lines denote candidate branches for new circuits. Table 1 presents the load in each bus to the system. Table 2 shows all the branches data including the length and the initial conductor type for each branch. In the initial system, buses 21 and 22 are existent substation that can be expanded. Table 3 presents the investment alternatives for substations. Table 4 shows the alternatives for conductor types. Buses 5, 9, 15, 16 are candidates to install a wind turbine. The stochastic scenarios are shown in the Table 5 considering four blocks of time, three loads, and wind power factors levels for a maximum level of wind speed of 17.08 (m/s) based on [26]. All levels within a same block of time are defined with a probability of 1/3.

The MICP model is solved using CPLEX 12.7.1 [31] under \(\hbox {C}^{++}\), and the relative MIP gap is 0.01%. For the second part, the TS algorithm is implemented in \(\hbox {C}^{++}\) to fix the integer variables, and then calculating of the SCP for stochastic variables is solved using CPLEX 12.7.1 in each iteration. The characteristics of the computer used are as follows: 4 processors XEON E7 4807 1.86  GHz and 125 GB of memory.

This system is tested under two conditions. Case 1 Without considering the installation of DG. Case 2 Considering the installation of DG.

Fig. 4
figure 4

24-bar system

Full size image
Table 1 Load data (kVA)
Full size table
Table 2 Branch data
Full size table
Table 3 Substations data
Full size table
Table 4 Conductor data
Full size table
Table 5 Load, wind power factor per time block data
Full size table

5.1 Mixed integer conic programming

The proposed model is adaptable with pre-solving and solving steps of the commercial solver CPLEX. In the CPLEX solver, the pre-solve step is used to reduce the size of the problem and improve the formulation via pre-processing and probing techniques, which rely mainly on the model’s simplicity. During pre-processing, the identification of infeasibility, identification of redundancy, improving the bounds, and rounding (for MIP) is considered while in probing, fixing the variables, improving the coefficients and the logical implications are taken into account [32].

5.2 Case 1: without considering the installation of DG

For this case, 4 blocks of time and 3 load levels are considered, that accounts for 12 scenarios. Hence, the weight of each scenario is 1/3. The optimization model found the first integer feasible solution of US$ 115.113 million in a CPU time about 457 s with an optimality gap of 0.52%. The best obtained solution is US$ 114.685 million within 1631 s with an optimality gap of 0.04% and the process spent 158 s more to reach the 0.01% optimality gap. The investment cost is US$1.393 million and the operating cost is US$ 113.292 million. The results of planning reveal the construction of two new substations in buses 23 and 24 of 17 and 15 MVA, respectively. The circuits need a total investment of US$ 732,513.25. The circuit 1–21 needs to be resized. The circuits 2–12, 4–9, 4–16, 5–24, 7–19, 11–23, 13–20 and 15–17 need to be installed with conductor type c1. The circuits 3–23, 7–23, 10–16, 10–23, 14–18, 17–22, 18–24 and 20–24 need to be installed with conductor type c2. The circuits 2–3, 6–22 and 7–8, are disconnected to the operating state of the system. The optimal expansion plan for the 24-node system with substations size, circuits, and type of conductors is shown in Fig. 5. The proposed solution is a radial distribution system that satisfies the operational constraints in every scenario.

5.3 Case 2: considering the installation of DG

For this case, 4 blocks of time, 3 load levels, and 3 wind power factor are considered, that accounts for 36 scenarios. Hence, the weight of each scenario is 1/9. The optimization model found the first integer feasible solution of US$ 110.231 million in a CPU time about 13,267 s with an optimality gap of 0.47%. The best solution found is US$ 109.930 million within 46,510 s with an optimality gap of 0.04% and the process spent 11,532 s more to reach the 0.01% optimality gap. The investment cost is US$ 1.579 million and the operating cost is US$ 108.351 million. The model proposes the construction of two new substations with the capacity of 17 MVA and 15 MVA in buses 23 and 24, respectively. The circuits need a total investment of US$ 718,499.25. The circuit 1–21 needs to be resized. The circuits 2–12, 4–9, 4–16, 5–24, 7–19, 10–16, 11–23, 13–20 and 15–17 need to be installed with conductor type c1. The circuits 3–23, 7–23, 10–23, 14–18, 17–22, 18–24 and 20–24 need to be installed with conductor type c2. The circuits 2–3, 6–22 and 7–8, are disconnected to the operating state of the system. The installation of two wind turbines is proposed in the buses 9 and 16 with an investment cost of US$ 200.00 million. The optimal expansion plan for the 24-node system with substations size, circuits, type of conductors, and DGs allocation is shown in Fig. 5. The proposed solution is a radial distribution system that satisfies the operational constraints in every scenario.

Fig. 5
figure 5

Proposed solutions

Full size image

5.4 Tabu search

5.5 Case 1: Without considering the installation of DG

The TS algorithm has a satisfactory performance to solve the DSEP problem. The convergence criterion is 15 iterations without an upgrade for the incumbent solution. Starting from a randomize radial solution, the optimization process needed 35 iterations to find a solution of US$ 114.685 million while it required a CPU time of 1008 s to reach the established convergence criterion. The expansion planning proposes the same integer solution as the MICP model for the same case 1. The final topology is radially feasible and does not have operating problems for any scenario.

5.6 Case 2: Considering the installation of DG

The TS algorithm has a satisfactory performance to solve the DSEP problem. Using the integer solution found for TS in the case 1 as the initial point for the optimization process, the algorithm needed 3 iterations to find the solution with a total cost of US$ 109.946 million while it required a CPU time of 1261 s to reach the established convergence criterion in the case 1. The expansion planning proposes the same integer solution as the MICP model for the same case 2. The final topology is radially feasible and does not have operating problems for any scenario.

6 Discussion and comments

Table 6 Results comparison for the test system
Full size table

Table 6 shows a comparison between the MICP model and TS considering the time to reach the stop criterion for each solution technique. As can be seen, the TS algorithm obtains the same integer solution that the MICP model while spending less time in both cases. Although the hybrid MICP model and TS obtain the same integer solution, there exists a small difference in the objective function, that is caused by the precision and parameters used by CPLEX for MICP and conic programming models.

The CPU time solution of the TS in comparison with those of the MICP model are lower in the test cases, this happens both to find the best solution and to reach the stop criterion. In case 2, the increase of the number of scenarios and integer variables has a great effect in the performance of the MICP model.

Although the investment cost in case 2 is higher than the investment cost in case 1, the wind turbines have a significant impact in the system operating cost. A reduction of 4.15% over the total cost of the planning can be expected when added the wind turbines to the distribution system. For this system only the conductor type proposed in the circuit 10–16 is different for both case 1 and case 2.

A COPF is used to evaluate the quality of stochastic solution for each hour to calculate the real operating costs. For case 1, the operating cost is US$ 113.297 million and for case 2 the operating cost is US$ 109.300 million. This result corroborates the quality of the stochastic solution and the used scenarios. Note that the maximum difference between real and stochastic operating costs corresponds to 0.85% of the operating cost for case 2 using MICP. In the DSEP problem, this difference is considered to be acceptable.

7 Conclusions

In this paper a mixed-integer conic programming (MICP) model and a hybrid algorithm Tabu Search (TS) and commercial solver, for solving the distribution system expansion planning (DSEP) problem considering uncertainties in the load and wind speed have been proposed. A stochastic conic programming (SCP) model has been used to handle the load flow problem. In both proposed techniques, the commercial optimization solver CPLEX was used to ensure a reliable response. The proposed MICP model by using either a classical optimization technique or a commercial solver can guarantee to find the global solution of the DSEP, although the computational efficiency of this model is not very high. On the other hand, for the two case studies, the hybrid algorithm finds good feasible solutions in lower CPU times than the commercial solver. In order to incorporate the inherent properties of a distribution system, a two-stage stochastic programming has been used. Stochastic optimization is an appropriate way to represent uncertainties in the system and calculate an operation expected value closer to the reality. Results show that for the test system used, the proposed MICP model can find the optimal global solution in about one day, which is acceptable in planning problems; however, a feasible solution can be found with a commercial solver much faster using a relaxed optimality gap. This shows that when we have enough time for starting a wind-based planning project, which in practice we do, the proposed MICP can make a more precise decision. On the other hand, the TS algorithm, due to the heuristic characteristic may not reach an optimal solution but given the computational efficiency of the TS algorithm for large systems, it can provide an initial solution of excellent quality for the MICP model.