Efficient hybrid algorithm for transmission expansion planning

Abstract

This work presents an efficient hybrid algorithm (EHA) that consists of a search space reducer (SSR) and a modified bat-inspired algorithm (MBA) to solve the transmission network expansion planning (TNEP). The contribution of the proposal is to consider, at the same time, the security constraints criterion ‘N − 1’, load scenarios and network losses to give a more comprehensive approach in an efficient manner, which allows applying the EHA to large-scale real system. Discrete variables in the TNEP are handled by the MBA, and an optimal power flow is used to evaluate the fitness function as well as planning options. By using the SSR to define the initial candidate set for the MBA, the solution search space is reduced improving the computational performance of the proposed MBA. To validate the proposed method and show its efficiency in comparison with others in the literature, tests are conducted on Garver and IEEE 24-bus test system, in addition to an equivalent Brazilian system.

1 Introduction

The goal of the transmission network expansion planning (TNEP) is to determine the optimal number and place of transmission reinforcements that meet the power supply to the consumers during a given horizon, with adequate conditions and at the lowest possible cost.

The classical TNEP optimization problem has the following characteristics: (a) a nonconvex solution space, that is, several solutions, which leads many algorithms to converge toward a local optimal point; (b) combinatorial nature related to the investment alternatives, resulting in a high computational effort; (c) the existence of disconnected electrical systems and isolated buses and (d) the existence of nonlinear constraints and integer variables. Therefore, the TNEP solution is hard and requires nonconvex mathematical models and mixed-integer nonlinear programming (MINLP).

Thus, the use of some optimization packages such as CPLEX (Copyright^© IBM Corp.), Gurobi (Copyright^© Gurobi Optimization INC.), LINGO package (Copyright^© LINDO SYSTEMS INC.) and others is limited to small test systems and sometimes neglects active transmission losses, mainly due to previous items (b) and (c). This discussion is better addressed in [1, 2].

The aforementioned features make the TNEP problem hard to be solved, and many studies [1,2,3,4] have been performed since the first work in the 70s [5].

There are different approaches for solving the TNEP problem that use linear or nonlinear modeling. Although the linear optimization methods have been widely used, nonlinear models have also been applied to represent aspects such as active transmission losses [2, 6].

Analytical approaches based on Benders decomposition allow including security constraints and representing uncertainties in the TNEP and have received a lot of attention from researchers [7,8,9]. A TNEP model is proposed in [7] that considers investment and operation costs, reliability requirements, stochastic load, hydro inflows, fuel prices and renewable energy, but active transmission losses are ignored. In [8], a multistage decomposition scheme based on the Benders technique is applied to the TNEP. The optimization models have been implemented and solved by using MATLAB^® with Gurobi [10]. However, reliability requirements and transmission losses are not considered.

Security constraints and operation costs are modeled in [9] for one-stage planning problem based on the Benders technique, which is specifically tailored to the TNEP binary decision variables. The solver Gurobi [10] is used via the MATLAB^® interface YALMIP [11], but without including active transmission losses and load uncertainties.

There are many works based on heuristic methods that can find a good transmission planning with reasonable computational effort, even for a multistage planning horizon. Reference [12] shows a heuristic approach based on Lagrange multipliers index for the multistage transmission expansion planning. By using an expansion decision variable incorporated into an integer, coupled and extended linear (DC) OPF, the reference provides an example solved with MINLP from the LINGO package, but limited to a small system.

Metaheuristic approaches are suitable to handle discrete decision variables, but they have their performance affected by the complexity of the solution space. In this way, researches are looking for ways to improve the performance of such techniques, by reducing the search space without losing quality. For that, a constructive heuristic algorithm is proposed in [13], based on sensitivity indices from a hyperbolic tangent function, to initiate a multimodal optimization process and solve the TNEP with suitable and reduced search space. However, transmission power losses and reliability requirements are neglected.

Besides the challenges, many works have been investigating the incorporation of contemporary and complex metaheuristic features for the TNEP. In general, these methods are able to deal with nonconvex solution space having several solutions. In [14], the performance of a metaheuristic algorithm is discussed, but limited to a small system. A genetic algorithm (GA) combined with interior point method (IPM) is applied in [15] to simultaneously solve the TNEP and the reactive power planning problems by using the full nonlinear (AC) network model, but the results are also limited to small-scale system.

In [16], a particle swarm optimization (PSO) is formulated for the TNEP with risk analysis, without considering load uncertainties and security constraints. The PSO is also used in [17] to solve the multi-year transmission planning with uncertainties over the load forecast, but the results are also for small-scale system. Another PSO algorithm is proposed in [18] for the multistage transmission planning in a competitive pool-based electricity market. The algorithm includes load scenarios, market profile, reliability, investment and operating costs for a multi-year horizon by using the AC model, but transmission losses are neglected.

A critical review on transmission expansion planning that focuses on its most recent developments and challenges is presented in [19]. The review gives a classification for different solution methods that have been applied to the problem.

Facing this background, it can be observed that there is a gap in the transmission planning problem. Some works present solutions without considering the active transmission losses and/or security constraints and load uncertainties. Other works only use small and connected systems without isolated buses. Notice that nonconnected networks are widely found in real situations involving, for instance, isolated buses with wind generation or a new bus to be connected to the system. Moreover, some works consider only the heavy load condition, which leads to an excessive investment.

In this way, the present paper proposes a methodology to solve the TNEP problem aiming at providing a comprehensive algorithm. The contributions are listed hereafter:

• 1. A search space reducer (SSR) based on Lagrange multipliers and Benders coefficient suitable for obtaining candidate sub-optimal planning decisions that comprise a set of branches with candidate transmission reinforcements.

• 2. Although the TNEP can be solved by using any metaheuristic algorithm, as GA or PSO, a modified bat algorithm (MBA) is proposed aiming at computational efficiency. In this sense, the proposed MBA needs the specification of only one parameter, spends reasonable computational time to converge and leads to a solution that has been never found in the literature, as presented and discussed in the results.

• 3. As the SSR and MBA form an efficient hybrid algorithm (EHA), it can run many times, which is enough to consider important issues like active transmission losses, security constraints, load scenarios and large-scale real systems in the TNEP problem, with reasonable computational effort. It can be stressed that the handling of the aforementioned issues in a simultaneous way for large-scale networks can be achieved due to the computational efficiency of the proposed approach. For that, the SSR and MBA are effective, as well as the DC load flow model is tailored to represent transmission losses. Notice that the DC model can be considered suitable for the TNEP since it consists of a long-term planning problem [4]. However, some important issues as the network losses are neglected in this model and for eliminating such a drawback, the proposed approach includes the losses into the original DC formulation, aiming at considering them while maintaining the computational efficiency.

The aforementioned contribution and improvements are better explained hereinafter. In addition, the EHA is tested on the Garver and the IEEE 24-bus test systems. As the equivalent Southern Brazilian system is hard to be solved because it presents many isolated buses, it will be used to prove the effectiveness of the proposed approach.

2 Proposed EHA

2.1 The proposed TNEP formulation

The proposed TNEP with the representation of network losses, security constraints criterion ‘N − 1’ and load scenarios is a nonlinear integer program, and it can be modeled as in (1)–(9).

$$ \begin{aligned} {\text{OBF}} = & {\text{Min}}\sum\limits_{{k \in R_{ij} }} {\sum\limits_{ij \in C} {\left( {ce_{k} \cdot {\text{EP}}_{k,ij} } \right)} } \\ & + \sum\limits_{i \in Z} {\sum\limits_{u \in S} {\sum\limits_{c \in L} {\left( {{\text{pc}}_{i} \cdot {\text{pg}}_{i,u,c} } \right)} } } \\ & + \,\sum\limits_{i \in B} {\sum\limits_{u \in S} {\sum\limits_{c \in L} {\left( {{\text{dc}}_{i} \cdot p_{u} \cdot {\text{pd}}_{i,u,c} } \right)} } } \\ \end{aligned} $$

(1)

$$ \begin{aligned} & {\text{Subject}}\;{\text{to:}} \\ & {\text{EP}}_{k,ij} \in [0,1]\quad \forall k \in R_{ij} ,ij \in C \\ \end{aligned} $$

(2)

$$\begin{aligned} &{\text{pg}}_{i,u,c} + {\text{pd}}_{i,u,c} - \sum\limits_{{k \in \varOmega E_{i} }} {fE_{k,u,c} } - \sum\limits_{{k \in \varOmega C_{i} }} {fC_{k,u,c} } \\&\quad= d_{i,u,c} \,\forall i \in Z,\,u \in S,\,c \in L \end{aligned}$$

(3)

$$\begin{aligned} &{\text{pd}}_{i,u,c} - \sum\limits_{{k \in \varOmega E_{i} }} {fE_{k,u,c} } - \sum\limits_{{k \in \varOmega C_{i} }} {fC_{k,u,c} } \\&\quad = d_{i,u,c} \,\,\,\forall i \in B,\,u \in S,\,c \in L \end{aligned}$$

(4)

$$ \left| {fE_{k,u,c} } \right| \le fE_{k}^{{\rm max} } ,\,\,\,\,\forall k \in E_{ij} ,\,ij \in E,\,u \in S,\,c \in L $$

(5)

$$ \left| {fC_{k,u,c} } \right| \le fC_{k}^{{\rm max} } \,\,\,\,\forall k \in R_{ij} ,\,ij \in C,\,u \in S,\,c \in L $$

(6)

$$ {\text{pg}}_{i}^{{\rm min} } \le {\text{pg}}_{i,u,c} \le {\text{pg}}_{i}^{{\rm max} } \,\,\,\,\forall \,i \in Z,u \in S,\,c \in L $$

(7)

$$\begin{aligned} fE_{k,u,c} &= - b_{k} \cdot \theta_{ij,u,c} + g_{k} \\& \quad \cdot \frac{{\theta_{ij,u,c}^{2} }}{2}\,\,\,\,\forall k \in E_{ij} ,ij \in E,\,u \in S,\,c \in L \end{aligned}$$

(8)

$$\begin{aligned} fC_{k,u,c} &= EP_{k,ij} \cdot \left( { - b_{k} \cdot \theta_{ij,u,c} + g_{k} \cdot \frac{{\theta_{ij,u,c}^{2} }}{2}} \right)\,\,\,\\& \quad \forall k \in R_{ij} ,ij \in C ,\,u \in S,\,c \in L \end{aligned}$$

(9)

$$ fF_{k,u,c} = - \gamma_{k} \cdot \theta_{ij,u,c} \,\,\,\forall k \in F_{ij} ,ij \in F ,\,u \in S,\,c \in L $$

(10)

$$ \gamma_{k} < < b_{k} \,\,\,\,\forall k \in F_{ij} ,\,\,\,ij \in F,\,u \in S,\,c \in L $$

(11)

Equation (1) gives the objective function (OBF), where the first term corresponds to the investment related to the transmission system expansion, the second one is related to the operation cost of generators and the third term is related to the minimization of the energy deficit, which has a high operational cost. The deficit flexibility associated with a penalization makes the problem feasible even when the expansions do not meet the load.

Constraint (2) shows the decision of building line k in branch ij, which is represented by a nonzero value of EP_k,ij. On the other hand, when EP_k,ij is zero, it means that line k is not selected to be built.

The active power balance, Eqs. (3) and (4), is given by the well-known Kirchhoff’s first law. These equations include the network losses in an indirect way as described hereinafter, ‘N − 1’ security constraints through the inclusion of operational conditions besides the base case (normal operation condition), as well as different load scenarios. Moreover, positive values for fE_k,u,c and fC_k,u,c mean power flows from bus i, whereas negative values mean flow to bus i. Constraints (5) and (6) represent the limits of active power flow in the existing and candidate lines, respectively, according to their capacities. The generation limits are given by (7).

In the presented model, there are three types of lines: (a) the existing ones in the base topology, (b) the candidate reinforcement lines for expansion and (c) fictitious lines that seek to avoid mathematical issues related to unconnected networks. Then, the power flows through the existing, candidate and fictitious lines are modeled by Eqs. (8), (9) and (10), respectively, which correspond to Kirchhoff’s second law. The second terms of (8) and (9) represent half of the active power losses that introduce a nonlinear quadratic term. Constraints (10) and (11) are added to mathematically avoid problems related to unconnected networks in the OPF model, as in [13], where the value adopted for γ_k is 0.001 pu. Moreover, although unconnected networks are possible to be obtained, they imply high deficit costs, third term of Eq. (1), if load buses are isolated. Therefore, these solutions are avoided in the OPF model.

In (9), it can be emphasized that the decision parameter EP_k,ij multiplies the power flow of candidate line k. Moreover, it implies the multiplication of a discrete parameter, EP_k,ij, and the nonlinear term related to the losses.

The described features make the solution of the TEP problem too hard to be solved by using some optimization package. On the other hand, metaheuristic approaches have been suitable to solve this type of problem as proposed in the present paper. As aforementioned, the proposed approach considers the ‘N − 1’ contingency criterion to represent security constraints in the OPF, where the power system is planned to support single line outages with the maintenance of the power supplying. In ‘N − 1’ operation condition, an overload of up to 10% in each line is allowed.

Therefore, the planning must meet not only the network requirements in normal operation condition but also under contingencies. All these operational conditions are included in set L, and they are considered in equations from (1) to (11). It should be emphasized that the ‘N − 1’ criterion increases the number of equations, thus requiring high computational effort to be solved mainly for large systems.

The representation of load scenarios provides a more realistic solution because the system does not always operate in the peak loading [9]. Therefore, the third term of the OBF (1) includes the summation for load scenarios (u) with their respective probabilities (p_u).

Considering the proposed formulation, the total number of variables (TNV) of the proposed OPF can be calculated by Eq. (12). The expressive number of integer and continuous variables within nonlinear constraints is given by the first and second terms of (12), respectively.

$$ {\text{TNV}} = N{\text{C}} + N{\text{L}} \cdot NS \cdot (N{\text{p}}g + 2 \cdot N{\text{B}}) $$

(12)

The number of variables in (12) is related to:

• N_C correspond to EP_k,ij.

• N_L · N_S · N_pg correspond to pg_i,u,c.

• 2 · N_B correspond to θ_ij,u,c and pd_i,u,c.

For computational efficiency in the face of the high number of variables and the complexity of the mixed-integer problem, the proposed approach involves its decomposition into two parts, as follows.

2.2 The problem decomposition

In order to obtain an efficient approach for solving the TNEP by avoiding nonlinear integer program, a decomposition scheme is proposed by splitting the global problem (1)–(11) into two subproblems, defined as master and slave. The master or investment subproblem performs the lines expansion decisions by optimizing the discrete EP_k,ij variables, as in (13).

$$ {\text{OBF}}_{1} = {\text{Min}}\sum\limits_{{k \in R_{ij} }} {\sum\limits_{ij \in C} {\left( {{\text{ce}}_{k} \cdot {\text{EP}}_{k,ij} } \right)} } $$

(13)

It can be emphasized that only the constraints modeled in (2) should be included in this integer program. This paper proposes a modified bat algorithm to solve the master subproblem as described hereinafter.

On the other hand, the slave or load shedding subproblem is formulated with the objective function OBF₂ of (14), subject to the constraints in (3)–(11).

$$\begin{aligned} {\text{OBF}}_{2} &= \sum\limits_{i \in Z} {\sum\limits_{u \in S} {\sum\limits_{c \in L} {\left( {{\text{pc}}_{i} \cdot {\text{pg}}_{i,u,c} } \right)} } } \\&\quad + \sum\limits_{i \in B} {\sum\limits_{u \in S} {\sum\limits_{c \in L} {\left( {{\text{dc}}_{i} \cdot p_{u} \cdot {\text{pd}}_{i,u,c} } \right)} } } \end{aligned}$$

(14)

It can be stressed that in the slave subproblem, EP_k,ij is not variable, but it is set at the corresponding value obtained in the master subproblem. As a consequence, the slave subproblem consists of nonlinear programming with only continuous variables in constraints (3)–(11).

Figure 1 presents the flowchart of the proposed methodology with the related subproblems. The slave subproblem includes the base case and contingencies for all load scenarios, where each one is solved disconnectedly. It can be observed that the investment decision EP_k,ij, made in the master subproblem through the application of the MBA, gives the reinforcements that should be carried out, which are valid for all condition operations. So, EP_k,ij links the different conditions with each other through the same decision and is sent to the each OPF of the slave subproblems to evaluate OBF₂. Thus, the total load shedding that computes the contributions of all operation conditions and load scenarios is returned to the master subproblem, for a new decision-making process until there is no load shedding with minimal transmission investment.

Fig. 1

Flowchart of the proposed methodology

It can be emphasized that the convergence of the proposed decomposition problem is reached when the second term of objective function (14) is close to zero. In other words, the OBF₁ added to OBF₂ gives the same value of objective function OBF, Eq. (1), in the convergence.

2.3 The proposed search space reducer (SSR)

The proposed SSR seeks to obtain a good set of candidate lines for the search process of the MBA in the master subproblem. As the TNEP is a nonconvex problem with many local optimum points, the initial set has a large influence on the quality of the final solution and can help multimodal search processes faced by metaheuristic algorithms. Therefore, a good initial search space is very important for the efficiency of the proposed approach.

The SSR is composed of two steps as described in Ref. [13]: continuous and discrete. The continuous step is performed to check if there is a load shedding in the system and consists of solving the OPF (1)–(11) for the base case and for all single contingencies, one at a time considering only peak load, with variables EP_k,ij being handled as continuous in the range from ‘0’ to ‘1’. It results in a series of N_L nonlinear programming problems (one base case and contingencies). The nonlinear constraints (8) and (9) are formed by continuous value of EP_k,ij and the square of angular difference to accommodate active power losses. Fortunately, the variable angle is too small because it is given in radians unit. Then, these equations are well behaved, and the region considered in power flow is convex, leading to efficient convergence of any nonlinear package.

The application of two indexes is proposed for reducing the search space by selecting the candidate lines in an efficient manner. Equation (15) shows the first index that can be found in Ref. [9].

$$ \begin{aligned} & SI1_{k} = b_{k} \cdot \theta_{ij,u,c} \cdot \pi_{ij,u,c} , \\ & k \in R_{ij} ,u \in \;{\text{peak load scenario}},c \in L \\ \end{aligned} $$

(15)

where π_ij,u,c is the difference between Lagrange multipliers related to constraints (3), (4) at buses i and j. The Lagrange multipliers provide the marginal costs of a given constraint regarding the objective function. As the angular difference between two buses has a strong relationship with the necessity of a new transmission line, the difference between two Lagrange multipliers could also indicate the same. This reasoning can be extended for the angular difference between terminal buses [13], whereas a high susceptance value favors the power flow through the corresponding line and is also used to suggest potential reinforcements. Therefore, the highest values of SI1_k can indicate candidate lines in the proposed SSR.

The SSR process flows as follows: (a) After the continuous step is performed, SI1_k is calculated by Eq. (15), the candidate line with the higher SI1_k value is selected to be built, and its corresponding EP_k,ij is set at ‘1’ for the remainder of all process. For the other lines, EP_k,ij is set at ‘0’ for the discrete step; (b) the discrete step seeks to evaluate the system operation, based on the load shedding requirement for all single contingencies, evaluated one at a time, with the EP_k,ij obtained in (a). If the total load shedding comprising all the contingencies is smaller than a given tolerance (ε), the planning is reached and the SSR process ends. Otherwise, the process returns to step (a) to include another line.

Looking for enhancing the group of candidate reinforcements with little computational effort, another sensitive index related to the Lagrange multipliers is used to complement the first index and insert other possibilities of reinforcements that may be important for the final solution. It must be highlighted that both indexes used are attested in the literature with good results to solve the TNEP. Therefore, the second index is described in [2] and presented in Eq. (16), which evaluates the sensitivity normalized by the financial costs for constructing a candidate line.

$$ \begin{aligned} & SI2_{k} = {{\left| {\pi_{ij,u,c} } \right|} \mathord{\left/ {\vphantom {{\left| {\pi_{ij,u,c} } \right|} {ce_{k} }}} \right. \kern-0pt} {ce_{k} }} \\ & k \in R_{ij} ,u \in \;{\text{peak load scenario}},c \in L \\ \end{aligned} $$

(16)

The same step-by-step process (a)–(b) described for SI1_k is used to obtain another planning by using SI2_k. After that, the search space is composed of the union of the transmission lines that appear in each planning. As aforementioned, the reinforcements obtained by the SSR are used to define a reduced initial set for the MBA. It can be emphasized that the computational effort in SSR is too small because this problem has only continuous variables.

Notice that the indexes are calculated for the base case and the contingencies that are considered one at a time. In relation to the load scenarios, the indexes are obtained only for the peak load, since this extreme scenario tends to comprise more diverse reinforcements’ options, which contributes for the quality of the reduced search space. For further clarification of SSR, the case study with the well-known Garver system [5] is used as a tutorial description.

2.4 The proposed modified bat algorithm (MBA)

Many recent metaheuristic optimization techniques have been inspired in nature behaviors, such as genetic algorithms and swarm intelligence. Recently, [20] proposed a new optimization algorithm inspired by the echolocation behavior of microbats. Although the algorithm is considered a kind of swarm intelligence, it presents some special features to combine global and local search procedures. The Doppler effect is modeled in [21] for the bat algorithm. This effect is verified in actual waves, as the electromagnetic ones, and the phenomenon consists of changing the frequency observed by the receiver due to the relative movement between source and receiver.

An improvement in a Doppler effect for bat algorithm is proposed in the present paper. Figure 2 presents the MBA steps that consider the Doppler effect. Afterward, the steps and the proposed improvements are described considering each line of Fig. 2 as a step.

Fig. 2

Modified bat-inspired algorithm flowchart

In step 1, the population size, which is a parameter of the algorithm, is defined. The population is initiated at step 2 in a random way resulting in an investment cost (OBF₁) for each individual. Step 3 evaluates the objective function (OBF₂) as well as (OBF) for each individual as a fitness. Step 4 comprises steps 5–21, and it is used to update the population. The convergence criterion checked in step 5 is given by a maximum number of iterations, and step 6 runs all bats. Step 7 updates the frequency according to the Doppler effect, as described in Eq. (17).

$$ f_{\text{Din}} = f_{\text{in}} \cdot \frac{{v \pm v_{*} }}{{v \pm v_{\text{in}} }} $$

(17)

From the updating of f_Din according to the Doppler effect, steps 8 and 9 update v_in and x_Cin, respectively. From step 10, it can be observed the main modification proposed in this paper, which consists of generating random values for A_in and r_in in case of trapping at a local solution, where A_in and r_in are within [0.5, 1] and [0, 0.5], respectively. A random number in the range [0, 1] is generated at step 11 and compared with r_in. If the random number is smaller than r_in, x_Cin will be updated at step 12.

If the condition of step 14 is met, the discrete position value of bat ‘in’ is obtained and x_in is included in the population at step 15. On the other hand, x_Cin is also included at step 16, which is a modification that seeks to maintain the solution even if their conditions are not currently met. It is based on the premise that in optimization, a solution that does not reach the requirements in the current iteration can carry relevant information to evolve the population at the next iterations. Moreover, step 17 checks if x_Cin is within the search space boundary and adjust it if required. Step 18 updates A_in and r_in as described in Eqs. (18) and (19).

$$ A_{\text{in}}^{t} = \alpha_{\text{in}}^{t} \cdot A_{\text{in}}^{t - 1} $$

(18)

$$ r_{\text{in}}^{t} = 1 - A_{\text{in}}^{t} $$

(19)

where α_in is calculated according to the last movement of bat ‘in’. As proposed in the present paper, if bat ‘in’ moves toward the current optimal point (receiver), α_in is given by (20); otherwise (21) is used.

$$ \alpha_{\text{in}}^{t} = \left( {{{r_{\text{in}}^{t - 1} } \mathord{\left/ {\vphantom {{r_{\text{in}}^{t - 1} } 2}} \right. \kern-0pt} 2}} \right)^{{\frac{1}{{0.25 \cdot t_{\hbox{max} } }}}} $$

(20)

$$ \alpha_{\text{in}}^{t} = \left( {{{A_{\text{in}}^{t - 1} } \mathord{\left/ {\vphantom {{A_{\text{in}}^{t - 1} } 2}} \right. \kern-0pt} 2}} \right)^{{\frac{1}{{0.25 \cdot t_{{\rm max} } }}}} $$

(21)

The relative movement between bat ‘in’ and the receiver is Δv in (22). A positive value of Δv means an approximation between bat and receiver, establishing A ^t_in and α ^t_in as proportional to r ^t−1_in . Thus, the amplitude is updated with the pulse rate indicating that the receiver is next, according to the bat algorithm fundamentals. Otherwise, a negative value means a movement in the opposite direction and the amplitude is updated with its previous value, also according to the bat principles.

$$ \Delta v = v_{*} - v_{\text{in}} $$

(22)

Therefore, the proposed MBA is able to obtain the approach or removal information between bat and receiver, by adjusting the updating of rates A_in and r_in according to this relative movement. To illustrate how the proposed modification impacts the convergence of the method, Figs. 3 and 4 present the convergence paths for MBA and the original bat algorithm with the Doppler effect (BA) from the literature [21].

Fig. 3

Pulse amplitude: a MBA and b BA

Fig. 4

Pulse rate: a MBA and b BA

In [21], A_in and r_in receive the initial values ‘1’ and ‘0’, respectively. After that, A_in decreases and r_in increases over the iterations and they take all iterations to converge to ‘0’ and ‘1’, respectively, which consists of the premise of the algorithm.

The major contribution of the proposed modifications is that the MBA rates converge more quickly than the original BA rates, configuring an advance in the research process, as Figs. 3 and 4, which makes the MBA more attractive.

The y-axes of Figs. 3 and 4 refer to the pulse amplitude and rate, respectively, and therefore are given in the usual units for these quantities, i.e., meters (m) for the pulse amplitude and cycles per second (Hz) for the pulse rate.

Despite its fast convergence, the MBA algorithm avoids being trapped into local optimal points due to the action performed in step 10, which promotes a better balance between local and global search at steps 11 and 12, through the random generation of A_in and r_in at each iteration. As a result, the action increases the global exploration of the search space.

In short, the modifications proposed in this work for the bat algorithm are the procedures of steps 10, 16 and 18, as well as the updating of α_in as in (20), (21), which impacts the updating of A_in and r_in in (18), (19). Notice that the most important proposed improvement stems from the previous modifications and consists of reducing the number of pre-established parameters to one; that is, only the population size (η) should be predefined in the MBA, which is an advantage over several metaheuristic techniques from the literature.

3 Results

Three systems are used to assess the proposed EHA for the TNEP: the well-known Garver system, the IEEE 24-bus test systems and a practical large and complex equivalent system from South Brazil. It can be highlighted that the Brazilian system presents difficulties for solving the TNEP due to the presence of several isolated sections. In addition, it has 4⁷⁹ possible reinforcement combinations.

The Garver system [5] is composed of six buses, six existing lines in the base topology and three active power generators. There are 15 expansion branches, a maximum of three lines by branch and an expected load of 760 MW.

The IEEE 24-bus system [22] has 38 existing lines, 10 generators, 41 candidate branches for expansion, where each one can receive a maximum of three reinforcements, and the total demand is 8550 MW.

The equivalent system of South Brazil [22] is formed by 46 buses, being 11 isolated from the system, 66 existing lines in the base topology, 12 generators, 79 candidate branches for expansion, with a maximum of three reinforcements by each branch, and an expected load of 6880 MW.

All single contingencies of the existing lines are considered for the tested systems. Under each contingency, flexibility is considered for the system operation through a permissible overload of up to 10% in each line.

Table 1 presents the load scenarios and its probability for all systems, which were obtained by [9], as a percentage of the corresponding peak load.

Table 1 Loading scenarios

For each system, the following simulation cases (SC) are performed.

SC-A:

TNEP considering only transmission losses, without contingency or load scenarios.

SC-B:

TNEP considering both transmission losses and contingencies, but without load scenarios.

SC-C:

TNEP considering transmission losses, contingencies and load scenarios.

SC-D:

TNEP without considering transmission losses, contingency and load scenarios.

The proposed analyses seek to show the impacts of representing losses, security constraints and load scenarios on the TNEP problem.

All simulations were conducted using a PC core I7 with 2.1 GHz, and all algorithms were implemented on a MATLAB^® platform. In analyses SC-A, SC-B and SC-D, a total of 100 simulations of the proposed MBA are performed to assess its robustness in obtaining good quality solutions, and the population size is 100. For analysis SC-C, in turn, the population size is 50 and the number of simulations is 30 due to the higher computational effort required by this analysis.

For each case study, the best result obtained is presented, together with the best ones found in the literature, except for case SC-C, which no comparison data have been found.

It is worth mentioning that for SC-C, a smaller number of reinforcements are expected in the optimal planning, consequently implying a cost lower than in SC-A and SC-B. It occurs because the peak loads do not operate all the time in SC-C, since the loads are represented by scenarios and their probabilities of occurrence.

3.1 The Garver system

The TNEP for this system has 405 variables, as given by Eq. (12), of which 45 are integer. This TNEP can be solved properly through the proposed EHA. To begin with, the proposed SSR algorithm is applied to find a reduced search space.

Table 2 shows the first calculation round of SI1_k and SI2_k in case SC-A only for major indexes’ values. For SI1_k, line ‘2–6’ has the highest value, so it is chosen as the first reinforcement. On the other hand, for SI2_k the values of lines ‘2–6’ and ‘4–6’ are the same. In this case, the algorithm chooses as the second reinforcement the option that is different from the previous one; i.e., line ‘4–6’ is the second to be built, aiming at improving the set of obtained plans with higher diversity.

Table 2 First calculation of the SI1 and SI2, Garver system

Table 3 summarizes the plans obtained for each index, Eqs. (15) and (16), in case SC-A. When SI1_k is used, six transmission lines are added, and the investment cost is equal to 160 M$, as shown in second row of Table 3, where two lines are added to each one of the indicated branches. Although the plan proposed by index SI2_k is more expensive than that for SI1_k, the former adds an important branch, ‘2–3’. Thus, the two plans have interesting information able to reduce the search space to the MBA application, as described as follows.

• 1. Reduced initial search space: It comes from the union of the branches pointed out by SI1_k and SI2_k. In this case, the union set is given by U = {branches ‘2–3’, ‘2–6’, ‘3–5’ and ‘4–6’}, as described in first row of Table 3. Therefore, the search space is reduced from 15 options, as in the original problem, to the four options of set U. It should be emphasized that up to three reinforcements can be built by branch. Table 4 also presents the reduced search space for SC-D case. The spaces for SC-B and SC-C are the same as for SC-A, in this system.

  Table 3 Plans by SI1 and SI2, Garver system

  Table 4 Reduced space search for the Garver system

• 2. Generation of an initial population for the MBA: Each individual has a number of expansion lines given by a small variation around the number obtained by SI1_k or SI2_k. As the solution from SI1_k presents the smallest OBF, it is chosen in this case to define the size of the individual. So, all individuals of the MBA propose new lines to be built ranging around six. In the present paper, a variation of four lines is used. Thus, all individual ranges from ‘6 − 4 = 2’ to ‘6 + 4 = 10’ reinforcements.

From the previous information provided by SSR, the MBA is performed, and its results are presented in Table 5. For instance, the best solution of SC-A determines three lines in branch ‘4–6’ and one line in each one of the branches ‘2–3’ and ‘3–5’, with a total cost of 130 M$ related to the OBF in Eq. (1). In all cases, there is no load shedding in the system. The proposed MBA reaches the best solution for 100% of the runs; meanwhile, the bat algorithm with the Doppler effect from the literature [21] gives the best solution for SC-A, for instance, in only 19% of the runs and spends around 8.5 min, which shows the effectiveness of the modifications proposed for the literature. The simulation times of Table 5 consist of the mean values obtained in all runs for each case.

Table 5 Best solutions obtained by EHA. Garver system

For SC-C, a smaller number of lines are verified in the optimal planning, in relation to SC-A and SC-B, due to the aspect previously described the peak load duration. Moreover, SC-D also gives a relative small number of reinforcements; because as it does not consider losses, contingency or load scenarios, the corresponding solution is optimist and then less expensive than SC-A and SC-B, but not holistic.

Other simulations were carried out considering no information from SSR. The proposed MBA can obtain the best solutions of Table 5 also without SSR for this system but spends higher computational effort.

Table 6 presents the results found in the literature in the same conditions of cases SC-A, SC-B and SC-D. From Tables 5 and 6, it can be observed that the results from the proposed EHA match the best solutions from the literature for cases SC-A and SC-D. For case SC-B, in turn, the proposed EHA reaches a solution better than the best one from the literature.

Table 6 Results from the literature for the Garver system

3.2 The IEEE 24-bus system

The TNEP for the IEEE 24-bus system has a number of 8939 variables, given by Eq. (12), of which 123 are integer. Aiming at reducing the search space, the EHA starts from the proposed SSR, leading to the reduced set of candidate reinforcements shown in Table 7. For this system, the search space for SC-D is the same as for SC-A, as well as for SC-C and SC-B.

Table 7 Reduced space search for the IEEE 24-bus system

The best solutions obtained for the IEEE 24-bus test system, through the proposed EHA, are presented in Table 8 with the total cost related to OBF (1), whereas Table 9 presents the corresponding results from the literature when they are available. From the comparison between the results of Tables 8 and 9, it can be observed that the proposed approach achieves better solutions than the literature for cases SC-A, SC-B and SC-C, and matches the literature for SC-D, showing the effectiveness of the proposed EHA.

Table 8 Best solutions obtained by EHA, IEEE 24-bus system

Table 9 Results from the literature for the IEEE 24-bus system

The best solution of SC-A was found in 7% of the bat algorithm (BA) [21] runs and spent around 14.5 min, whereas the proposed MBA reaches its best solution in all runs, which shows the effectiveness of the proposed improvements.

3.3 The Brazilian system

For the equivalent Southern Brazilian system, the TNEP involves 27,693 variables, given by Eq. (12), of which 273 are integer. In addition, there are many disconnected buses that bring more complexity to solve this transmission planning. However, starting the proposed EHA with SSR, the reduced search space is reached as presented in Table 10. SC-D has the same candidate reinforcements of SC-A, and the same occurs for SC-C and SC-B.

Table 10 Reduced search space for the Brazilian system

Tables 11 and 12 present the results for the Southern Brazilian equivalent system obtained by the proposed EHA and from the literature, respectively. Again, the proposed approach presents better results than the literature for all simulation cases that have reference in the literature for comparison. It can be highlighted that the computational time spent by the proposed algorithm is not prohibitive for the TNEP because it consists of an offline application.

Table 11 Best solutions obtained for the Brazilian system

Table 12 Results from the literature for the Brazilian system

For SC-A, the BA [21] reaches the best solution in only 2% of the runs, spending around 34.5 min, whereas the proposed MBA reaches its best solution in 52% of the runs. Thus, the proposed modification is also effective for this real test system.

4 Conclusions

This work presented an efficient hybrid algorithm to solve the TNEP problem considering transmission losses, ‘N − 1’ security constraints within the optimization procedure and probabilistic load scenarios at the same time, due to the efficiency of the proposed EHA provided by the SSR and MBA. The EHA previously reduces the space search to improve its efficiency by using two sensitivity indexes based on Lagrange multipliers. After that, EHA uses an efficient modified bat algorithm to find the optimal transmission planning. The proposed modification in original Doppler effect of bat algorithm represents a valorous contribution because it prevents the algorithm from being trapped into local solutions, as it was proven in the obtained results, which have quality equal or better than those of solutions found in the literature. In addition, the MBA requires the specification of only one parameter, which is a good feature expected from a metaheuristic technique. The results also show the effectiveness of the proposed approach even for practical systems with many isolated buses. Therefore, the EHA has also potential to be applied in a real system with wind generation as well as other renewable sources.