A Joint Planning Method for Substations and Lines in Distribution Systems Based on the Parallel Bird Swarm Algorithm

Abstract

Reasonable distribution network planning schemes can not only improve the power quality and power supply capacity of the power system, but also increase the economic benefits and welfare of the whole society. In this work, a bi-level optimization model is proposed for the joint planning of substations and lines in looped urban distribution systems. The upper-level model aims to address the substation locating and sizing problem, whereas the lower-level model the network planning problem. Both the substations directly supplying power to a load and the contralateral substations that act as backup power source to the load are considered in the bi-level model. In order to solve the bi-level planning model which is mathematically mixed integer programing and with plenty of continuous and discrete variables, the bird swarm algorithm is improved and applied based on the idea of parallel computing of big data theory. Simulations on actual planning problems are employed to verify the effectiveness of the proposed bi-level distribution network planning model and the parallel bird swarm algorithm.

1. Introduction

Reasonable distribution network planning schemes can not only improve the power quality and power supply capacity of the power system, but also increase the economic benefits and welfare of the whole society. In the distribution network planning (DNP) problem, the load amount and the status of the distribution network within the future planning horizon should be forecasted, and the planning requirements of substations in each voltage level should be determined on the basis of the power balance constraint [1,2]. Then the locations and sizes of substations can be optimized. The planning of lines or the network is performed finally. After the power is balanced, there is also an alternative, i.e., joint planning for substations and lines in a distribution network, which is the focus of this work.

So far, there have been many research works on optimization models and solving algorithms of the DNP problem. The researches on optimization models for distribution system planning include single stage ones and multi-stage ones, which generally aim to minimize the investment with the power balance constraint and transmission limit constraints met. The distributed generators, energy storage system, DC distribution system, active distribution network, and energy internet are also considered in this category of works to formulate the optimization models. This is thanks to the advancements in sophisticated control, monitor and coordination technologies and data mining as well as analyzing methods in power systems [3,4,5]. In ref. [6], a two-stage robust investment co-planning model is presented, wherein the first stage model addresses the investment decisions, while the second stage model adjusts the demand response participations so as to coordinate the distributed generation. In ref. [7], a DNP model is proposed taking into account wind power, solar power, controllable loads, the temporal characteristic and randomness of these distributed energy sources (DESs), and the reactive power balance. In ref. [8], a DNP model is presented with the applications of multi-energy conversion and storage equipment to the energy internet considered. In ref. [9], a bi-level robust planning method considering distributed generator and loads in an active distribution network is proposed and a second order cone optimization model is formulated to describe the problem. In ref. [10], a multi-configuration multi-period optimal power flow (OPF)-based method for assessing the maximum distributed generator capacity in active distribution systems is proposed with the uncertainties and different operational status of distributed generator considered. In ref. [11], the reinforcement of the existing substations and distribution lines, capacitor and voltage regulator placement, as well as network expansion of the active distribution network are addressed and are proposed as a multi-stage optimization model in minimizing the net present values of investment cost. In ref. [12], the investment costs of an AC/DC hybrid distribution system and an AC distribution system are compared, and the results show that the hybrid system with sensitive loads has a smaller investment cost. Based on the characteristics of the DNP problem, some publications have proposed multi-objective models that consider the investment and operating costs and reliability of the distribution system. In ref. [13], the objectives are to minimize the investment cost, the cost of network losses, and the index of network risk. In ref. [14], the annual equipment investment cost, the cost of active power losses, the cost of reliability losses, and the cost of importing power from the upper power grid are used as the objectives of the DNP model. In ref. [15], a two level optimization model for the DNP problem with DESs is proposed, where the upper-level aims at minimizing the annual comprehensive cost, whereas the lower-level aims at minimizing the abandoned DES output power. In ref. [16], the objective of the DNP model is to maximize the total supply capability with the N-1 security constraint met. Some works on long-term DNP have investigated the multi-stage planning strategy. In these works, the decision variables at various stages are considered, and multi-stage DNP models are presented [17]. In ref. [18], based on geographic information system data an integrated model for distribution network load forecasting, substation location, and planning is proposed to improve the accuracy of the DNP, in which the spatial attributes of loads, substations, and networks in the distribution network are considered.

In terms of solving algorithms, substation and network planning in the distribution network is essentially a mathematical optimization problem, thus the methods for solving mathematical optimization problems, such as heuristic algorithms and mathematical programming [19], can be utilized to solve DNP models. In ref. [20], the improved immune clonal selection algorithm is used to optimize the DNP model, and the graph theory to repair the infeasible solution and improve the efficiency of the algorithm [21]. The planning problem of three-phase reactive power optimization, in which the variables in the optimization model are continuous but the model itself is non-convex, is addressed in ref. [22] by converting the non-convex model to a convex one through the second-order cone relaxation technique. Then the problem can be solved in polynomial time using the existing optimization algorithms. In ref. [13], a multi-objective DNP model is presented, in which the improved strength pareto evolutionary algorithm and TOPSIS (technique for order preference by similarity to an ideal solution) method are utilized to optimize the multi-objective model. In ref. [14], the multi-objective DNP model is transformed into a single-objective programming problem by weights. Some works have formulated the DNP model considering uncertainties. In ref. [23], a DNP model considering natural disasters is presented utilizing robust optimization to tackle uncertainties of natural disasters. In ref. [24], the impacts of natural disasters on the distribution network are modelled as scenarios, and the scenario-based method is used for DNP. In ref. [25], the blind number theory is used to describe the uncertainties of future power sources and load demands, and a blind number theory based DNP model is presented.

Based on the current research works related to substation locating, a joint planning method for substations and lines in the distribution network is proposed in this work. The proposed model is applicable to looped networks. The traditional DNP models usually consider only the selection of substations that supply power to the loads, whereas in order to reduce the total length of the lines and reduce the investment cost, the proposed model considers the selection of the contralateral substation that is connected to the load but does not directly supply power to that load under normal operating conditions. Besides, in order to deal with the data-intensive problem in the planning model, the solving algorithm is improved based on the idea of parallel computing of big data theory, so as to attain the planning schemes.

In summary, the main contributions of this works are as follows. (1) A bi-level optimization model for distribution network planning is presented, in which the upper-level model focuses on the substation locating and sizing problem, whereas with the lower-level model the network planning problem; (2) A joint planning method for substations and lines in the distribution network based on the bird swarm algorithm (BSA) is proposed for dealing with plenty of continuous and discrete variables in the bi-level distribution network planning model; (3) A master-slave architecture based parallel BSA for joint planning of substations and lines in distribution systems is proposed based on the idea of parallel computing of big data theory for increasing the computational efficiency.

The rest of this work is organized as follows. Section 2 presents the BSA method, the bi-level joint planning model and the master-slave architecture based parallel BSA for solving the bi-level planning model. Simulations, compressions, and discussions of the proposed parallel BSA-based bi-level joint planning model are presented in Section 3. Section 4 concludes this work.

2. The Joint Planning Method for Substations and Lines in the Distribution Network Based on Parallel Bird Swarm Algorithm

The current researches on DNP first optimize the substation locating problem, and then determine the network planning scheme after the locations of substations are known. This category of planning models is generally small-scale. On the other hand, there are also joint methods for planning substations and lines in the distribution network, which aim to attain a globally optimal solution [26]. In this work, the joint planning of substations and lines in the urban distribution network is investigated. Since the joint planning of substations and lines is an optimization problem, generally characterized as nonlinearity, multi-extreme value, and plenty of variables, BSA is introduced for the joint planning of the distribution system. Then, a bi-level DNP model is proposed, in which the upper-level model aims to address the substation locating and sizing problem while the lower-level model the network planning problem. For the sake of solving the proposed bi-level problem, the procedures of applying BSA are presented in detail and a master-slave architecture based parallel BSA is proposed for the bi-level DNP optimization problem.

To increase the reliability of power supply, urban distribution networks are generally designed to be closed loop, although they are open loop when in normal operation [27,28]. When the power supply to a load is from two different substations, the substation not directly connected to that load (i.e., the contralateral substation) generally has a greater impact on the line length and cost since that substation has a longer distance than the substation that provides the concerned load with power. Based on these conditions, the DNP model for the urban distribution system is presented in this work. The characteristic of the closed loop of the urban distribution network is taken into account in the presented model, i.e., in addition to consideration of the substation directly providing power, the contralateral substation is also considered.

After the selection of substations, only a few locations of the substation can be optimized to be the candidate sites, which are represented as a binary variable. Then the locating and sizing problem of substations can be formulated as a mixed integer programming model with binary variables, and the network planning problem as an integer programming model. The objective functions of the models are characterized as nonlinearity, multi-extreme value, and plenty of variables. The feasible domain of these models is discontinuous and even non-analytic on some conditions. Therefore, heuristic algorithms can be used to solve the DNP models. Among many heuristic algorithms, the swarm intelligence based evolutionary methods are suitable tools for solving planning problems, since they can approximate the optimal solutions by randomly generating initial solution groups and iteratively optimizing the problems of concern. Many research works have been conducted to explore and improve the intelligence based evolutionary algorithms, such as the genetic algorithm [29], particle swarm optimization [29,30], the artificial fish school algorithm [31], the firefly algorithm [32], chicken swarm optimization [33], and the bird swarm algorithm (BSA) [34]. Among these algorithms, BSA can effectively optimize non-convex and non-differentiable optimization problems through simulating the natural behavior of birds [35], and is not subject to local optimal solutions. Therefore, BSA is utilized in this work for solving the proposed planning model.

2.1. The Bird Swarm Algorithm for DNP

BSA is a new heuristic algorithm established based on the characteristics of swarm behaviors of many birds in nature, such as foraging, vigilance, and migration of bird swarms [34]. These swarm behaviors of BSA are presented as follows.

2.1.1. Foraging Behavior of BSA

Each bird in the swarm searches for food based on the foraging experience of the swarm and its own. The bird immediately records the best position and shares it with the entire swarm. The optimal foraging position of the entire swarm is counted as an updated foraging experience for further foraging. The foraging behavior can be expressed as follows [33,34]:

$$x_{i,j}^{t+1}=x_{i,j}^t+(B_j-x_{i,j}^t)·C_1·rand(0,1)+(p_{i,j}-x_{i,j}^t)·C_2·rand(0,1)$$

(1)

where $x_{i,j}^t$ represents the jth direction of the position of the ith bird at time t; $B_j$ represents the jth direction of the optimal position of the swarm; $p_{i,j}$ represents the jth direction of the optimal position of the swarm that the ith bird has gone through; C₁ and C₂ are two positive coefficients representing the cognitive and social accelerated levels respectively; rand(0,1) represents a random number within interval [0, 1] that satisfies the uniform distribution.

2.1.2. Vigilance Behavior of BSA

In BSA, the birds would attempt to move to the center of the swarm. When a bird moves towards the center of the swarm, it is inevitably subject to competition with other birds in nature. In order to express the vigilance behavior, BSA considers that birds with more food reserves have a greater probability of flying to the center of the swarm, but each bird does not fly directly to the center of the swarm. The process of the vigilance behavior can be represented as follows [33,34].

$$x_{i,j}^{t+1}=x_{i,j}^t+(M_j-x_{i,j}^t)·A_1·rand(0,1)+(p_{\mathrm{k},j}-x_{i,j}^t)·A_2·rand(-1,1)$$

(2)

$$A_1=a_1·\exp [-pFi{t}_i/(spFit+\epsilon )·N]$$

(3)

$$A_2=a_2·\exp [-(pFi{t}_i-pFi{t}_k)·pFi{t}_k·N/(|pFi{t}_i-pFi{t}_k|+\epsilon )/(spFit+\epsilon )]$$

(4)

where N represents the number of birds in the swarm, k takes a value randomly from the set {1, 2, …, N} and k ≠ i; a₁ and a₂ are constant numbers and are within the interval [0, 2]; $pFi{t}_i$ represents the fitness value of the ith bird, i.e., the food reserves of the optimal position the ith bird has gone through; $spFit={\displaystyle \sum _{i=1}^{N}pFi{t}_i}$ represents the sum of fitness values of all the birds; $\epsilon$ is a sufficiently small positive real number to avoid zero of the denominator; $M_j$ is the average value of the jth direction of the positions of all the birds in the swarm; rand(−1,1) represents a random number within interval [−1, 1] that satisfies the uniform distribution.

2.1.3. Migration Behavior of BSA

In order to avoid natural enemies and find new food spots to maintain the continuation of the swarm, the bird swarm will migrate to other areas and forage regularly. In the BSA, the birds are classified as producers and scroungers. Producers look for food directly, while the scroungers follow producers for food. The bird with the best position in the swarm is designated as one of the producers, and the other birds are designated as producers and scroungers, respectively. The ratio between the producers and scroungers is about 1:1 in the swarm. The producer’s behavior is expressed as follows.

$$x_{i,j}^{t+1}=x_{i,j}^t+x_{i,j}^t·rand(0,1)$$

(5)

where $rand(0,1)$ represents a random number between [0, 1] that satisfies the normal distribution. The scrounger’s behavior is expressed as follows.

$$x_{i,j}^{t+1}=x_{i,j}^t+(x_{k,j}^t-x_{i,j}^t)·F_L·rand(0,1)$$

(6)

where k is a random number taking value from the set {1, 2, 3, …}, and $k\ne i$; $F_L\in [0,2]$ is a random parameter, which means that the scrounger would follow the producer for food.

Each bird performs the above behaviors according to the following rules.

(1) Each bird in the swarm randomly selects foraging or vigilance behaviors. This random behavior is determined by the following procedures.

i. Set a threshold for each bird in each iteration, i.e., for the ith bird the threshold v_i can be determined by:

$$v_i=a·rand(0,1)+1-a$$

(7)

where a is a user-set parameter.

ii. Set a random number r_i for the ith bird in the iteration. If $r_i<v_i$, select the foraging behavior; otherwise, select the vigilance behavior.

(2) Each time BSA is iterated FQ times, a migration behavior will occur for the bird swarm. FQ is a positive integer. After migration, the status of the producer or scrounger of each bird has changed once.

2.2. The Bi-Level Distribution Network Planning Model

When using BSA to solve a problem, the status of each bird in the swarm is stored as a temporary variable in the system. If single-level planning is used, the number of birds that represent the variables of substation locating and network planning problems will increase rapidly as the scale of the problem rises, resulting in a rapid increase in the occupied storage resources. For most of the currently used heuristic algorithms, the position of a computing unit of the algorithm is updated via referring to the positions of other computing units, i.e., by calling the data of other computing units. In order to perform parallel computing for each computing unit, the positions of all computing units must be updated in one main process. On the other hand, due to the different nature of variables in the substation locating and sizing problem and in the network planning problem, the search speed of the corresponding heuristic algorithm is also different. Therefore, in order to reduce the significant increase of number of birds and reduce the occupancy of storage resources in large-scale planning problems, the DNP model is transformed into and solved by a bi-level optimization model in this work [36], wherein the upper-level focuses on the substation planning problem while the lower-level the network planning problems. For most of the heuristic algorithms including BSA, the upper and lower levels of programming models are solved by means of mutual iteration [37,38].

The DNP problem generally aims to minimize the investment cost for the planning years and estimated operating costs [39,40]. Thus, the upper-level optimization model of the bi-level optimization problem of DNP can be formulated as [18,25]:

$$\min C=C_S+C_M+C_W=(C_{Sf}+C_{Sv})\frac{r{(1+r)}^m}{{(1+r)}^m-1}+C_M+C_W$$

(8)

where r represents the discount rate; m represents the depreciation year of substations; C_M represents the estimated maintenance cost; C_S represents the cost of the substation; C_Sf represents the fixed cost for the substation; C_Sv represents the variable cost that varies with the capacity of the substation; C_W represents the cost of lines.

The lower-level optimization model of the bi-level optimization problem of DNP can be formulated as:

$$\min C_W=(C_{Wf}+C_{Wv})\frac{r{(1+r)}^m}{{(1+r)}^m-1}+C_{Wl}$$

(9)

where C_Wf represents the fixed cost of lines; C_Wv represents the variable cost of lines and is considered as varying with the line length; C_Wl represents the estimated cost of network losses, and can be calculated by [18]:

$$C_{Wl}={\beta }_l{\displaystyle \sum _{a=1}^N{\displaystyle \sum _{i\in J_a}{(P_i^a)}^2{L}_i^a}}$$

(10)

where $P_i^a$ represents the power demand of the ith load in the ath substation; $J_a$ represents the set of loads in the ath substation; $L_i^a$ represents the electrical distance from the power source to the ith load in the ath substation; N represent the number of substations. ${\beta }_l$ can be expressed as:

$${\beta }_l=\frac{{\beta }_1{\beta }_2{\beta }_3}{U_l^2{\cos }^2\phi }$$

(11)

where ${\beta }_1$ represents the electricity price in this concerned area, ${\beta }_2$ represents the resistance per kilometer of the outlet of the substation; ${\beta }_3$ represents the annual loss hours of the line; $U_l$ represents the line voltage; $\cos \phi$ represents the power factor.

The constraints for the bi-level DNP model are as follows.

$${\displaystyle \sum _{i\in J_a}{P}_i^a}\le S_{\max }^a\cos \phi$$

(12)

$$\underset{i\in J_a}{\max }{L}_i^a\le L_{\max }^a$$

(13)

Equation (12) represents the supply capability constraint. $S_{\max }^a$ represents the maximum allocated capacity for the new planned load. Equation (13) represents the constraint to the power supply radius. $L_{\max }^a$ represents the maximum power supply radius of the ath substation. Besides, the N-1 security constraint should also be met. The loop power-supply network is of high reliability and itself can meet the requirements of the line N-1 security. Therefore, the N-1 security can be checked via offline of a single substation in the proposed DNP model.

It should be noted that for the sake of simplicity and focusing mainly on the joint planning of distribution systems, the uncertainty of load demands in the planning period is not considered in the proposed bi-level model. Robust optimization is a widely used uncertainty tackling method and will be applied in our future works to manage the uncertainty of the DNP problem [41,42,43].

2.3. BSA-Based Optimization Procedures of the Proposed Bi-Level Optimization Model of DNP

2.3.1. Optimization Procedure of the Upper-Level DNP Model

The upper-level DNP model can be optimized by the following procedures.

(1) Vectorize in numerical order the capacities of the substation to be built and the substation to be expanded in the planned area as a new/expanded vector whose elements are positive real numbers. Number the candidate locations of the substations to be built and form a location vector whose elements are binary variables. The two vectors form the input vector for the upper-level model.

(2) Initially, the sum of elements in the new/expanded vector is set to be equal to the sum of the capacities of all the substations to be built and expanded, and the sum of elements in the location vector to $n_1$ the number of substations to be built. Each update in the optimization process should ensure the above two equations; otherwise:

i. Correct the new/expanded vector $\overrightarrow{V}=(V_1,V_2,\dots ,V_{n_1+n_2})$, where $n_2$ is the number of the substations to be expanded, by the following steps.

Step 1: set all the elements less than zero in $\overrightarrow{V}$ as zeros;

Step 2: correct $V_i(i=1,2,\dots ,n_1+n_2)$ by:

$$V_i^{\ast }=\frac{V_i}{{\displaystyle \sum _{i=1}^{n_1+n_2}{V}_i}}{V}_T$$

(14)

where $V_T$ represents the overall capacities of the substations to be built and expanded.

ii. Correct the location vector $\overrightarrow{B}=(B_1,B_2,\dots ,B_{n_1+n_2})$ by the following equation.

$$B_j^{\ast }=\{\begin{array}{ll}0& B_j<\max (B_j)(j=1,2,\dots ,n_1)\\ 1& B_j=\max (B_j)(j=1,2,\dots ,n_1)\end{array}$$

(15)

2.3.2. Optimization Procedure of the Lower-Level DNP Model

The lower-level DNP model can be optimized by the following procedures.

Number each load planned for building, and then form a decision vector of loads. Each load in the vector has two decision variables. The first variable represents which two substations the load is connected to, while the second represents which connected substation supplies power to the load. In order for BSA to have a certain searching direction, the first decision variable is specified as follows.

The value of the variable is 1, 2, …, $C(N,2)$, where N is the total number of substations, including the existing substations (expanded and to be expanded) and the planned substations to be built; C is the operator for the combination number, i.e., $C(N,2)=N(N-1)/2$. If the sum of the distances from a load to two certain substations is the minimum, then the value of this variable at that load is 1; if it is only larger than the minimum but smaller than the other sum of distances, the value of this variable at that load is 2; other situations can be done in the same manner. All values of the variables are initialized to be 1. Each update during the optimization process should guarantee that the value of the first variable is in the range [1, $C(N,2)$], and the value of the second decision variable is 1 or 2. Otherwise, the decision vector $\overrightarrow{D}=(D_1,D_2,\dots ,D_m)$ is corrected as follows:

Step 1: set all elements in $\overrightarrow{D}$ less than 0 as 0, and set elements greater than $D_{\max }$ the maximum of the codomain to be $D_{\max }$.

Step 2: correct the elements in $\overrightarrow{D}$ by:

$$D_i^{\ast }=\{\begin{array}{ll}{D}_i-\left\{D_i\right\}+1& D_i<D_{\max }(i=1,2,\dots ,m)\\ D_i& D_i=D_{\max }(i=1,2,\dots ,m)\end{array}$$

(16)

where $\left\{D_i\right\}$ represents the decimal part of $D_i$.

When calculating the objective function, the two decision variables are converted into the number of the two substations connected to each load and the power supply substation. Then the length of the line under different connection combinations is calculated to determine the connection order of the loads connected to the two same substations. Figure 1 shows two different connection orders of loads.

For the single loop network, the line length can be approximately regarded as the sum of the distance between the substation and the directly connected loads and the distance between the directly connected loads; for the double loop network, the line length twice the above summation.

The Manhattan distance is utilized to calculate the distances in this work [44], as:

$$d_{i,j}=\left|x_i-x_j\right|+\left|y_i-y_j\right|$$

(17)

where $d_{i,j}$ represents the distance between the load (or substation) in $(x_i,x_j)$ to the load in $(y_i,y_j)$.

When connecting to the same substation and load, a connection mode with a longer line length leads to increase of the power supply radius, increase of network losses, and decrease of power supply reliability. Therefore, the connection mode with the shortest distance to connect the concerned substation and load is selected as the network planning scheme.

Each planning scheme should meet constraints (12) and (13). In order to check the N-1 security, the substation supplying a certain load is cut off and the load is transferred to the contralateral substation to which that load can be connected. If all the transferred loads can be supplied under a given operating condition, the N-1 security can be guaranteed.

The BSA-based optimization procedures for the proposed joint planning of substations and lines in the distribution network are shown in Figure 2.

2.3.3. The Master-Slave Architecture based Parallel BSA for the Bi-Level DNP Optimization

Conventionally, the data volume in the processes of distribution network substations and network planning is less than terabyte (TB) or petabyte (PB) levels, thus it is not economical to use Hadoop for calculation. However, when calculating the objectives of the bi-level planning model, a large number of calculations of the line lengths of different load connection orders is required. In addition, the planning schemes under the concerned operating conditions should also be checked, leading to a data-intensive problem. Therefore, based on the idea of parallel computing of big data theory, parallel BSA is proposed to increase the computational efficiency.

In this work, master-slave parallel architecture is adopted, and the complex calculation processes are allocated to each slave process to reduce the calculation time. The master process controls the entire calculations, as well as a bulletin board that records the bird behaviors in the BSA. The slave processes are responsible for computing the objective function, security checking, and forming the parallel BSA with master-slave structure. The proposed master-slave architecture based parallel BSA for the bi-level DNP optimization is shown in Figure 3.

3. Simulations and Discussions

An actual area in China with a distribution system to be planned is used as an example for demonstrating the effectiveness of the BSA-based algorithm for joint planning of substations and lines in the distribution system. A coordinate corresponding to actual geographical locations with unit km is established. There are currently three substations in the area. The substations 1, 2, and 3 are with coordinates of (1.00, 4.70), (0.45, 0.70), (4.15, 1.25), and with capacities of 20 MVA, 20 MVA, and 15 MVA to supply new added loads, respectively. According to load forecasting, power balance and load capacity requirements, a substation is determined to be built in this area, and substations 2 and 3 are determined to be expanded. The overall to be built and to be expanded capacity is 80 MVA. The candidate locations of the substation to be built are: location 1 at (3.00, 3.50), location 2 at (3.75, 4.15), and location 3 at (4.60, 3.40). According to reference [45] and other regional planning reports and guidelines, the fixed costs for the two substations to be expanded are all 7.5 million CNY. The fixed costs for the substation at candidate locations 1, 2, and 3 are 21.2, 21.05, and 21.25 million CNY, respectively. The variable cost is 45,000 CNY per MVA.

According to the load forecasting results in this area, 10 loads need to be built. The coordinates of the loads numbered from 1 to 10 are (1.00, 3.50), (1.00, 2.30), (1.00, 1.25), (1.80, 1.40), (2.25, 2.25), (2.00, 4.15), (3.10, 2.15), (3.00, 4.10), (4.25, 4.20), (3.90, 2.40), respectively, and the loads are 2.5 MW, 4 MW, 3 MW, 4 MW, 2.5 MW, 3 MW, 3.5 MW, 4 MW, 3 MW, 2.5 MW, respectively.

In the proposed BSA-based bi-level optimization method, the internal iterations I₂ and I₃ of the bi-level planning model are set as 50. The number of birds in the upper and lower levels is 40 and 90 respectively. Iteration I₁ between the two levels is 500. The overall planning model runs 150 times. The optimization results are as follow. The annual cost of the optimized planning scheme is 6,430,980 CNY. The total length of lines is 18.25 km. Substations 1 and 3 will not be expanded, while substation 2 is expanded with 29 MW and the substation to be built is at location 2 with 51 MW. The traditional single level optimization method first designates which substation to supply power to the load and then determines the planning scheme. By the traditional single level optimization method [20], the annual cost is 6,573,098 CNY, and the total length of lines is 24.80 km. These two planning schemes are shown in Figure 4 (all circuit breakers are not illustrated). Figure 5 shows the iteration results of the joint planning of substations and lines in the distribution systems.

It can be seen from the results in Figure 5 that the annual cost of the proposed BSA-based bi-level optimization method considering the contralateral substation is significantly lower than that of the traditional single level optimization method, which verifies the effectiveness of the proposed BSA-based bi-level optimization method. Besides, the descending trend of the annual cost appears to be steadier after 200 iterations, which indicates that a large number of iterative processes are needed. As a result, it seems necessary to introduce the parallel BSA to improve the computing performance.

In order to further demonstrate the validity of the proposed parallel BSA, the proposed DNP model is run on two computers. The details of the two computers are shown as follows.

PC1: Intel^® Core(TM) i5-7300HQ CPU @ 2.50 GH, 8 GB 2400 MHZ DDR4 memory (Hynix, Wuxi, China), parallel computing environment: MATLAB 2016a (MathWorks, Natick, MA, USA).

PC2: Inter^® Core(TM) i5-4590HQ CPU @ 2.50 GHz, 4 GB 1600 MHZ DDR3 memory (Hynix, Wuxi, China), parallel computing environment: MATLAB 2013a (MathWorks, Natick, MA, USA) with at most 12 slave processes.

The indexes of speedup factor S_n (the ratio of the computing time with parallel strategy to that without parallel strategy) and parallel computing efficiency E_n (the ratio of speedup factor to the number of processes) are utilized to evaluate the algorithm performance [46]. The results are shown in

Table 1. The indexes of speedup factor and parallel computing efficiency for the proposed bi-level distribution network planning (DNP) optimization.

Process No.	Sn		En		Process No.	Sn		En
	PC1	PC2	PC1	PC2		PC1	PC2	PC1	PC2
2	0.9155	0.8963	0.4578	0.4481	8	1.5885	2.142	0.1986	0.2678
3	2.0192	1.5798	0.6731	0.5266	9	1.4092	2.0896	0.1566	0.2322
4	2.2797	2.0994	0.5699	0.5249	10	1.3087	2.0347	0.1309	0.2035
5	2.2121	2.4925	0.4424	0.4985	11	1.2149	1.9679	0.1104	0.1789
6	1.9657	2.23	0.3276	0.3717	12	1.1147	1.867	0.0929	0.1556
7	1.7721	2.1487	0.2532	0.307	13	1.0242	1.6064	0.0788	0.1236

.

When the number of processes is 2 (that is, one master process and one slave process), the speedup factors of the two computers are less than 1, i.e., the efficiency is lower than that when the master-slave parallel structure is not used. Since the tasks performed by the main process and the slave process are different and the processes are not executed simultaneously, the execution structure in the case of two processes is the same as that in the serial computing. The decrease of efficiency is mainly caused by the communication between the master and slave processes. When the number of processes is greater than 2, that is, when there are multiple slave processes, the speedup factors of both computers are greater than 1, indicating that the parallel algorithm is faster than the serial one. The maximum speedup factors of the two computers exceed 2, which means that parallel computing can save more than half of the time and it has a remarkable acceleration performance. As the number of processes increases, the speedup factor increases first and then decreases. This is because when the number of processes is significantly more than the number of computer processors, the hardware condition of a computer cannot accommodate all the processes running at the highest speed simultaneously, hence resulting in some processes being idle. Therefore, the actual configuration of the hardware needs to be considered when implementing the parallel strategy.

4. Conclusions

A bi-level model for the joint planning of substations and lines is proposed for urban distribution systems. The model is solved by the well-established BSA that incorporates parallel computing through a master slave architecture. Simulation results and comparisons show that the proposed BSA-based bi-level joint planning method for the distribution system can obtain better planning schemes, and the proposed parallel BSA can effectively increase the calculation speed and reduce the running time of the DNP model.