Portal de Periódicos da CAPES

Fast distribution network reconfiguration with graph theory

2018; Institution of Engineering and Technology; Volume: 12; Issue: 13 Linguagem: Inglês

10.1049/iet-gtd.2018.0228

1751-8695

Shengjun Huang, Venkata Dinavahi,

Software-Defined Networks and 5G

IET Generation, Transmission & DistributionVolume 12, Issue 13 p. 3286-3295 Research ArticleFree Access Fast distribution network reconfiguration with graph theory Shengjun Huang, Corresponding Author Shengjun Huang shengjun@ualberta.ca orcid.org/0000-0002-4703-9020 Department of Electrical and Computer Engineering, University of Alberta, Edmonton, Alberta, T6G 2V4 Canada College of Information System and Management, National University of Defense Technology, Changsha, Hunan, 410073 People's Republic of ChinaSearch for more papers by this authorVenkata Dinavahi, Venkata Dinavahi orcid.org/0000-0001-7438-9547 Department of Electrical and Computer Engineering, University of Alberta, Edmonton, Alberta, T6G 2V4 CanadaSearch for more papers by this author Shengjun Huang, Corresponding Author Shengjun Huang shengjun@ualberta.ca orcid.org/0000-0002-4703-9020 Department of Electrical and Computer Engineering, University of Alberta, Edmonton, Alberta, T6G 2V4 Canada College of Information System and Management, National University of Defense Technology, Changsha, Hunan, 410073 People's Republic of ChinaSearch for more papers by this authorVenkata Dinavahi, Venkata Dinavahi orcid.org/0000-0001-7438-9547 Department of Electrical and Computer Engineering, University of Alberta, Edmonton, Alberta, T6G 2V4 CanadaSearch for more papers by this author First published: 22 May 2018 https://doi.org/10.1049/iet-gtd.2018.0228Citations: 5AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract Owing to mixed-integer and non-linear properties, the distribution network reconfiguration (DNRC) problem has been widely addressed with meta-heuristic algorithms. To accelerate the solution process, two essential components of meta-heuristic algorithms are investigated in this study: solution representation and fitness evaluation. Instead of the popular binary and integer numbers, decimal encoding is employed. Decoding is based on the proposed probability-based loop destruction strategy. The fitness evaluation is based on the power flow calculation of radial network. Different from backward/forward sweep method, the advantageous direct solution technique is utilised, where the matrix generation process has been accelerated. Both improvements are based on the graph theory and fully explained with illustrative examples. Case studies are implemented on five benchmark systems. The superiority of the proposed methods over their advanced counterparts has been established with intensive comparisons. Finally, these methods are integrated into a standard particle swarm optimisation framework for the solution of DNRC. Results indicate that the proposals significantly improve the solution efficiency without the loss of quality. Nomenclature BCBV branch-current to bus-voltage BFS backward/forward sweep BIBC bus-injection to branch-current BRD branch-based reachability detection DA direct approach DN distribution network DNPF distribution network power flow DNRC distribution network reconfiguration FD fast decoupled GA genetic algorithm GS gauss-Seidel MINLP mixed-integer non-linear programming MRD matrix-based reachability detection MST minimum spanning tree NR Newton-Raphson PLD probability-based loop destruction PSO particle swarm optimisation RTS radial tree structure MILP mixed-integer linear programming 1 Introduction As the most intensive part of power systems, the distribution network (DN) is directly connected to large numbers of consumers, where unexpected failures and load fluctuations are inevitable. To deal with these uncertainties, flexibility is indispensable. Generally, the DN is built as interconnected with switches, while radial tree structure (RTS) is maintained in operation [1]. The radial tree is obtained from the opening of switches, and the transformation of one tree into another is possible with the adjusting of on/off status of switches; therefore, the flexibility is achieved. Finding an optimal RTS from the DN with specified objective while satisfying an operating constraint is classified as the DN reconfiguration (DNRC) problem. Owing to low-voltage levels, the DN produces a large number of power losses, thus minimising system power loss comprises the major objective of DNRC in this work. Other goals considered in the literature include high reliability [2] and smooth voltage profile [3]. In addition to the global optimality of the final solution, execution time is of great significance for DNRC. For any decision-making problem, the obtained solution is optimal only when the input status has not changed; otherwise, it might be suboptimal or invalid. Since the customer action keeps changing, the solution time of DNRC should be minimised to preserve the optimality. Nevertheless, the solution process of DNRC is not trivial. Actually, it is a mixed-integer non-linear programming (MINLP) problem with combinatorial property [4]. Linearisation techniques [5–8] are widely utilised to formulate the MINLP into an MINLP problem, where deterministic methods [9–11] and heuristic strategies [12–17] are available. However, the accuracy might be sacrificed due to the utilisation of simplification and relaxation. On the other hand, meta-heuristic algorithms [1, 4, 18, 19] are capable to accurately solve the MINLP problem. To achieve satisfactory optimality and efficiency from the solution process of DNRC with the computationally intensive meta-heuristic algorithm, the following two major concerns should be fully addressed: RTS: Generally, the DN is described as a graph , where and are finite sets containing vertices and edges. Thus, the DNRC problem is to find out an optimal tree with respect to specific goals, where and . In the meta-heuristic algorithm, T is described as the individual and evolutionary operation is conducted on it to achieve better individuals. However, the newly obtained T might be infeasible since all elements in should be connected and no cycles are permitted in T. Generally, graph theory [20] should be followed for the generation of T. DN power flow (DNPF): The values of resistance R and reactance X in the DN are of a great range, which may result in a big ratio of . In this case, the efficient fast decoupled (FD) PF algorithm may fail to converge since the major assumption is violated [1]. On the other hand, it is complicated and time-consuming to introduce the Gauss–Seidel or Newton–Raphson (NR) methods for the solution of DNPF due to the RTS of DN [4]. The key point to address RTS concern is guaranteeing all the generated individuals are feasible. The infeasible individual will destroy the evolutionary process since the fitness value cannot be identified, i.e. the evolutionary direction cannot be evaluated. In the literature, two types of heuristics are widely investigated to obtain feasible individuals: Modification: This kind of method starts from an RTS tree T. To obtain a new T, only two steps are required. First, select one edge in and add it into . Owing to RTS feature and graph theory, the resulted T does not hold RTS since a cycle is formulated by . Second, in order to obtain RTS again, select one edge belonging to the cycle and add it into . This method is named branch exchange in the literature, i.e. exchanging with . Within this framework, different strategies are proposed [12–14] to determine and . Generation: This type of method starts from the full graph G. A successive process should be implemented to generate a candidate RTS. At each step, identify one cycle in G, and then select one edge in that cycle to delete. Each step means breaking a circle/loop. This process continues until there is no cycle in G. On the basis of how to select in each loop, different methods are developed [15–17, 21]. Although these heuristics are straightforward and easy to implement, they are greedy and the final solution depends on the initial configuration [1], thus it is a local optimum rather than the global best. Therefore, they are commonly integrated into a meta-heuristic framework to achieve the global optima. Nevertheless, the encoding and decoding strategies are usually complicated or inefficient due to the identification of different circles. For example, the integer coded genetic algorithm is utilised in [18], where crossover and mutation operations are based on the matroid theory, which is highly dependent on the circles. Instead of dealing with loops, a novel decimal encoding technique is proposed in [4], where the RTS is naturally guaranteed for each candidate based on the minimum spanning tree (MST) calculation. Given an undirected graph G whose branches are weighted with decimal numbers, different trees can be generated by advanced MST algorithms. This method is direct, but the solution process is time-consuming because the MST searching is computationally intensive and should be executed thousands of times. In this paper, a new encoding and decoding strategy [(probability-based loop destruction (PLD)] is proposed based on decimal numbers. Instead of the heavy MST computation, only simple operations are involved in the PLD method. To address the DNPF concern shown above, techniques widely utilised for transmission network have been modified and applied to accommodate DN such as the FD [22–24] and NR [25–27] algorithms. One limitation of this kind of method is that the successive admittance matrices must be updated in each iteration due to the topology variation. The construction and factorisation of these matrices bring heavy computation burden; thus, the solution efficiency is limited. On the other hand, the backward/forward sweep (BFS) method [28] and its variants [19, 29, 30] have gained great popularity for the DNPF solution due to their good convergence and easy applicability. One major drawback of the BFS as summarised in the literature [31] is the requirement on the numbering schemes for the system buses and/or branches, which could reduce the flexibility and affect its ability to accommodate changes in topology. In addition, the solution time of DNPF with BFS is mainly determined by the number of system buses, thus the capability for large-scale systems is restrained. Instead of the time-consuming LU decomposition and backward/forward substitution, a distinctive direct approach (DA) was proposed in [32], where only the matrix multiplications were involved. The essential processes related to two newly defined matrices, i.e. the bus-injection to branch-current (BIBC) matrix and the BC to bus-voltage (BCBV) matrix. The advantages of DA has been revealed in [32, 33]. Although the formulation algorithm [branch-based reachability detection (BRD)] of BIBC and BCBV reported in [32] is intuitive, the efficiency is limited since only one branch is considered at each step. In this paper, a novel algorithm [matrix-based RD (MRD)] for the construction of BIBC and BCBV is developed based on the graph theory, where all switches are considered concurrently by adjacency matrix and path matrix. In summary, two improvement proposals are developed in this paper to address two major concerns of a meta-heuristic algorithm for the solution of DNRC, i.e. PLD and MRD for RTS and DNPF, respectively. To validate the accuracy and efficiency, both PLD and MRD, as well as their advanced counterparts MST and BRD, are coded and integrated into a standard particle swarm optimisation (PSO) framework provided by the MATLAB global optimisation toolbox [34]. Five benchmark systems are introduced for implementation and comparison. The PLD is faster than MST method for the decoding of 10,000 individuals. Compared to BRD, MRD can reduce the execution time by 62.93%. In addition to the efficiency, PLD is also beneficial on the convergence property. The results indicate that the superiority of the proposed strategies is significant within the evolutionary computing framework. It is believable that their application on other algorithm frameworks such as deterministic and heuristic are also promising. The rest of this paper is organised as follows. Section 2 is devoted to the concerns of RTS, where the detailed steps of PLD are described and explained. To achieve high efficiency on the solution of DNPF, the MRD is proposed and embedded within the DA framework in Section 3. Case studies and discussion are provided in Section 4. Finally, Section 5 concludes this paper. 2 Solution encoding and decoding strategies The DNRC solution consists of a series of open branches, which can be intuitively represented with binary and integer numbers. Although both of them are straightforward and easy to implement, the radial topology of the network cannot be maintained efficiently, which results in a large number of infeasible solutions during the evolutionary process; therefore, the convergence property is limited and the capability for the large-scale system solution is weak. To alleviate these concerns, a novel encoding technique was developed in [4], where each branch corresponds to one element in the solution vector and assigned with a real number. When decoding, the real number corresponding to each branch is regarded as the weight, thus a weighted undirected graph was established. By doing an MST computation, the radial topology can be uniquely determined. This method guarantees all solutions are feasible, i.e. the RTS is always preserved. Although there are several advanced algorithms for MST computing such as Prim's, Kruskal's, and Boruvka's algorithms, the computational complexity is still high. In addition, the MST calculation should be performed for thousands of times, corresponding to the generation of each candidate. To alleviate the computational burden and improve the solution efficiency, a two-stage probability-based encoding and decoding processes are developed in this paper. 2.1 Stage 1: network analysis As a preliminary process, this stage is independent of decoding process and will be executed for only once. The main objective is to find out the shortest cycle for each tie switch and organise them in a specified order. On the basis of this order, Stage 2 is designed to break these cycles and generate the RTS. For simplicity, a small-scale distribution system is introduced for illustration, which is shown in Fig. 1. The target network consists of nodes, branches, and tie switches (indicated by dashed lines). The following steps are responsible for network analysis, where step-by-step temporary results corresponding to Fig. 1 are also revealed: Step 1: Open all the switches to generate a radial tree. The result is indicated by Fig. 2a. Step 2: Close each tie switch to find a corresponding cycle. This step can be fulfilled by calculating the shortest path between two nodes of each tie switch in the radial tree. Fig. 2b illustrates these cycles with responding to both branch and node ID. Step 3: Join the cycles with branch ID into one whole vector , and determine the index of each switch in to generate another vector . Finally, insert a 0 at the beginning of . Fig. 2c demonstrates the ultimate results of Stage 1. Obviously, the number of cycles is ; therefore, is of length . On the other hand, the length of is problem dependent due to branch reputation at different cycles. To sum up, the input of network analysis is the initial configuration, and the outputs are vectors and . Fig. 1Open in figure viewerPowerPoint Configuration of the target DN Fig. 2Open in figure viewerPowerPoint Intermediate results of the network analysis (a) generated radial tree structure by the opening of tie switches, (b) identified cycles corresponding to each tie switch with shortest path calculation, (c) organized vectors for cycles and indices 2.2 Stage 2: solution representation On the basis of vectors and , this stage illustrates how to encode and decode decimal solution vector . 2.2.1 Encoding To determine whether a branch should be open or close, a probability value is granted for each branch in this paper; therefore, the decimal solution vector can be encoded intuitively as 2.2.2 Decoding Given a real number encoded solution as shown in Fig. 3a, the PLD decoding processes are developed as follows: Step 1: Generate a temporary vector , whose elements are corresponding to the probability of each tie switch in . Step 2: Sort in ascending order and store the indexes vector as . Set . Step 3: Let , find out the cycle based on and . Step 4: Look up the probability value in for each branch of the cycle. Step 5: Select the branch with the largest probability value as the one for breaking, which is marked as . Step 6: Update the probability value of the cycle in R as −1.00. Step 7: If , go back to Step 3 ; otherwise, output the decoded solution S. Temporary results from Steps 1 and 2 are illustrated in Fig. 3b, while other results are demonstrated in Fig. 3c. Fig. 3Open in figure viewerPowerPoint Encoded real number solution vector and its decoding (a) real number encoded solution, (b) decoding preparation, (c) decoding process 2.3 Supplementary explanation The basic idea of PLD is branch exchange : Stage 1 is utilised to find the cycle formulated by closing one switch, and that loop is destroyed in Stage 2 by opening one branch based on the probability. All cycles generated from Stage 1 are stored in two vectors and with respect to the specified order. Intuitively, these circles can be broken with the same order for all decoding process. Nevertheless, this will destroy the randomness and restrict the solution space. For example, if the destruction of the cycle is always earlier than a cycle , then the branch 10 in the second cycle will never be broken since its probability is updated into −1.00 after the destruction of the first cycle. To address this concern, the breaking of different cycles should be conducted in a random order, that is, the reason to introduce the vector in Steps 3–6. In terms of how to determine different for the various decoding process, the easiest method is a random generation. However, this will result in diversity during the convergence process since one may be decoded into different if different is utilised. To guarantee that one can only be decoded into a unique , the should be the same for each decoding. One possible strategy is directly deducing from , which is fulfilled by Steps 1 and 2. Although Stage 1 is straightforward, it is more computationally intensive than Stage 2 due to the shortest path searching. The complexity of Dijkstra algorithm with Fibonacci heap for the shortest path calculation is [35]. Similarly, the MST calculation also comes with heavy computation. The complexity of Kruskal's algorithm for MST is [36]. Fig. 4 demonstrates the implementation framework of PLD and MST methods for encoding and decoding. It can be seen that the heavy computation workload is involved for all N times of decoding in the MST method, while only one network analysis is required for the PLD method; therefore, the computational complexity of PLD is lighter. Solid quantitative validation will be given in the case studies. Fig. 4Open in figure viewerPowerPoint Implementation frameworks of different decoding techniques (a) PLD method, (b) MST method 3 DNPF analysis As indicated in Section 1, the DA proposed by Teng [32] is advantageous; therefore, its framework is determined by the solution of DNPF. The DA solution process is dominated by BIBC and BCBV matrices, which are generated by BRD in [32]. After a brief introduction of the solution process of DA, this section intends to propose a novel and efficient MRD for the substitution of BRD when formulating BIBC and BCBV. 3.1 Solution process of the DA Given a DN with nodes, the equivalent current injection for the node i at the k th iteration is given as (1) where is the voltage of bus i at the k th iteration; and are real and reactive power injections on the node i, respectively; is the conjugate operator. Consider and are vectors of and without reference node. Then the voltage update steps at the k th iteration are given as (2) Therefore, the voltage vector can be updated as (3) where is a vector whose all elements are the voltage of reference bus. On the basis of the above preliminary description and definition, the iterative solution process is summarised as Algorithm 1. Algorithm 1.Iterative solution process of the DA method 1: Initialise , set iteration and . 2: Generate matrices , , and . 3: while do 4: Calculate according to (1). 5: Compute based on (2). 6: Update just as (3), and set . 7: end while 8: Calculate the power losses based on and . 3.2 Matrix generation It can be seen from Algorithm 1 and (1)–(3) that matrices and are essential for the iterative procedure. To illustrate how to generate , the distribution system shown in Fig. 1 is utilised as an example, where the tie switches 4–13, 7–11, and 2–8 are open to formulate a radial tree. Consider as the current for the branch i. The objective is finding matrices and such that (4) (5) At first, the formulation of is illustrated as follows: Step 1: Reorganise the branch data: Suppose the input data is the one shown in Fig. 5a, then a radial tree can be generated as in Fig. 2a. This step is exchanging the 'from' and 'to' ends of each branch such that the 'from' has a smaller layer number than the 'to'. The intermediate result is shown in Fig. 5b. Step 2: Rank the branch data: For any DN with nodes, there are branches. After the reorganisation, the 'to' nodes of branches are different from each other, which corresponds to non-reference buses. This step ranks these branches in an ascending order of their 'to' nodes, and then assigns an ID to them. Fig. 5c illustrates the temporary result. Step 3: Construct the adjacency matrix: To describe the direct relationship between and , an adjacency matrix is defined. Its size is , containing all branches and non-reference buses. Each element is filled with a binary number, where means that can be directly accessed by , and vice versa. The construction process is as follows: (i) since is identical with , the diagonal of are all ones; (ii) if there is a branch from non-reference node i to j, set . Fig. 5d demonstrates , where ten off-diagonal elements are corresponding to ten branches without reference node. Step 4: Calculate the path matrix: According to Teng [32], is a binary matrix, and represents that can be accessed by either directly or indirectly. According to the graph theory, this definition is similar to the path matrix, thus the is generated as (6) where is a function that converts any non-zero elements into 1 and keeps zeros constant. The final obtained result is shown in Fig. 5e. On the basis of (4), in Fig. 5e can be interpreted as (7) which is identical with Fig. 1. It was stated in [32] that is an upper triangular matrix. We intend to claim that this is not always true though Fig. 5e shows an upper triangular pattern. In Fig. 5c, if the 'from' is larger than 'to', matrices and are both not upper triangular. For example, replace the branch 4–3 with 4–13, the resulting is not triangular. Fig. 5Open in figure viewerPowerPoint Intermediate results of matrix BIBC generation (a) original branch data set, (b) reorganised branch data set, (c) ranked branch data set, (d) generated adjacency matrix, (e) calculated path matrix As indicated in [32] that the construction processes of and are similar, thus the above process can be reused with minor revision. Actually, these two matrices were built in the same subroutine in [32] to save computation resources and time. In this paper, the is generated by the following simple equation: (8) where is the transpose operator; is the matrix whose diagonal is the line impedance shown in Fig. 5c. Combining (5) and (8), we get (9) which is in accordance with Fig. 1. 3.3 Supplementary explanation It should be noted that the generated in Step 3 is not the adjacency matrix according to the definition of graph theory [20] due to the non-zero diagonal. Regarding the tree as a directed graph (each branch is directed from the higher layer to the lower layer) and let , then is the adjacency matrix coordinated with the definition. According to Harris et al. [20], the path matrix can be deduced by (10) where n is the size of , i.e. in this paper. The entry of is equal to the number of walks from node i to j that use exactly k edges. On the other hand, according to the binomial expansion theorem (11) where are constant numbers valued as . Since there are no cycles in the tree, the maximum number of paths between any two nodes is one; thus, the elements of as well as are zeros and ones. Therefore, (6) can be rewritten as (12) Although (6) is identical with (10), the difference on the computational burden is large. In (10), a lot of matrix power should be calculated such as and , while there is only one matrix power executed in (6). The complexity of is equivalent with the matrix addition. Thus (6) is much more efficient than (10). Furthermore, based on the above analysis and (11), we obtain (13) Since the longest walk in the tree with n nodes is (14) Thus (15) This property can be utilised to further improve the efficiency of (6), i.e. to reduce the number of matrix multiplications from to . In this example, ; therefore, , and can be generated by times of matrix multiplications as follows: In [32], the BIBC is formulated by steps. Since each step is dependent on the former step, the constitution process must be executed in sequence. On the other hand, there are only sparse matrix multiplications in MRD method, and each multiplication can be accelerated with parallel processing. Comparison of the efficiency will be discussed with numerical experiments. 4 Numerical experiments As demonstrated above, two methods PLD and MRD are proposed in this paper to accelerate the solution process of DNRC. To evaluate their performance, three types of numerical experiments are implemented in this section. In the beginning, the comparison between PLD and its advanced counterpart MST method is carried out for the solution decoding. Then, the MRD method is compared with the BRD method on the DNPF solution. Finally, these methods are integrated into a standard PSO framework for the solution of DNRC. The former two tests are the partial validation of the performances of PLD and MRD, while the last one is a complete evaluation of their potential for the DNRC solution. Five benchmark systems generated from [37] are introduced as the testbed. Table 1 summarises the scales of these systems. All tests are implemented on a personal computer equipped with Intel Xeon E5-2620 central processing unit and Windows 8.1 operating system. MATLAB 2017a is employed for programming and execution. Table 1. Scales of the benchmark systems Systems Buses Feeders Branches Tie switches 14-bus 13 3 16 3 33-bus 32 1 37 5 70-bus 68 2 79 11 83-bus 83 11 96 13 136-bus 135 1 156 21 4.1 PLD method versus MST method for solution decoding Within the meta-heuristic algorithm framework, the solution decoding process will be executed a lot of times in each iteration; therefore, its efficiency is of great significance for the whole execution. On the other hand, the representation methodology should not contain any bias, i.e. the randomness is valid. This section is devoted to the performance evaluation of the PLD method in terms of randomness and efficiency, where the MST method reported in [4] is introduced for comparison. 4.1.1 Randomness Without supplementary information, the global optimal may lie anywhere in the solution space. Therefore, the meta-heuristic algorithm always demands an evenly initialised population to cover the solution space as large as possible. Both the PLD and MST methods are designed for decimal encoded solutions, whose randomness is guaranteed by a lot of software such as MATLAB. Therefore, the randomness of the decoded integer solution is dominated by the transformation methodology. Fig. 6Open in figure viewerPowerPoint Frequency of branches chosen for breaking in the 14-bus system For the performance validation and comparison, 10,000 real number encoded solutions are randomly generated for the 14-bus system. After decoding, 10,000 integer solutions with sizes of are obtained, which means there will be 30,000 branches to be chosen for breaking. Since the number of candidate branches for breaking is only 15 (branches 6–9 cannot open as it is not included in any cycles), the frequency of each branch should be 2000. Fig. 6 illustrates the results of both methods, it can be seen that the randomness of the PLD and the MST methods are similar and satisfactory. For the MST method, branches close to the root node have a high probability to be chosen for breaking such as branches 1, 5,