Electric Transmission Network Expansion Planning with the Metaheuristic Variable Neighbourhood Search

1. Introduction

Due to consumption growth of electrical power, the need of increasing the existing transmission network power flow capacity is evident. This expansion can be a dynamic or static performance. The static long-term power transmission network expansion planning (TNEP) problem consists of determining the minimum cost planning which specifies the number and the locations of transmission lines to meet a forecasted demand while satisfying the balance between generation and load and other operational constraints [1]. Transmission investments are very capital intensive and have long useful lives, so transmission investment decisions have a long-standing impact on the power system as a whole; therefore TNEP has become an important component of power system planning, and its solution is used to guide future investment in transmission equipment.

The pioneering work on transmission expansion planning is reported in [2], and since then TNEP literature has been vast and reports that there are usually considered various solution methods that depend on the mathematical model formulation [3]. A state of the art, which was obtained from the review of the most interesting models found in the international technical literature, is presented in [4]. In [5] TNEP is reviewed from different aspects such as modelling, solving methods, reliability, distributed generation, electricity market, uncertainties, line congestion and reactive power planning. A critical review focusing on its most recent developments and a taxonomy of modelling decisions and solution to TNEP are presented in [6].

The convenient mathematical modelling to indicate the appropriate operation would be the representation of the problem by mathematical relationships of the AC load flow, typically used for the electric system operation analysis [1]. However, this modelling is more difficult to be used in an efficient way in transmission network planning, due to its non-convex and nonlinear nature. Consequently, the mathematical modelling in its most accurate representation is the direct current (DC) model, which considers Kirchhoff’s voltage (KVL) and current (KCL) laws just for balance and active power flow. In this case, the resulting problem is a nonlinear mixed-integer programming with high complexity for large systems, presenting combinatorial explosion of the number of alternative solutions, with extra difficulty of presenting many local optima, which most of the time are of poor quality [3].

A more simplified modelling is the so-called transportation model (TM) which just enforces the KLC at all existent nodes [2]. In this case the resulting problem is an integer linear programming problem which is normally easier to solve than the DC model although it maintains the combinatorial characteristic of the original problem [3].

It is still possible to consider hybrid models which combine characteristics of the DC model and the transportation model. In this model it is assumed that KCL constraints are satisfied for all nodes of the network, whereas the constraint which represents Ohm’s law (and indirectly KVL) is satisfied only by the existing circuits (and not necessarily by the added circuits) [3].

Technical literature related to the TNEP proposes many solution methods that can be classified into mathematical optimization, heuristic and metaheuristic approaches [7]. Techniques such as dynamic programming [8], linear programming [2], nonlinear programming [9], mixed-integer programming [10], branch and bound [11], hierarchical decomposition [12] and Benders decomposition [13] have been used and are categorized as mathematical-based approaches. But these techniques demand large computing time due to the dimensionality curse of this kind of problem. Heuristic methods emerged as an alternative to classical optimization methods, and their use has been very attractive since they were able to find good feasible solutions demanding less computational effort.

Some heuristic approaches have been proposed using constructive heuristic algorithms (CHA) [10, 14, 15, 16] and the forward-backward approach [17]. Metaheuristic methods emerged as an alternative to the two previous approaches, producing high-quality solutions with moderate computing time. Genetic algorithms [18, 19], greedy randomized adaptive search procedure [13], tabu search [20, 21], simulated annealing [20, 22], GRASP [23], scatter search [24] and grey wolf optimization algorithm [25] have been used to solve the TNEP problem, among other metaheuristic optimization techniques. It is important to point out that they cannot guarantee the global optimal solution to the TNEP problem.

A varied bibliography regarding the theory and application of metaheuristics can be found in [26, 27]. Other applications of metaheuristics appear in [28].

Considering that exact methods of optimization to TNEP are not efficient to big data problems, this paper presents a novel metaheuristic method that considers the so-called variable neighbourhood search (VNS) to solve the TNEP problem considering DC model. The VNS metaheuristic was presented in the middle of the 1990s, by Mladenovic and Hansen [29], and represents a significantly different proposal compared to other metaheuristics. The fundamental idea of the VNS algorithm is based on a basic principle: to explore the space of solutions by systematic changes of neighbourhood structures during the search process. Thus, the transition through the search space of the problem is always accomplished with an improvement of the objective function, and, therefore, the transition is not allowed for a solution of worse quality as occurs with most of the metaheuristics [29].

The VNS algorithm was used with success in the optimization of several problems of operational research [26, 27, 29, 30], but it is still insignificant in the optimization of problems related to the operation and the planning of electric power systems. The VNS was used to TNEP considering transportation model in [31, 32].

This paper is organized as follows: Initially the mathematical model for TNEP problem and the VNS metaheuristic are presented. After, the developed VNS algorithm to solve the TNEP problem is described. Later, obtained results are presented and commented. Finally, conclusions are drawn.

2. Mathematical model of TNEP

The mathematical formulation of the TNEP for the DC model is given by Eqs. (1)–(8) and performs as a nonlinear mixed-integer programming problem [3]:

where vis the total investment value for a predefined horizon; cijis the cost of a circuit or facility that can be added in the branch ij; nijis the number of circuits added during the optimization process; nij0is the number of existing circuits in the initial topology; γijis the susceptance of the branch ij; θiis phase angle at the bus i; Fis the vector of power flow with components fij; f¯ijis the transmission capacity of a circuit through branch ij; Ais the transposed incidence branch-node matrix of the power system; Gis a vector with elements gk(power generation at bus k) with maximum values g¯k; n¯ijis the maximum number of circuits that can be added to the branch ij; Ωis the set of all branches where it is possible to add new circuits.

Eq. (1) that contains the sum of the investments costs is the objective function. The KCL is framed in Eq. (2), and the Ohm’s law is expressed in Eq. (3) which implicitly takes into consideration Kirchhoff’s voltage law (KVL). Inequalities Eq. (4) represent capacity constraints for transmission lines, whereas the absolute value is necessary since power can flow in both directions. Other constraints Eqs. (6)–(8) represent operational limits of the generators, maximum limit for the addition of circuits per branch and integrality demand of the variables nij, respectively.

The model Eqs. (1)–(8) cannot be solved by using traditional algorithms, and there is no efficient method for solving these kinds of problems directly. Therefore, metaheuristics become suitable optimization tools for finding optimal and suboptimal solutions for the TNEP problem when it is considered complex power systems (big instances).

A more simplified model called the transport model can be considered, which contemplates only Kirchhoff’s current law and could be obtained by relaxing the nonlinear constraint Eq. (3) of the DC model described above [3]. In this case, the resulting model is an integer linear programming problem. Even though it is linear, it is still very difficult to find the optimal solution for large and complex systems. The transport model was the first systematic proposal of mathematical modelling used with great success in the problem of planning of transmission systems. The model was proposed by Garver [2] and has represented the beginning of systematic research in the area of transmission system planning.

Another model that has been considered for the PPEST is the linear hybrid model (LHM) which combines characteristics of the DC model and the transport model. This model, in a simpler formulation, preserves the linear properties of the transport model, considering Kirchhoff’s current law in all nodes of the network and KVL only in the circuits in the base network (not necessarily in the circuits that will be added) [3, 10]. The LHM is framed by Eqs. (9)–(17):

where A0is the transposed incidence branch-node matrix of the base topology in previews iterations of the algorithm system; F0is the vector of base power flow with components fij0; nij0is the circuits added during the iterative process to the base case; Ω0is the set of all the circuits added during the iterative process and all of the prime circuits of the base case.

The LHM was originally proposed in [10] whose authors present a mathematical modelling Eqs. (9)–(17) which specifies that the portion of the electric system corresponding to the circuits existing in the base configuration must satisfy the two Kirchhoff’s laws and the other corresponding part from new circuits must satisfy only Kirchhoff’s current law.

The LHM Eqs. (9)–(17) will be considered as a sensitivity indicator to the proposed heuristic algorithm.

3. Metaheuristic VNS

A metaheuristic is a search strategy that orchestrates an interaction between local improvement procedures and higher local strategies to create a process capable of escaping from local optima and performing a robust optimization method for complex problems. This search is performed by means of transitions in the search space from an initial solution or a set of initial solution. In this context, the main difference among the diverse metaheuristic techniques is the strategy used to carry out the transitions within the search space. VNS is a metaheuristic that systematically exploits the idea of neighbourhood change to find local-optimal solutions and to leave those local optima. In that fundamental aspect, VNS is significantly different from other metaheuristics. Most metaheuristics accept the degradation of the current solution as a strategy to leave a local-optimal solution. The VNS algorithm does not accept this possibility [26].

The VNS algorithm changes the neighbourhood as a way of leaving local-optimal solutions. During this process, the current solution is also the incumbent, which does not happen with other metaheuristics. Thus, it is possible to state that the VNS algorithm performs a set of transitions in the search space of a problem and at each step this transition is performed for the new incumbent. If the process finds a local optimum, then the VNS algorithm changes the neighbourhood in order to leave from that local optimum and to achieve the new incumbent. As a consequence of this strategy, if the VNS algorithm finds the global optimum, the search stops at that point, eliminating any chance of leaving it. This behaviour does not occur with other metaheuristics.

The strategy of the VNS algorithm is inspired by three important facts [29]:

Fact 1—A minimum with regard to one neighbourhood structure is not necessary for another.

Fact 2—A global minimum is a local minimum with regard to all possible neighbourhood structures.

Fact 3—For many problems, a local minimum with regard to one or several neighbourhoods is relatively close to each other.

The latter is particularly important in the formulation of the VNS algorithm. This empirical fact implies that a local-optimal solution often provides important information regarding the global one, especially if the local-optimal solution presents excellent quality. It is also an empirical fact that local-optimal solutions are generally concentrated in specific regions of the search space. If local-optimal solutions were to be uniformly distributed in the search space, all metaheuristics would become inefficient. Consequently, if a local optimum is found in the same region where the global optimum is, then the VNS metaheuristic has better chances of finding this global optimum. On the other hand, if the global optimum pertains to another region, then the only possibility to find it is to implement a diversification process. For this reason, equilibrium between intensification and diversification during the search process can be important in a metaheuristic.

There is another important aspect related to the quality of the local optimum that should be part of the implementation logic of a VNS algorithm. A local optimum with a better-quality objective function is not necessarily more suitable for trying to find the global optimum. Let xaand xbbe two local-optimal solutions with fxa<fxbfor the minimization problem. Considering the traditional analysis, it can be concluded that xais a local optimum with better quality than xb.

If these solutions are to be used for initiating (or reinitiating) the search process, then it can be affirmed that the solution presenting internal characteristics closer to those of the global optimum is the most suitable for initiating (or reinitiating) the search and, consequently, solution should not necessarily be chosen.

Thus, for instance, considering the TNEP problem, the local-optimal solution with the largest number of nijelements equal to the optimal solution is the most appropriate for initiating (or reinitiating) the search. It is evident that in normal conditions, the optimal solution is unknown. However, there are some problems where the optimal solution is known, and there are also various heuristic algorithms to find local-optimal solutions for this problem.

In this way, the previous observation can be used to identify the heuristic algorithm that produces best-quality local-optimal solutions for initiating the search using the VNS algorithm. This type of behaviour occurs in the TNEP problem where for some instances (power systems) optimal solutions are known and various constructive heuristic algorithms used to find excellent local-optimal solutions are available. Thus, the best constructive heuristic algorithm to be incorporated into the solution structure of a VNS algorithm can be identified.

Let Nk, k=1,…,kmaxbe a finite set of preselected neighbourhood structures, and let Nkxbe a set of solutions or neighbours in the kth neighbourhood of x.

An optimal solution xopt(or global minimum) is a solution where the minimum of Eqs. (9)–(17) is achieved.

A solution x′is a local minimum of Eqs. (1)–(8) with regard to Nkx, if there is no solution x′∈Nkx⊆X,such that fx′′<fx′.

Thus, the idea is to define a set of neighbourhood structures that can be used in a deterministic, random or both deterministic and random manners. These different forms of using the neighbourhood structure lead to VNS algorithms with different performances.

There are various proposals of VNS algorithms that can be used independently or in an integrated manner forming more complex VNS structures. The simplest form of a VNS algorithm is the variable neighbourhood descent (VND). The VND algorithm is based on previously mentioned Fact 1, i.e. the local minimum for a given move is not necessarily the local minimum for another type of move [29]. In this way, the local optimum x′in the neighbourhood N1xis not necessarily equal to the local optimum x′′of x′to the neighbourhood N2x.

The VND algorithm takes on the form shown in Figure 1.

This algorithm can be integrated into a more complex structure of the VNS algorithm.

For example, the sept (a) in Figure 1 could be replaced by randomly generating a solution neighbour x′of x(x′∈Nkx); and the resulting algorithm is called the reduced variable neighbourhood search (RVNS). In the RVNS, usually, the neighbourhoods will be nested, i.e. each one contains the previous. Then a point is chosen at random in the first neighbourhood. If its value is better than that of the incumbent (i.e. fx′<fx), the search is recentred there (x′← x). Otherwise, one proceeds to the next neighbourhood. After all neighbourhoods have been considered, one begins again with the first, until a stopping condition is met.

The RVNS algorithm chooses neighbours more dynamically by selecting those from all neighbourhood structures (diversification) and prioritizing the first neighbourhood structure (intensification) during the initial stages of the search. Nevertheless, an important component of the RVNS structure is its capacity for finding new promising regions from a local optimum. The RVNS algorithm can also be used independently or be integrated into a more complex structure of the VNS algorithm.

More efficient VNS algorithms can be formulated by integrating those characteristics of the VND algorithm that allow local quality optima to be found and those of the RVNS algorithm that allow new promising regions from a local optimum to be found. Thus, by merging those characteristics, two types of VNS algorithms that generally exhibit excellent performance can be formulated. These algorithms are called the basic variable neighbourhood search (BVNS) and the general variable neighbourhood search (GVNS).

The BVNS algorithm combines a local search with systematic changes of neighbourhood around the local optimum found in [33]. The structure of the BVNS algorithm is presented in Figure 2.

The logical procedure adopted by the BVNS is very interesting. Firstly, kneighbourhood structures should be chosen. The optimization process is initiated from a solution xand the corresponding neighbourhood N1x. Then, a neighbour x′of xin N1xis randomly selected. From x′, a local search process to find the local optimum x′′is started.

In this context, three cases may occur:

1. If x′′it is equal to x′, one already was the local optimum of the valley and, consequently, a change of neighbourhood level should be performed (N2xin this case).

2. If x′′is worse than x′,then the local optimum with less quality than the incumbent xwas found, and a change of neighbourhood should also be carried out.

3. If x′′is better than x′, it means that a better solution than the incumbent was found, and, consequently, the incumbent should be updated; the search should be reinitiated from the new incumbent while remaining in the neighbourhood N1.

Whenever the local search finds a new incumbent, at any iteration of the process, the neighbourhood N1xshould be considered again. Also, whenever the local search finds an equal or worse quality solution than the incumbent, a change towards a more complex neighbourhood should be performed. This strategy and the random choice of the incumbent x’neighbour avoid cycling and allow local optima which are distant from the current incumbent to be found.

The local search of the BVNS algorithm can be any heuristic strategy. Nonetheless, the local search can also use a strategy of the VNS algorithm. Therefore, the BVNS algorithm can be transformed into a more general algorithm called general variable neighbourhood search (GVNS). The GVNS algorithm is obtained through the generalization of the BVNS algorithm by simply using a VND algorithm as a local search and using a RVNS algorithm to improve the initial solution required to begin the search.

All observations made for the BVNS algorithm remain valid for the GVNS algorithm. As mentioned previously, the fundamental change corresponds to the improvement stage of the initial solution using an RVNS algorithm and a VND algorithm for the local search stage.

Since the VNS algorithm can be implemented in various ways, a family of VNS algorithms can also be implemented. In [26, 30, 33] diverse types of VNS algorithms are analysed. In this work, only one of these algorithms is presented. There are other more complex algorithms or structures based on the logic of the VNS algorithm that are out of the scope of this work. Those algorithms can be found in [30, 33].

4. Modified VNS for TNEP

In this section the application of our proposed VNS to the TNEP will be described. The GVNS described in Figure 3 will be used considering the following steps that will be explained in detail in sequence:

1. Step 1—Initial solution: Considering a heuristic algorithm to determine an initial solution.

2. Step 2—Definition of neighbourhoods: Characterization of each neighbourhood and determination of their elements.

3. Step 3—Improvement: Improve the initial solution by using a RVNS algorithm.

4. Step 4—Local search: Apply some local search to determine the best configuration for each current solution neighbourhood.

5. Step 1: Initial solution

To determine a DC initial solution to TNEP, the constructive heuristic algorithm (CHA) presented by Villasana-Garver-Salon (VGS) [10] is considered. This algorithm iteratively chooses a new circuit to be added to the system considering a step-by-set procedure that uses a sensitivity index (given in Eq. (18)) that plays a key role in the CHA. The iteratively process continues until a feasible solution is achieved; that means that there is no need for new circuit additions:

Generally, for large and complex systems, the derived solutions are local-optimal [10]. The VGS can be summarized by the following steps:

• VGS1: Take a base topology as a current solution, and resolve the HML Eqs. (10)–(17) considering that all of the circuits of the current solution must follow both Kirchhoff’s laws.

• VGS2: Solve LP for the HML using the current solution. If the LP solution indicates that the system is adequately operating with the new additions and v=0, then stop. A new solution for the DC model was found. Go to step 4.

• VGS3: Identify the most attractive circuit considering the sensitivity in Eq. (18). Update the current solution with the chosen circuit, update nij0and Ω0, and go to step 2.

All of the added circuits represent the solution of the CHA. It can be noted that although the VGS uses a hybrid linear model to identify the best circuit for addition in an iterative process, it complies with both of Kirchhoff’s laws after adding a new circuit; thus, the final solution is also feasible in DC.

Example 1: considering Graver’s system [34] that includes six transmission lines and six buses with a 760-MW demand for base topology, which is shown in Figure 4a, after has applied the VGS it gave the topology in Figure 4b, with v=130.000 m.u.

1. Step 2: Definition of neighbourhoods

Given solution x,the structures of neighbourhood within the solution space can be defined by Eq. (19):

where dxx′=kis the quantity of branches with a different number of added circuits in the solutions xand x′.

For example, given solutions x, x’and x”from Figure 5a–c, respectively, which are coded in Figure 6, dxx′=1, and dxx′′=2. So, solution x′is a neighbour of xin N1x, and solution x′′is a neighbour of xin N2x.

Neighbour x′is obtained from xby adding a circuit in branch 8 (buses 3–6), whereas the neighbour x′′was obtained from xby adding one circuit in branch 7 (buses 3–5) and removing one circuit in branch 9 (buses 4–6). In the same way, the neighbours in the other kneighbourhoods can be obtained.

1. Step 3: Improvement of the initial solution

Considering kmax=5and the initial solution obtained in step 1, a local improvement search using a GVNS described in Figure 3 is applied considering the HLM Eqs. (9)–(17).

In N1x, sort all added circuits in cost-decreasing order, remove the circuit having the maximum cost, and verify the operation using the HLM model. If such removal keeps a feasible solution which indicates that the system is in adequate operation condition (i.e. v=0after HML solution), remove that circuit; otherwise, keep the circuit. Repeat the process of simulating circuit removal until all of the added circuits have been tested.

At the end of the process, all the added circuits that were not removed represent the improved solution.

As for the remaining neighbourhoods, the cost variations due to changes (cost difference between entering and leaving circuits) are calculated, and only the changes that exhibit negative variation are simulated (the HLM is solved). If the simulation points out a feasible configuration, then it is a candidate to be used by updating the current configuration. If the new configuration is unfeasible, then the simulation is cancelled.

It is important to elucidate that the movement only be carried out if the new configuration is better than the incumbent and that in this step the procedure only accepts movements that lead to feasible solutions.

The stop criterion corresponds to the maximum number of solved HLM.

1. Step 4: Local search

The local search is based in VND described in Figure 1.

5. Results

To illustrate the effectiveness of the proposed method, three problems are considered: the Garver 6-bus, the IEEE 24-bus and the Brazilian Southern 46-bus systems.

Full data can be found in [34, 35, 36], respectively. Planning could be done with (r) or without (w) generation rescheduling, resulting in these following cases that have been widely used to validate results of new methods [2, 10, 15, 16, 20, 34]; Da [21, 22, 23, 24, 31, 32, 35, 36]:

• Case 1w: Garver 6-bus system without rescheduling

• Case 1r: Garver 6-bus system with rescheduling

• Case 2w: IEEE 24-bus system without rescheduling

• Case 2r: IEEE 24-bus system with rescheduling

• Case 3w: Brazilian Southern 46-bus system without rescheduling

• Case 3r: Brazilian Southern 46-bus system with rescheduling

The Brazilian Southern is a real referred system originally formed by 46 buses and 66 circuits in the base topology, 79 candidate paths and 6.880 MW as expected demand [35].

For reducing the size of the considered neighbourhoods, only those added circuits operating below 70% of their capacity were considered to be candidate circuits for removal.

Table 1 shows the results. The proposed method was more efficient than the methods shown in [15, 20], since it requires less number of linear programing resolutions.

6. Conclusions

In this paper an efficient new method based on variable neighbourhood search has been proposed for transmission networking problem planning considering the DC model whose mathematical formulation is nonlinear and mixed integer. The TNEP is a multimodal problem of high complexity for medium and large systems and cannot be solved by exact algorithms in reasonable computational times.

The proposed method systematically exploits the idea of neighbourhood change to find local-optimal solutions and to leave those local optima. It was observed that the definition of neighbourhood structures plays an important role to the convergence of the VNS algorithm applied to TNEP.

The proposed method was tested in the Garver 6-bus, in the IEEE 24-bus and in the Brazilian Southern 46-bus systems, and the results got more chance of finding better solutions than mathematical optimization techniques and find local-optimal solution requiring fewer solved linear problems.

As further research directions, new strategies for reducing the size of the neighbourhood such as using adjacency lists to avoid adding new lines in isolated circuits and different kinds of structure neighbourhoods could be developed.