04-11-2016, 11:00 AM
Advantageous Power Flow Path Selection and restoration of power Using Different Shortest Path Algorithms.
1464353964-ADIP2WORD.docx (Size: 272.61 KB / Downloads: 3)
INTRODUCTION:
Whenever a blackout occurs in the transmission network, the power system operators are under immense pressure to restore the network. The main aim of the power system restoration is to restore as much load as possible & as quickly as possible. After a blackout occurs first all the generators has to be energized and then synchronized. After synchronization of generators only all the loads can be supplied. For energizing the generators a sequential procedure has to be followed. If the sequence used is wrong then it may lead to cascaded outages.
Efficient management of a network requires the shortest route from one point(node) to another ,this is termed the shortest path. It is often neccessary to determine alternative routes through the network, in case any of the shortest path is damaged or busy.
Power system network can undergo outages during which there may be a partial or total black out in the system. To minimize the interruption of power supply to consumers, proper switching of power lines is required. Identification of power flow path in the network is the difficult task of the load dispatching center.
The scope of this proposed work is to identify the optimal power flow path using three shortest path algorithms:
*Dijkstra’s Algorithm,
*Bellman- Ford Algorithm(BFA)
*Floyd Warshall Algorithm (FWA).
Results obtained from the load flow studies and other constraints are used to apply the solution for restoring the load in the transmission line.
It consists of two steps:
The first step is to determine an optimal configuration
The second step is to prepare a sequence of switching operations (restoration plan) in order to bring the faulted network into the obtained target system.
SHORTEST PATH:
1. Whether shortest paths are computed from a single source vertex to all other vertices (SSSP), or between all pairsof vertices (APSP). One shouldalso consider the intermediate problem of computing shortest paths from multipleSources (MSP).
2. Whether the edge lengths are non-negative or arbitrary.
3. Whether the graph is directed or undirected.
4. Whether shortest paths are computed using just comparison & addition operations,or whether they are computed assuming a specific edge-length representation(typically integers in binary) and operations specific to that representation.Comparison-addition based algorithms are necessarily general and they work when edge-lengths are either integers are real.
When a fault occurs in the power system network, we need to divert the power through the other transmission lines. This diverted path of power flow during fault condition or partial black out condition should be of minimum impedance in order to reduce the losses in the network. Then only the power can be sent through the restorative path.That’s why above mentioned algorithms are appropriate to be used.
DIJKSTRA’S ALGORITHM
Dijkstra's algorithm, conceived by Dutch computer scientist EdsgerDijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing.
Dijkstra’s algorithm is applied to find path between physical locations, such as driving directions on websites like Mapquest or Google Maps. In a networking or telecommunication applications, Dijkstra’s algorithm is used for solving the minimum delay path problem. In data network routing, the goal is to find the path for data packets to go through a switching network with minimal delay. It is also used for solving a variety of shortest path problems arising in plant and facility layout, robotics, transportation,and VLSI design.
Bellman-Ford Algorithm:
Bellman Ford algorithm obtains solution in the single source problem if the edge.
Weights are negative.It outputs a vector where it finds the shortest distance from one node to another.
It can detect a negative-weight cycle. It is also extremely easy to code and its coding time is also less than a few minutes.
FloydWarshall Algorithm:
The FWA is a graph analysis algorithm for identifying the shortest path in a weighted graph.
The shortest path between all pairs of vertices is obtained in a single execution of the algorithm. It is an example of dynamic programming.
It will consider negative weights too.
It can detect a negative-weight cycle. It is extremely easy to code and coding time less than a few minutes.
FWA will find the shortest paths between all pair of vertices, we assume node 1 & node 4 as source and all other nodes are destination.
Implementation of the Dijkstra’s Algorithm to the Practical Network
A 19 bus, 28 lines practical network is considered for this study and it provides electricity to more than one million customers in a metropolitancity in India which is shown in Figure. The network is tied with the Power grid of India which supplies 220 MW power through the Neyveli Power Station (bus 18). The network has total installed generating capacity of 2300 MW. The corresponding nodal diagram is shown in Figure. All the values of generation and loads are represented in MW. In order to explain theimplementation of the Dijkstra’s algorithm, MTPS one of the generatingstations (Bus no 14) is considered as the starting node and the area Kadaperiis taken as the load bus (Bus no 12). Since the impedance is a small numerical value, for explanation purpose actual distance is taken between the areas.
PSEUDOCODE:
DIJKSTRA’S ALGORITHM:
fori=1 to v
dist[i]= infinity
previous node in optimal path is undefined
previous [i]= undefined
dist[source]= 0
Q= the set of all nodes in graph
u= vertex in Q with smallest distance in dist_
ifdist[u] = infinity
break;
all remaining vertices are inaccessible from source
remove u from Q
for each neighbor v of u
alt = dist[u] + dist_between(u,v)
if alt<dist[v]
dist[v] = alt
previous[v] = u
decrese-key v in Q
BELLMAN-FORD:
Initialize ds =0 and dv =_ for all v_s
for k=1…..n-1;
for each edge u_v of cost c:
dv= min(dv,du+c)
for each edge u_v of cost c:
if dv> du +c:
Floyd Warshall Algorithm:
fori = 1 to N
for j = 1 to N
if there is an edge from i to j
dist [0][i][j] = the length of the edge from i to j
else
dist [0][i][j] = INFINITY
for k = 1 to N
fori = 1 to N
for j = 1 to N
dist [k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])
COMPARISON:
The primary difference in the function of the two algorithms is that Dijkstra's algorithm cannot handle negative edge weights.
Bellman-Ford's algorithm can handle some edges with negative weight. It must be remembered, however, that if there is a negative cycle there is no shortest path. FloydWarshall calculates shortest distance between all pairs of nodes.
That’s why Dijkstra’s algorithm and BFA can be used in a network where single source is to be considered. FWA is applicable to a network of any type because it finds shortest path between all pair of nodes present in a network.
The software can also be developed for the execution of optimal path identification in MATLAB.
CONCLUSION:
When a fault occurs in the power system network, we need to divert the power through the other transmission lines. This diverted path of power flow during fault condition or partial black out condition should be of minimum impedance in order to reduce the losses in the network. Then only the power can be sent through the restorative path. That’s why above mentioned algorithms are appropriate to be used.