Optimal Feeder Routing and DG Placement Using Kruskal’s Algorithm

Optimal Feeder Routing and DG Placement Using Kruskal’s Algorithm

Gholam-Reza Kamyab

Department of Electrical Engineering, Gonabad Branch, Islamic Azad University, Gonabad 9691664791, Iran

Corresponding Author Email: 
kamyab@iau-gonabad.ac.ir
Page: 
71-78
|
DOI: 
https://doi.org/10.18280/ejee.220109
Received: 
5 August 2019
|
Accepted: 
10 January 2020
|
Published: 
15 March 2020
| Citation

OPEN ACCESS

Abstract: 

In this paper, the optimal feeder routing along with optimal distributed generator placement is formulated as an optimization problem. In this problem, the total cost of capital recovery, supply interruption and energy losses are minimized. Also, line loading capacity and bus voltage constraints are applied. By proposing a novel method to code the solutions of the optimization problem with the facilitation obtained from the utilization of the Kruskal's algorithm, it is guaranteed that graphs of all solutions would always be spanning trees. The main result of the implementation of this method within meta-heuristic algorithms is to limit the search space to radial networks leading to snap quicker answers with higher degree of optimality. A distribution network with a 24 load points and 42 candidate branches is used as a baseline to indicate the effectiveness of the proposed method which was tested using three meta-heuristic algorithms including genetic algorithm, particle swarm optimization and simulated annealing.

Keywords: 

electrical distribution network planning, distribution feeder routing, distributed generators

1. Introduction

The feeder routing is one of the main parts of distribution system planning, aiming at determining number of feeders and their routes to connect demand locations with substations undertaking the satisfaction of technical and physical constraints in a way that the demand is met at minimum cost. The growth of peak demand, low reliability, and high-power losses are major problems of distribution networks. To deal with these problems, the use of distributed generators (DGs) in distribution networks has considerably grown to satisfy the needs for providing load locally, reduce the peak demand of distribution network, reduce power losses, increase reliability, and improve voltage profile. At the presence of distributed generators, feeder routing would have more significant role because DGs have great effect on determining the optimal route. In this paper, feeder routing and DG placement issues are considered simultaneously.

Because distribution feeder routing is a large-scale non-convex problem which involves many variables and constraints, the preferred solution mostly contains meta-heuristic optimization approaches rather than mathematical techniques. Since distribution networks are generally used radially, one of the main constraints of the problem of distribution feeder routing is the radiality of the feeding paths of all load points. This is a hard limit discrete constraint. It is therefore recommended not to use the penalty concept at optimization process.

Generally, the problem of optimal routing of distribution feeders, independently or in combination with other issues of the distribution network planning problem, such as determining the location and optimal size of substations, has been considered in a variety of studies, some of which are referred to hereafter. The combination of the steepest descent approach and the simulated annealing technique is used for optimal planning of radial distribution networks, taking the uncertainties of the inputs and the various models of determining the interruption costs into account [1]. In this paper, only the connectivity of network configuration is checked using a network connectivity matrix. A stochastic model for the expansion planning of an active distribution network comprising shared electric vehicle charging stations, solar based distributed generations, and battery energy storage systems is presented [2]. A mixed integer linear programming model is presented for short-term expansion planning of power distribution systems [3, 4]. The model is able to solve the problems of optimal allocation of voltage regulators and capacitor banks, optimal reconductoring of distribution networks and determining optimal tap position of distribution transformers. A practical methodology based on georeferenced data for planning a resilient underground distribution network is presented [5]. In this paper, a modified-prim algorithm is used to determine optimal location of distribution transformers and to find the minimal path of the medium voltage network. A multi-objective joint planning model for active distribution network planning is presented [6]. In this paper, using the multi-objective natural aggregation algorithm, the location and size of the electric vehicle charging stations, renewable energy sources, battery energy storage system, and distribution network expansion schemes are determined. By using an improved harmony search algorithm, optimal location and size of distribution substations and feeders are investigated in the presence of distributed generators [7]. In this paper, in order to keep the radial structure of distribution network, the simultaneous satisfaction of the two constraints is evaluated: first, the determinant of the branch-node matrix must be zero, and second, the number of branches should be less than the number of nodes by one. An adaptive genetic algorithm is applied to determine the optimal site and size of sub-transmission substations and renewable and non-renewable distributed generations associated with optimal feeder routing [8]. In this paper, a method is introduced based on the rank of the Laplacian matrix of bus incidence matrix for checking the radiality of networks with a desired number of HV/MV substations. A stochastic optimization algorithm is provided to find the optimal feeder routing considering the stochastic variations of electric vehicle charging stations as well as photovoltaic and wind distributed generators [9]. In this paper, the radial structure of feeders is not considered. The simulated annealing algorithm is used for optimal planning of new urban distribution networks based on the selection of the best subset of paths providing back-feed from the entire path set generated for the available cable routes [10]. In this paper, the interconnecting and/or ring (not radial) feeders are searched. Using genetic algorithm, the planning of a hybrid AC/DC distribution system involves determining the optimal location and size of the AC/DC distribution substations, as well as the length and capacity and path of the AC/DC feeders on both low and medium voltage sides [11]. In this paper, the Minimum Spanning Tree method is used for routing feeders on both the MV and LV sides of the distribution system. A biogeography-based optimization is employed to find the optimal location and rating of distribution transformers and substations, as well as the type and route of medium and low voltage feeders based on uniform or non-uniform load density [12]. The Imperialist Competitive Algorithm (ICA) is used to find an optimal route of medium-voltage (MV) feeders at the presence of load forecasting uncertainties in multistage mode [13]. The presented solution uses two features of a tree in a graph to check the radial structure of the network in any iteration of ICA. A combined methodology [14] implemented by the particle swarm optimization (PSO) technique for the distribution network expansion planning, considering DGs in the presence of load and price uncertainties under electricity market environment has been presented; however they have ignored any expansion plan that does not have a radial structure. A multistage expansion planning framework [15] has been proposed to find optimal sizing, siting and timing of HV substation and medium voltage feeders’ routes using an imperialist competitive algorithm (ICA) with an efficient coding. In their presented method, during the optimization process to maintain the radial structure of a network, firstly, the vectors (countries) of the ICA are manipulated so that the number of their “1” do not change, and secondly, by executing a subroutine only solutions that do not have a loop are accepted, and the other solutions are removed from the simulation process. A graph-theoretic [16] based feeder routing of the given power distribution system is observed and the impact of DG integration on the feeder routing have been proposed. In their approach firstly, using the proposed methodology, a set of near optimal solutions has been originated and then an optimal solution from the set of near optimal solutions is selected by running the modified load flow program for each of the near optimal solutions. The particle swarm optimization technique [17] is used to determine the optimal location and size of MV/LV distribution substations, and a modified-Prim algorithm is used to find the optimum feeder routing of LV and MV networks. A multi-objective planning algorithm [18] using dynamic programming is suggested to determine the optimal feeder routes and branch conductor sizes with simultaneous optimization of cost and reliability. Their proposed method guarantees that the radiality constraint is never violated since the network nodes are connected one by one using dynamic programming; however, because the dynamic programming suffers heavily from the “curse of dimensionality”, it limits its application to small networks. A modified bacterial foraging technique [19] for optimal feeder routing in radial distribution system planning has been used to provide a solution rapidly with a better probability of achieving a global optimal solution. A direct search technique [20, 21] is applied for optimum feeder routing in radial distribution system. In these papers, the concept of principle of optimality theorem is effectively used to make the direct method more computationally efficient, reducing total numbers of radial paths. A new technique [22] employing discrete particle swarm optimization (DPSO) method is presented to find optimally distribution transformer and substation locations and ratings, as well as, the route and type of Medium Voltage (MV) and Low Voltage (LV) feeders. An improved genetic algorithm [23] is applied to determine optimal sizing and locating of the high and medium voltage substations, as well as medium voltage feeders routing. They use a subroutine to check the loop conditions in the network at any iteration according to crossover and mutation processes. Optimal planning of radial distribution network [24] is done by employing simulated annealing technique and the steepest descent approach is used to generate the initial solution for the optimization procedure. They check the graph connectivity of new solutions by evaluating a network connectivity matrix. The ant colony system algorithm (ACS) [25] is adapted to find the solution of the optimal planning problem of primary distribution circuits. They enforce the radial characteristic of the network by a proposed branch selection approach.

The main challenge of the routing of distribution feeders is that the solution (network configuration) should be radial. On the other hand, using the Kruskal's algorithm, we can find the minimum spanning tree for a connected weighted graph. Therefore, in this paper, first a coding method for each solution is proposed. Using this coding together with the Kruskal's algorithm, we can limit the optimal solution search space to no more than the radial (tree) distribution solutions. Then, the capability of the proposed coding is examined with its application in the implementation of the three meta-heuristic algorithms (GA, PSO and SA) to devise a comprehensive solution method for the feeder routing and DG placement problems altogether.

At the rest of the paper, first, in section 2, the problem is formulated. Then, in the third section, problem-solving algorithms are introduced. In Section 4, the proposed method for coding the solution of the problem and in Section 5, its fitness function is presented. Section 6, contains the results of implementing the proposed method on a distribution system. Finally, in the seventh section, the paper ends with expressing the conclusion of the study.

2. Problem Formulation

In this paper, optimal feeder routing along with DG placement is defined as an optimization problem in which the objective function is the minimized total cost which satisfies the specified constraints. In this section, the objective function and the constraints and the modeling of DGs are introduced. 

2.1 Objective function

Eq. (1) introduces the objective function of the optimization problem [21, 24]:

$c_{t}=c_{c}+c_{i}+c_{i}$       (1)

where, $C_{t}, C_{C}, C_{i}$ and $C_{l}$ are the total annual cost, capital recovery fixed cost, the cost of supply interruption and the cost of energy losses, respectively.

The capital recovery cost can be calculated as [21, 24]:

$c_{c}=g \sum_{k \in M} c_{k}$      (2)

where, $g$ is the capital recovery rate of the fixed cost and $C_{k}$ is the cost of the branch $k$ of the main feeder. It should be noted that costs of branches originating from the source substation include both the lines and the corresponding substation costs. M stands for the set of branches of a network configuration that has been investigated.

Considering the facts that in radial networks there is no alternative supply route and the outage of a branch interrupts the delivery to all consumers supplied through it, the cost of supply interruption can be obtained by Eq. (3) [21, 24]:

$c_{i}=c_{i p} \alpha d \sum_{k \in M} \lambda_{k} R e\left\{I_{k}\right\} \sqrt{3} U_{r}$       (3)

where, $c_{i p}, \alpha, d, \lambda_{k}, I_{k} \operatorname{and} U_{r}$ indicate the cost per unit of energy not delivered, the load factor, the repair duration, the branch failure rate, the branch current at peak load and the network rated voltage, respectively.

The cost of energy losses is calculated by Eq. (4):

$C_{l}=\mathbf{8 7 6 0 c}_{l p} \boldsymbol{\beta} \sum_{k \in M} \boldsymbol{r}_{k}\left|\boldsymbol{I}_{k}\right|^{2}$       (4)

where, $c_{l p}, r_{k}$ and $I_{k}$ are the cost per unit of energy lost (the cost of one watt-hour of energy loss), the branch resistance and the branch current at peak load, respectively.

The coefficient β is the loss factor defined by (5) in terms of the load factor ($\alpha$):

$\beta=0.15 \alpha+0.85 \alpha^{2}$       (5)

2.2 Constraints

The constraints to be satisfied are:

i) Loading capacity constraints: The current which passes through a branch of the network should be within its thermal capacity limit:

$\left|I_{k}\right| \leq\left|I_{k \max }\right| \cdots \cdots \cdots \cdot \forall \cdot k \in M$       (6)

where, $\left|I_{k}\right|$ is the current magnitude of the branch k and $\left|I_{k \max }\right|$ is the upper bound of $\left|I_{k}\right|$. The current magnitudes of the network branches are calculated by performing load flow.

ii) Bus voltage constraints: The voltage of a bus must be within its allowable limits:

$V_{i m i n} \leq\left|V_{i}\right| \leq V_{i m a x}$       (7)

where, $\cdot\left|V_{i}\right|$ is the voltage magnitude of bus i and $V_{i m i n}$ and $V_{i m a x}$ are the upper and lower bounds of $\left[V_{i}\right]$ respectively. The voltage magnitudes of the network buses are calculated by performing load flow.

iii) Radiality constraint: Since distribution networks are operated radially, one of the main constraints of the problem is that the network structure should be radial. In other words, the graph of the network should be a spanning tree, which is a tree that connects all nodes (buses) and has no loops. This is a hard limit discrete constraint so the use of penalty concept within the optimization process is not recommended [15].

2.3 Modeling of distributed generators

The distributed generator unit in each bus is modeled as negative PQ load. Because the distributed generator injects active power into a network, the active power of the PQ load is considered to be a constant and a negative value. Since it is assumed here that the distributed generator operates with a unity power factor, the reactive power of the PQ load is considered as constant value of zero.

3. The Problem Solving Method

Given that the problem of the optimal feeder routing along with DG placement is a complex and combinatorial problem, in this paper a meta-heuristic optimization approach is used to solve it. Therefore, the use of three meta-heuristic algorithms including genetic algorithm (GA), the particle swarm optimization (PSO) algorithm, and the simulated annealing (SA) algorithm are tested. Before applying these algorithms, a possible solution of the problem must first be encoded as a string (vector) of numbers. Also a fitness function that expresses the degree of achieving to the main objective of the problem and the level of satisfying the constraints must be defined to evaluate each solution. After that, the implementation of the meta-heuristic algorithm begins by generating an initial solution or a population of initial solutions and continues by iterating an iterative process. At each iteration round, by applying the particular operators of the corresponding algorithm to the current population/solution, a new population/solution is generated which is an improvement regarding the previous one in terms of the fitness function. The iterative process of the algorithm is stopped when a predetermined stop condition is met. Then the best solution by far is introduced as the final optimal solution.

The process of generating new population/solution depends on the algorithm used. In genetic algorithm, the population of new solutions is generated by applying selection, crossover and mutation operators on the current population. In PSO algorithm, the new population of particles (solutions) is generated by updating the velocity and position values of the current population particles. The degree by which any particle will be updated depends on the best position obtained by the particle itself and the best global position obtained by all the particles at the previous iterations [14]. In SA algorithm, new solution at any iteration is generated in the neighborhood of the current solution by a certain neighborhood structure. Better solutions are always accepted, and the new solutions which are not better are also accepted with some probabilities to avoid falling into local optimal solution.

In the optimal distribution feeder routing, each solution is a configuration of the network, the traditional coding method for a configuration is to allocate a bit to each candidate branch (line) of the under-study network. Having “one” at any of corresponding bits indicates that the corresponding branch is a member of the corresponding network configuration while “Zero” means that the corresponding branch does not exist there.

To overcome the distribution feeder routing problem the main challenge is that the optimal solution (network configuration) should be radial, while if the traditional coding method is used to code the solutions (network configurations), most of the search space is formed by non-radial configurations (unacceptable solutions). In this paper, however, using the Kruskal's algorithm, a method is proposed for coding the distribution network configuration, which limits the search space to radial configurations only.

4. Coding Solution

The solution to the problem should specify the route of distribution feeders and the location of the DGs. So, each solution is coded by a vector X as follows:

$X^{T}=\left[\begin{array}{ll}w^{T} & D^{T}\end{array}\right]=[\underbrace{w_{1} \quad w_{2} \quad \cdots \quad w_{n b r}}_{\text {feeder routes }} / \underbrace{d_{1} \quad d_{2} \quad \ldots \quad d_{n D G}}_{D G \text { loactions }}]$   (8)

The vector X consists of two parts. The first part which contains the vector $w^{T}$, encodes the route of the distribution network, and the second part, which includes the vector $D^{T}$, encodes the location of the DGs. The element $w_{i}$, which is a number within the interval of [0,1], represents the weight of the candidate branch i within the execution of Kruskal's algorithm. The purpose of this research is to code routes so that using Kruskal's algorithm in graph theory, the search operation is performed only in the space of radial paths. In this case, high-quality optimal solutions are easily available. The element $d_{i}$ represents the bus number which is used to be a candidate to install i-th DG, and therefore it is an integer number between one and the number of candidate buses.

Using Kruskal's algorithm, a radial solution corresponding to the values of the elements of the vector $w^{T}$ is generated. Kruskal's algorithm is a greedy algorithm in graph theory, which is used to find a minimum spanning tree for a connected edge-weighted graph. The minimum spanning tree (MST) of a connected, edge-weighted graph is a subset of the edges of the graph that connects all the vertices together, without any cycles and with the minimized total edge weight. The process of using the Kruskal's algorithm to generate a radial solution corresponding to the weight vector w is as follows:

1- All candidate branches are arranged in an ascending order by their weights to form an ordered set, called set A.

2- The set of branches of the radial network corresponding to the weight vector w, called set B, is initially set to empty.

3- Moving forward along set A, for each member, if the union of branches in set B and the current member of A do not create any cycles, then the selected branch is added to the set B.

4- The branches of the resultant set B provide the radial solution corresponding to the vector w.

To clarify the issue, the implementation of Kruskal's algorithm is illustrated with a simple example.

Example: Consider the simple network shown in stage 1 of Figure 1, which has four nodes and five candidate branches with numbers 1-5. Suppose the weights of the vector encoding the routes of this network are $W^{T}=$[0.7 0.9 0.4 0.1 0.6]. The steps needed to find the corresponding network with the vector W are as follows:

1- Because the order of ascending weights of candidate branches are {$w_{4}=0.1, w_{3}=0.4, w_{5}=0.6, w_{1}=0.7, w_{2}=0.9${, the result of sorting the candidate branches will be the set A = {4, 3, 5, 1, 2}.

2- We initially set the set B to empty. So B = {}. B is the set of branches of the radial network corresponding to the weight vector W.

3- We select the first branch of set A, which is branch 4. If this branch is added to set B, the stage 2 of Figure 1 would be the outcome that does not produce any cycles. So we add this branch to set B, and so B = {4}.

4- We select the second branch of set A, which is branch 3. If branch 3 is added to the branches of set B, the stage 3 of Figure 1 would be the result that does not produce any cycles. So we add branch 3 to set B, and so B = {4, 3}.

5- We select the third member of set A, which is branch 5. If branch 5 is added to set B, the stage 4 of Figure 1 would be the upshot which generates a cycle. Therefore, we do not add branch 5 to set B.

6- We select the fourth member of set A, which is branch 1. If it is added to set B, the stage 5 Figure 1 would be the outcome that does not create any cycles. So we add branch 1 to set B, which means B = {4, 3, 1}.

7- We select the fifth member of set A, which is branch 2. Adding this branch to set B will lead us to the stage 6 of Figure 1 which generates a cycle. Thus, we do not add branch 5 to set B.

      8- Now, the final radial solution corresponding to route W is set B = {4, 3, 1}, which is shown in the stage 7 of Figure 1.

Figure 1. Graphs of the stages to reach a radial feeding path for a hypothetical example

5. Fitness Function and Generation of Possible Solution

In the meta-heuristic algorithms, the quality of each solution is evaluated by a fitness function. The fitness function must be defined in a way that it can show how much each solution can satisfy the main goal and the constraints of the problem. In the current subject, the goal is to minimize the cost function defined in Eq. (1). The problem constraints are the load capacity constraints and the bus voltage constraints defined in relations 6 and 7, respectively. Therefore, the fitness function for each solution is defined in relation 9, which must be minimized by a meta-heuristic algorithm.

$f(X)=\left\{\begin{array}{ccc}C_{t}(X) & \text { if } & \text { no limit violation } \\ C_{t}(X)+\gamma & \text { if } & \text { at least one limit violation }\end{array}\right.$ (9)

where, X denotes a solution, that is, the path of the distribution network feeders and the location of the DGs. f(X) is the fitness function of solution X. $C_{t}(X)$ is sum of the total costs introduced in Eq. (1); γ is a penalty factor (a large number). The “Limits” are the load capacity constraints defined in Eq. (6) or the bus voltage constraints defined in Eq. (7).

The fitness function in Eq. (9) is defined so that if none of the load capacity constraints or the bus voltage constraints are violated, then the value of the fitness function is equal to $C_{t}(X)$. However, if one of these constraints is violated, the value of the fitness function is equal to $C_{t}(X)+\gamma$, which is a large value, and therefore the meta-heuristic algorithm will not choose these types of solutions as the optimal solution.

To calculate the fitness function of each solution X, the following steps must be taken:

1- Determine the radial network corresponding to the part of the vector X using the Kruskal's algorithm.

2- Apply DG powers in load buses corresponding to the part D of the vector X .

3- Perform the load flow. In this research, since the network is always radial type, the forward-backward load flow, which is special for radial distribution networks and has a high computational speed, is used.

4- Calculate the total cost ($C_{t}(X)$) from Eq. (1) using the load flow results.

5- Check the load capacity and bus voltage constraints according to the load flow results.

6- Determine the value of the fitness function using Eq. (9).

It should be noted that since all solutions are always produced in a way that the corresponding network would be radial, the radiality constraint is automatically provided.

6. Simulation Results

In this section, the effectiveness of the proposed method is studied on a rural 10kV network reported in the study [21, 24]. Figure 2 shows the graph of available network routes. The network has 24 load points (transformers 10 kV/0.4 kV) and 42 available branches for their supply from the substation 35 kV/10.5 kV at node 1. To check the effects of DGs, four DG units of equal capacity are considered with a total DG capacity of 1.33 MVA at unity power factor. The predetermined locations of the DGs according to reference [16] are in nodes 7, 8, 9 and 10. But we obtain the optimal locations of these DGs and compare them with the predetermined locations. The details of consumption at load points, length of graph branches, line data and load data can be obtained in tables I, II and III of reference [24]. Cost and complementary load data have been given in Table 1.

The substation equipment and building capital cost per outgoing line is 75 k$. This amount is added to the costs of all branches directly connected to the source substation. The upper and lower bounds of voltages in all the buses are assumed to be 0.95 to 1.05 per unit respectively. The penalty factor in fitness function (γ) was set to 1×106.

To verify the effectiveness of the proposed method, multiple simulations were performed by three GA, PSO and SA algorithms in Matlab environment, and the comparative results are presented in the remainder of this section. The values of some parameters used for the simulation of the algorithms are given in Table 2. It is mentionable that the population size and number of generations in GA and PSO algorithms and the number of iterations in SA algorithm are chosen large enough making sure that in all three algorithms the optimal solution is obtained after complete convergence.

Figure 2. Graph of available supply routes for the rural 10kV network

Table 1. Cost coefficients and complementary load data

Parameter

Value

Power factor at all load points

0.9

Load factor (α) at all load points

0.6

Investment cost per kilometer of each branch (ck)

15000 US$/Km

cost per unit of energy not delivered (cip)

4 US$/KWh

cost per unit of energy lost (clp)

0.1 US$/KWh

the capital recovery rate of the fixed cost (g)

0.1

 

Table 2. The values of some parameters for the implementation of GA, PSO and SA

Parameter

Value

Population size for GA and PSO

100

Maximum generations for GA

100

Maximum generations for PSO

200

Number of iterations for SA

10,000

6.1 Comparison between Kruskal's coding and traditional coding

In the previous sections, the Kruskal’s algorithm was proposed to code the distribution network configurations to solve the distribution feeder routing problem. In this section, this proposed coding method is compared with the traditional coding method. Here since we just want to compare the effects of these coding methods on the feeder routing, in this case, we do not consider any distributed generator for the system. The results of solving the distribution feeder routing problem using three algorithms GA, PSO and SA with both the coding methods are given in Table 3; where the best values of the fitness function obtained from the implementation of 10 times simulations for random number generator seeds 0-9 for all three algorithms and both the coding methods are presented.

It is observed carefully in Table 3 that in all the three algorithms, when using traditional coding, the value of the fitness function is very large, due to the fact that one or more of the constraints including bus voltage constraints, loading capacity constraints and/or radial constraint are not satisfied. Therefore, the traditional coding method does not work well for any of the three algorithms. However, when the proposed Kruskal’s method is used, all three values of the fitness function are small, which means that the solutions obtained by all the three algorithms satisfy all constraints. Meanwhile, GA and SA methods have reached the same solution which is better than the solution of the PSO algorithm because the amount of their fitness function is lower. So, it can be concluded that while the use of traditional coding method with all the three algorithms has not even been able to achieve a feasible solution, the use of Kruskal's coding method looks very effective to solve the distribution feeder routing problem. Therefore, the Kruskal’s coding method is used in the rest of the study.

Table 3. Comparison of routing results to two coding methods with three algorithms

Algorithm

Fitness (×104)

Traditional coding

Kruskal’s coding

GA

107.95

3.4038

PSO

107.67

3.5411

SA

106.30

3.4038

6.2 Comparison of the algorithms

Table 4 shows the results obtained from solving the optimal feeder routing and DG placement problem for the following three scenarios and for the above-mentioned 25-bus distribution network with all the three algorithms. In this table, the best value of the fitness function obtained from the implementation of 10 times simulations for the random number generator seed 0 to 9 for each of the three PSO, GA and SA algorithms and with the Kruskal’s coding method is given.

Scenario 1) It is assumed that there is no DG and only the feeder routing problem is solved.

Scenario 2) It is assumed that DGs are installed at proposed locations in reference [16], i.e., at nodes 7, 8, 9, and 10, and only the feeder routing problem is solved.

Scenario 3) The distribution feeder routing problem along with the optimal placement of the four DGs is simultaneously solved.

Considering Table 4, the following points can be deduced:

  • It is observed that all values obtained for the fitness function in Table 4 are not very large, which means that according to Eq. (9), the amount of the penalty factor (γ) does not have any effect on the value of the fitness function. In other words, the value of the cost function is equal to the total cost. Consequently, the solutions obtained by Kruskal’s coding at all three scenarios and for all three PSO, GA, and SA algorithms have satisfied all the constraints.
  • By comparing the results of the second scenario with the third scenario, using all three algorithms, the amount of fitness function obtained at the third scenario is less (better) than the fitness value obtained at the second scenario. Therefore, the DG placement has improved the value of the objective function.
  • It can be seen that at all the three scenarios, the fitness function values of the solutions obtained by the GA are better (less) than the ones acquired by the PSO, and also the fitness function values of the solutions attained by the SA are better (less) than the ones achieved by the GA. Therefore, at all the three scenarios, the SA algorithm has found the best solutions.

Table 4. Fitness function values of the best solutions obtained for different scenarios and algorithms with Kruskal’s coding

Scenario

Fitness function value

PSO

GA

SA

Scenario 1 (Feeder Routing with no DG)

35411

34038

34038

Scenario 2 (Only Feeder Routing with DGs in predefined buses)

14488

14357

14294

Scenario 3 (Feeder Routing with DGs placement)

13029

12971

12306

6.3 Effect of DGs

For further evaluations, the details of the best solutions obtained by the SA algorithm with Kruskal’s coding for all the three scenarios are given in Table 5.

Considering Table 5, the following points can be deduced:

  • It can be seen that at all the three scenarios, the total cost (Ct) is equal to the value of its corresponding fitness function, which means that according to Eq. (9), the amount of the penalty factor has no effect on the value of the fitness function. In other words, the solutions obtained at all the three scenarios have satisfied all the constraints.
  • By comparing the results of the second and third scenarios with the first scenario, the presence of DGs at the second and third scenarios has led to a significant reduction in the cost of energy losses (Cl) and supply interruption (Ci) at the second and third scenarios compared to the first scenario, such that, the per unit total cost has dropped from 1 per unit at the first scenario to 0.42 per unit at the second scenario and to 0.36 per unit at the third scenario. Therefore, the existence of DGs has been very effective in reducing the cost of energy losses and supply interruption.
  • By comparing the results of the third scenario with the second, the total cost (Ct) has dropped from 0.42 per unit at the second scenario, where the DGs are at predefined locations (nodes 7, 8, 9, and 10), to 0.36 per unit at the third scenario, where the DGs are in optimal locations, and this cost reduction is mostly due to a reduction in the cost of supply interruption (Ci) at the third scenario, compared to the second one. Therefore, the DG placement has improved the value of the objective function.

As an example, variations in the fitness values of the evaluated solutions as well as optimal solutions during the steps of the implementing the SA at the third scenario are shown in Figure 3 which indicates that although the values of the fitness functions of the evaluated solutions at the initial steps have large fluctuations due to the higher probability of accepting weaker solutions to avoid being trapped by local optimal solutions, but at the next steps, the solutions gradually converge towards a final optimal solution. It is considerable that the scale of the vertical axis of the graph is logarithmic. The optimal solution found at the third scenario is displayed in Figure 4.

Table 5. Details of the best solutions obtained using the SA algorithm and Kruskal’s coding at different scenarios

item

Scenario 1 (Feeder Routing with no DG)

Scenario 2 (Only Feeder Routing with DGs in predefined buses)

Scenario 3 (Feeder Routing with DGs placement)

Fitness value

34038

14294

12306

Per unit of total cost (Ct)

1

0.42

0.36

Total cost (Ct)

34038

14294

12306

The capital recovery cost (Cc)

4125

4113.8

4080

the cost of supply interruption (Ci)

12063

2517.7

481

The cost of Energy Losses (Cl)

17850

7662.7

7745

Branches of the optimal network

[1 2 3 5 7 9 12 14 19 21 22 24 26 27 29 30 32 33 34 35 36 37 39 40]

[1 2 3 6 9 13 15 17 19 21 22 24 26 27 29 30 32 33 35 36 37 38 41 42]

[1 2 3 5 7 9 12 14 19 21 22 24 26 28 29 30 32 33 35 36 37 38 39 40]

DG buses

-

[7 8 9 10]

[9 13 14 15]

Figure 3. Variations in the amount of fitness function during the steps of the SA algorithm

Figure 4. The obtained optimal solution at the third scenario

7. Conclusion

In this paper, the problem of the optimal feeder routing along with DG placement was formulated as an optimization problem whose presented solutions by three meta-heuristic algorithms including PSO, GA and SA were examined. Using the Kruskal’s algorithm, a method for coding the distribution network configurations was presented by which the search space is restricted to radial configurations of the network. Numerical studies on a 10 kV distribution network with 24 load points and 42 available branches showed that, first, while using a traditional coding method with any of the three algorithms is not even able to achieve a feasible solution, the use of Kruskal’s coding method proved to be highly effective in solving the distribution feeder routing problem. Second, the SA algorithm obtains the best solutions in comparison with the PSO and GA algorithms. Third, the presence of DGs massively reduces the cost of supply interruption and the cost of energy losses. Fourth, the DG placement reduces the total cost significantly.

  References

[1]  Nahman, J.M., Perić, D.M. (2020). Radial distribution network planning under uncertainty by applying different reliability cost models. International Journal of Electrical Power & Energy Systems, 117: 105655. http://doi.org/10.1016/j.ijepes.2019.105655

[2]  Wang, S., Dong, Z.Y., Chen, C., Fan, H., Luo, F. (2019). Expansion planning of active distribution networks with multiple distributed energy resources and EV sharing system. IEEE Transactions on Smart Grid, 11(1): 602-611. http://doi.org/10.1109/TSG.2019.2926572 

[3]  Resener, M., Haffner, S., Pereira, L.A., Pardalos, P.M., Ramos, M.J. (2019). A comprehensive MILP model for the expansion planning of power distribution systems–Part I: Problem formulation. Electric Power Systems Research, 170: 378-384. http://doi.org/10.1016/j.epsr.2019.01.040

[4]  Resener, M., Haffner, S., Pereira, L.A., Pardalos, P.M., Ramos, M.J. (2019). A comprehensive MILP model for the expansion planning of power distribution systems–Part II: Numerical results. Electric Power Systems Research, 170: 317-325. http://doi.org/10.1016/j.epsr.2019.01.036

[5]  Valenzuela, A., Inga, E., Simani, S. (2019). Planning of a resilient underground distribution network using georeferenced data. Energies, 12(4): 644-662. http://doi.org/10.3390/en12040644 

[6]  Wang, S., Luo, F., Dong, Z.Y., Ranzi, G. (2019). Joint planning of active distribution networks considering renewable power uncertainty. International Journal of Electrical Power & Energy Systems, 110: 696-704. http://doi.org/10.1016/j.ijepes.2019.03.034

[7]  Rastgou, A., Moshtagh, J., Bahramara, S. (2018). Improved harmony search algorithm for electrical distribution network expansion planning in the presence of distributed generators. Energy, 151: 178-202. http://doi.org/10.1016/j.energy.2018.03.030

[8]  Salyani, P., Salehi, J., Gazijahani, F.S. (2018). Chance constrained simultaneous optimization of substations, feeders, renewable and non-renewable distributed generations in distribution network. Electric Power Systems Research, 158: 56-69. http://doi.org/10.1016/j.epsr.2017.12.032

[9]  Ahmed, H.M., Eltantawy, A.B., Salama, M.M. (2017). A stochastic-based algorithm for optimal feeder routing of smart distribution systems. In 2017 IEEE 30th Canadian Conference on Electrical and Computer Engineering (CCECE), pp. 1-4. http://doi.org/10.1109/CCECE.2017.7946677

[10]  Nahman, J., Perić, D. (2017). Path-set based optimal planning of new urban distribution networks. International Journal of Electrical Power & Energy Systems, 85: 42-49. http://doi.org/10.1016/j.ijepes.2016.08.001

[11]  Ghadiri, A., Haghifam, M.R., Larimi, S.M.M. (2017). Comprehensive approach for hybrid AC/DC distribution network planning using genetic algorithm. IET Generation, Transmission & Distribution, 11(16): 3892-3902. http://doi.org/10.1049/iet-gtd.2016.1293

[12]  Yosef, M., Sayed, M.M., Youssef, H.K. (2015). Allocation and sizing of distribution transformers and feeders for optimal planning of MV/LV distribution networks using optimal integrated biogeography based optimization method. Electric Power Systems Research, 128: 100-112. http://doi.org/10.1016/j.epsr.2015.06.022

[13]  Khatami, H., Ravadanegh, S.N. (2015). Probabilistic optimal robust multistage feeder routing under load forecasting uncertainty. IET Generation, Transmission & Distribution, 9(14): 1977-1987. http://doi.org/10.1049/iet-gtd.2014.1097

[14]  Hemmati, R., Hooshmand, R.A., Taheri, N. (2015). Distribution network expansion planning and DG placement in the presence of uncertainties. International Journal of Electrical Power & Energy Systems, 73: 665-673. http://doi.org/10.1016/j.ijepes.2015.05.024

[15]  Ravadanegh, S.N., Roshanagh, R.G. (2014). On optimal multistage electric power distribution networks expansion planning. International Journal of Electrical Power & Energy Systems, 54: 487-497. http://doi.org/10.1016/j.ijepes.2013.07.008

[16]  Kumar, D., Samantaray, S.R., Joos, G. (2014). A reliability assessment based graph theoretical approach for feeder routing in power distribution networks including distributed generations. International Journal of Electrical Power & Energy Systems, 57: 11-30. http://doi.org/10.1016/j.ijepes.2013.11.039

[17]  Hasan, I.J., Gan, C.K., Shamshiri, M., Ab Ghani, M.R., Omar, R. (2014). Optimum feeder routing and distribution substation placement and sizing using PSO and MST. Indian Journal of Science and Technology, 1682-1689.

[18]  Ganguly, S., Sahoo, N.C., Das, D. (2013). Multi-objective planning of electrical distribution systems using dynamic programming. International Journal of Electrical Power & Energy Systems, 46: 65-78. http://doi.org/10.1016/j.ijepes.2012.10.030

[19]  Singh, S., Ghose, T., Goswami, S.K. (2011). Optimal feeder routing based on the bacterial foraging technique. IEEE Transactions on Power Delivery, 27(1): 70-78. http://doi.org/10.1109/TPWRD.2011.2166567

[20]  Samui, A., Samantaray, S.R., Panda, G. (2012). Distribution system planning considering reliable feeder routing. IET Generation, Transmission & Distribution, 6(6): 503-514. http://doi.org/10.1049/iet-gtd.2011.0682

[21]  Samui, A., Singh, S., Ghose, T., Samantaray, S.R. (2011). A direct approach to optimal feeder routing for radial distribution system. IEEE Transactions on Power Delivery, 27(1): 253-260. http://doi.org/10.1109/TPWRD.2011.2167522

[22]  Ziari, I., Ledwich, G., Ghosh, A. (2011). Optimal integrated planning of MV–LV distribution systems using DPSO. Electric Power Systems Research, 81(10): 1905-1914. http://doi.org/10.1016/j.epsr.2011.05.015

[23]  Najafi, S., Hosseinian, S.H., Abedi, M., Vahidnia, A., Abachezadeh, S. (2009). A framework for optimal planning in large distribution networks. IEEE Transactions on Power Systems, 24(2): 1019-1028. http://doi.org/10.1109/TPWRS.2009.2016052

[24]  Nahman, J.M., Peric, D.M. (2008). Optimal planning of radial distribution networks by simulated annealing technique. IEEE Transactions on Power Systems, 23(2): 790-795. http://doi.org/10.1109/TPWRS.2008.920047

[25]  Gomez, J.F., Khodr, H.M., De Oliveira, P.M., Ocque, L., Yusta, J.M., Villasana, R., Urdaneta, A.J. (2004). Ant colony system algorithm for the planning of primary distribution circuits. IEEE Transactions on Power Systems, 19(2): 996-1004. http://doi.org/10.1109/TPWRS.2004.825867