Algorithms For Distribution Feeder Reconfiguration

794

ALGOFUTHMS FOR DISTRIBUTION FEEDER RECONFIGIJRATION D.E. Bouchard and M.M.A. Salama

A.Y. Chikhani

Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario N2L 3G1

Department of Electrical and Computer Engineering Royal Military College of Canada Kingston, Ontario K7K 5LO

-

A bshact Power distribution systems typically have a radial configuration. Sectionalizing switches along a feeder and interfeeder tie switches are used to maintain a radial structure. For every switch closed, another switch is opened, resulting in a new system configuration. To date, few algorithms and data structures have been proposed. In this paper, distribution system buses and sections are represented as adjacency and incidence matrices. Three algorithms are presented for reconfiguration. The first determines the admittance matrix for a feeder. The second algorithm performs a branch exchange between two feeders, ensuring no loads are left disconnected from the system, and that the systems's radial configuration is maintained. A third algorithm updates system data for the new configuration. I. INTRODUCTION Distribution system reconfiguration for loss minimization is an active area of research, and a recent review of the literature found over 35 references to the problem since: 1982 [ 11. However, few efficient algorithms and data structures for implementation in software have been proposed to date. Distribution systems are usually open loop, or iradial, structures. Sectionalizing switches along a feeder and interfeeder tie switches are used to maintain a radial structure. For every switch closed, another is opened. The primary benefit of a radial structure is that it simplifies fault detection, allowing a utility to quickly dispatch repair crews where needed, and to isolate faulted sections so that service to other sections can be restored. Supervisory control ancl data acquisition (SCADA) systems allow the remote control of distribution system switches to improve system reliability through fault isolation and service restoration. These switches can also be used to transfer loads among feeders in a distribution system to meet new load requirements, ;and to make better use of system capacity.

however, how the structure w,asgenerated was not presented. Cespedes [3] proposed a branch and node nomenclature that gave the branches a number that coincided with one of the end nodes of the same, allowing the representation of the network by a single vector. However, the representation presented only considered static networks, and would not be useful for the load re-allocation or reconfiguration problem. Borozan et al [4] proposed algorithms which improved the efficiency of the methods of Shirmohammadi and Hong [5]; however, they are not general enough to be used i~ other algorithms. In this paper, distribution system buses and sections are represented as adjacency arid incidence matrices. Three algorithms are presented for reconfiguration. The first determines the admittance matrix for a feeder. The second algorithm performs a branch exchange, ensuring no loads are left disconnected from the system, and that the system's radial configuration is maintained. A third algorithm updates system data for the new configuration.

11. SOME GRAPH THEORY Consider the two-feeder network of Figwe 1. Circled numbers represent buses, wlhile uncircled letters represent feeder sections. The dashed slection (section d) between buses 5 and 7 represents a currently-open sectionalizing switch. If this switch were to be closed, switch a, b, g, f or e would have to be opened to re-(establish the network's redial configuration. It is very easy to see how the network is connected from this figure; however, this representation is of no value for computer processing. However, the network can be represented conveniently ancl naturally by two matrices. If G is a graph with n vertices and e edges, the adjacency matrix, X = [x,,], can be defined having n rows corresponding to the n vertices, and e columns corresponding to the e edges,

Castro e t a1 [2] were perhaps the first to propose algorithms for distribution feeder reconfiguration. They proposed a fixed as follows [6]: data structure referred to as a switch table, which repre:sented the actual distribution system configuration in tabular form. x,, = 1, if there is ;an edge between the ith and j Data in the switch table was static, except for one cmolumn vertices: a d , which indicated switch status (open or closed). The dynamic = 0, otherwise. structure of the distribution network was represented as a multipath tree, and was generated from the switch table;

CCECE'96

0-7803-3143-5 /96/$4.00 0 1996 IEEE _-______

795

1 2 3 4 5 6 7 8 0 0 1 0 0 0 0 0

0 1 0 0 0 0

0

0 0 0 0 0 1 0 1 1 0

0 1 0 0 0

0 1 0 0 0

1 0 0 0 0

0 0 0 0 0

0 0 0 0 1

0 0 0 0 0 0 1 0 0 0 0 1 1 0

Quation (1) Adjacency matrix for the network of Figure 1.

1 0 0 1 0 0 0

0 0

2 3 4 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0

5 6 7 8

0 0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 - 1 0 0

0 0 0 0 1

0 0 0 T10 0 1 0 0 0 0 1 1 0

Quation (2) Adjacency matrix, with -I to indicate possible connections.

The adjacency matrix, X, for Figure 1 is shown in Equation (1). This is a binary symmetric matrix. A count of the number of 1's in a row (or column) indicates how many edges are incident on a vertex. Although no such rows or columns are present, a row or column of all zeroes would indicate an isolated vertex. Because it is the reconfiguration problem that is of interest, it is useful to have a method to indicate possible connections. This can be done by substituting a -1 for the 0 where applicable (for buses 5 and 7 in this case), and this is shown in Equation (2). It can be seen that this matrix is a sparse matrix, and hence a more compact representation is required, and thus the adjacency matrix is rewritten as a series of vectors, as shown in Equation (3). The zero at the end of each vector is simply

Figule 1. A small, two-feeder distribution system. The circled numbers are buses, and the letters represent sections.

quation (3) Adjacency matrix written as a series of vectors.

a marker to indicate there are no further elements in the vector. It is also possible to define an incident matrix, A(G), for graph G with n vertices and e edges having n rows corresponding to the n vertices, and e columns corresponding to the e edges, as follows [ 6 ] : ail

= 1,

if the Jth edge el is incident on the ith vertex v,; and,

= 0,

otherwise.

The incident matrix for Figure 1 can be written as a series of vectors, as shown in Equation (4) for the system of Figure 1. Both A(G) and X(G) contain all of the information about a radial network, and only one is needed to represent the netkork. However, in the algorithms that follow, it was more convenient to use both matrices in some instances, and thus both are used.

796

111. ALGORITHMS Step 1: set:

The following C* data structures were used to represent bus and section data: typedef struct { int left; int right; int status; complex impedance; complex admittance; 1 section-table;

typedef struct {complex load; int parent-bus-root; int adjacent[41; int incident[4]; 1 bus-table;

After reading the system data, including section data and switch status, as well as bus data and the system adjacency and incidence matrices, Algorithm 1 forms the graphs that represent each feeder, and builds their admittance matrix. Algorithm 2 connects two feeders together momentarily, until the decision is made as to which switch to open. to reestablish the radial configuration of the network. Then, Algorithm 3 is used to update system data.

IV. REFERENCES D.E. Bouchard, Using Evolutionary Strategies to Optimize Power Distribution System Perfonname - a PhLl Thesis Proposal, University of Waterloo, Waiterloo, Ontario, Canada, 1995. C.H. Castro, J.B. Bunch and T.M. Topka, "Generalized Algorithms for Distribution Feeder Deployment and Sectionalizing," IEEE Transactions on Power Apparatus and Systems, vol PAS-99, no. 2, MarchfApril, 1980, pp. 284-289.

R. Cespedes, "New Method for the Analysis of Distribution Networks," IEEE Transactions on Pow er Delivery, vol. 5, no. 1, January 1990, pp. 391-396. V. Borozan, D. Rajicic, R. Ackovski, "Improved Method for Loss Minimization in Distribution Networks," IEEE Transactions on Power Systems, vol 10, no. 3, August, 1995, pp. 1420-1425.

D.Shirmohammadiand H.W. Hong, "Reconfigurationof Electric Distribution Networks for Resistive Line Losses,'' IEEE Transactions on Power Delivery, vol. 4, no. 2, 1989, pp. 1492-1498.

N.Deo, Graph T h e o v with Applications to Engineering and Computer Science, Prentice-Hall, Englewoocl Cliffs, N.J., 1974.

b

Step 2: set: b

fi

v = x (x is the root-node where the search begins); i=O; stack = x; i = i+l num(v) = i ynum(5) = v (not required, but used later on)

Step 3: from v, look for a node that is unvisited, by examining adjacency list values, adjacentrv,0..4] $ a node i.s found, then * push node value to stack; b set v = node value; b go to Step 2; else, pop v from the stack i f v =x, the search is complete; go to Step 4 else, go to Step 3. Step 4: for (i=l to the number qf buses connected to the feeder) {ival=ynum,$eeder-nu,m ber][i]; k=l; neighbour =bus[ival].adjacent[l]; while (neighbour != 11) {if(neighbour > 0) {yffeeder-number][i][i] = yueeder-num ber][i][i] +

sectionf(bus[ival].incident[k])].admittance; entry=numfleedcr-num ber][neighbour]; y/$eeder-numbe~.l[J[entry] = -section[(bus[ival]. incident[k])].admittance; I, k-k+l; neighbour= bus[ival].adjacent[k]; I, // end while ) Nendfor

Algorithm 1. Form feeder graph and the associated Y matrix.

797

Set: endbusl = x (where x is the root node); v=x; count=-I; not-done =TRUE; Push 1 to stack; Push v to stack; while (not-done) {i=v; j=I; while (bus[i].adjacentLj]==stack OR bus[i].adjacentb] c = 0) {if (bus[i].aa'jacentfi]==stack)j = j +1; i f (bus[i].a~acentfiJ
Set v=root-bus; Set not-done=TRUE; Push 1 to stack; Push v to stack; while (not-done) { i=v; j=I; while (bus[i].adjacentli] = =stack[stackqtr] OR bus[i].adjacent,ij] c = 0 AND not-done) {if (bus[i].adjacentfi'= =stack) j=j+l; i f (bus[iJ.adjacentfiJ = 0) {while (bus[i].adjacent,fjJ < = 0) {pop i oflstack; v=i; pop j oflstack; if ((stack==root-bus) AND (bus[iJ.adjacent,lj+ 1]==0)) not-done =FALSE;

I

j=j+l;

I

j = j +I ;

I I push j to stack; push v to stack; count=count+I ; link[count]=bus[i].incidentfi]; v = bus[iJ.aa'jacent,fjJ;

I

if (not-done)

f o r @=I ;k< =NUMBER-OF-FEEDERS;k+ +) {if (bus[i].aa'jacentli]==feeder-root-node[k] AND bus[i].adjacent[iJ!=endbusl) {endbusd =feeder-root-node[k]; not-done =FALSE;

{push j to stack; push v to stack; x= bus[i].adjacentLi]; bus-root[x] =root-b us; v=bus[i].adjacent,fj];

I I

I

I I ~~~

Algorithm 2. Creation of link between two feeders.

Algorithm 3. Update of system data.