J. Cent. South Univ. (2012) 19: 2534-2540 

DOI: 10.1007/s11771-012-1307-8

Distribution network planning based on shortest path

LU Zhi-ying(路志英), GAO Shan(高山), YAO Li(姚丽)

Department of Electrical Engineering and Automation, Tianjin University, Tianjin 300072, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2012

Abstract: In order to form an algorithm for distribution network routing, an automatic routing method of distribution network planning was proposed based on the shortest path. The problem of automatic routing was divided into two steps in the method: the first step was that the shortest paths along streets between substation and load points were found by the basic ant colony algorithm to form a preliminary radial distribution network, and the second step was that the result of the shortest path was used to initialize pheromone concentration and pheromone updating rules to generate globally optimal distribution network. Cases studies show that the proposed method is effective and can meet the planning requirements. It is verified that the proposed method has better solution and utility than planning method based on the ant colony algorithm.

Key words: distribution network planning; shortest path; ant colony algorithm; pheromone

1 Introduction

The main task of distribution network planning is to optimize network structure, then to find the optimal distribution network expansion program. The investments and operating costs on the basis of network’s security can be minimized through the certainty of the grid’s route. The distribution network planning has several characteristics, including nonlinearity, discreteness, operation mode diversity, multi-stage and so on, which is quite complex to solve [1].

At present, there have been so many researches on distribution network planning. Linear programming algorithms (such as single-stage model and the multi-stage model [2-3]) are usually applied to the distribution network planning. However, many important constraint conditions are ignored. Therefore, it is difficult to solve large scale combinatorial optimization problems. Traditional optimization algorithms (such as the branch exchange method [4-5]) are closely related to the selection of the initial solution, and it is difficult to determine an initial solution close to the optimal solution for distribution network planning when the load data are uncertain, and the estimation of parameters is not accurate. The application of modern intelligent random search method provides a new idea for network optimization. Genetic algorithm [6] is a random search algorithm for solving global optimization problems, through a series of operators like crossover operator and mutation operator to produce excellent results. Although some of the advantages have been shown on the distribution network planning, the coding problems usually generate infeasible solutions, which directly affect the optimization efficiency. Compared to genetic algorithms, evolutionary strategy [7] also belongs to a simulated evolutionary algorithm, and pays more attention to the role of mutation. Tabu search algorithm [8] is a random search algorithm. It has a powerful global search performance when combined with other algorithms. But its local search performance tends to be impacted by dispersion. Simulated annealing algorithm [9] has been used to find the global optimal solution, by incorporating a probability function in the solution space of the objective function. Combined with other methods [10-17], it has been successfully used to solve distribution network planning problems.

At present, the method combined with geographic information to achieve auto routing still shows difference in actual distribution network planning. So, distribution network planning is completed by manual way. In this work, the power distribution planning is divided into two parts: one is looking for substation-load along the shortest path, and the other is routing optimization. An improved ant colony algorithm for distribution network planning is adopted. Through the simulation of physical planning area, a set of medium voltage distribution network routing planning is put forward.

2 Mathematical model and constraints of MV distribution network planning

2.1 Mathematical model

The objective function of mathematical model is based on the minimum comprehensive cost, including the network investment and annual operating costs:

                       (1)

           (2)

                       (3)

where C_line is the network investment, C_loss is annual operating costs,  f is the comprehensive cost, N is the total number of existing and newly-constructed substations, J_i is the total number of radial lines by substation i, l_ik is the length of line k added from substation i, m_l is the depreciation period of the line in the low side of substations, r₀ is the discount rate, P_ik is the load (active power) carried by line k of substation i, α is the investment cost of unit length of the line, and β is the conversion factor of line loss.

2.2 Constraint conditions

According to the operating features of medium voltage distribution network in city, 10 kV distribution networks must satisfy the following constraint conditions:

1) Voltage drop must be within the allowable range. The constraints of these drops of voltage are reflected by the length of network. According to the density and weight of load, the range of line length is 2-10 km.

2) Each line capacity must not be overloaded. To facilitate later wiring, each line reserves the margin of 50%.

3) Distribution network structure is radial.

4) Each line of network must be paved along city streets. During automatic routing, if any of the constraint is removed in a planning scheme, this scheme is a failure.

3 Formation of geographic information knowledge base

3.1 Knowledge structure

Figure 1 illustrates the distribution network. The geographical information of the distribution network is represented by the frame representation which supports the organization of knowledge into complex units. The detail of the frame representation is as follows:

(Substation supply area

(Substation  (substation 1   (coordinate (X, Y))

(capacitance value))

(substation 2  (coordinate (X, Y))

(capacitance value))

…)

(Load    (load 1 (coordinate (X, Y)) (load value))

(attached to substation substation No. ))

(load 2…)

…)

(Node    (node 1 (coordinate (X,Y)))

(node 2…)

…)

(Route  (route 1 (start point node No.)

(end point node No.)

(Adjacent load (load 1 load No.)

(load 2 …)))

(route 2 …)

…)

)

Fig. 1 Sketch map of street and load positions: 1-4: Load No.; ①-⑨: Node No.; (1)-(12): Route No.

3.2 Knowledge base

The SQL Server software was used to establish the geographical information database. Parts of the information are given in Tables 1-4.

Table 1 Information of substations

Table 2 Information of loads

Table 3 Information of routes

Table 4 Information of nodes

The GIS knowledge database is built by using geographical information. The database not only can describe the information relationships between the streets in the planning region, and the power supply range of substations accurately, but also is easy for calling, querying and updating of the program.

4 Power distribution network planning based on ant colony algorithm and shortest path

4.1 Basic idea of ant colony algorithm and its features

Ant colony algorithm is inspired by the collective foraging behavior of real ant colony and is an analog bionic algorithm [18-19]. A lot of observational studies show that during the foraging activities of ants, the choice of single ant is initially random, and each ant leaves substance which is called pheromone on its path. On one hand, the pheromone decays gradually over time; on the other hand, the later ants care the presence of pheromone, and guide their direction of movement by the amount of residual pheromone on the path.

Ant colony algorithm has the features of positive feedback, distributed computation and using greedy heuristic search and so on. Among them, the positive feedback is helpful to quickly find a better solution of the problems, distributed computing can avoid the phenomenon of the premature which occurs in the process of iteration, and greedy heuristic search can find an acceptable solution in the search process earlier. Although the ant colony algorithm has these advantages, the basic ant colony algorithm still has some shortcomings, such as slow convergence and being easily trapped into the local optimal solution.

According to the ant colony algorithm, the method of the distribution network planning based on ant colony algorithm is proposed and implemented in this work. In this method, a substation is treated as the “ant nest” meanwhile the load as the “food source” that the ants are looking for. In wiring, the ants choose their routes according to the transfer criteria. Examples show that this method can effectively obtain the optimal solution of distribution network planning.

The proposed method of distribution network planning has two new points: Firstly, the shortest path model is used to pheromone the initialization of ant colony; Secondly, transition probability model is combined with the pheromone updating rules.

4.2 Basic ant colony algorithm and shortest path

In this work, the basic ant colony algorithm is used to find the shortest path. The flow chart of laying the shortest path from the substation to the loads is shown in Fig. 2, where “curLoad” is the current load visited, “loop” is the current number of iterations, “numl” is the total number of load, “iItCount” is the largest number of iterations, j is the current number of ants, and “iAntCount” is the number of ants.

If the total number of loads is “numl”, the same number of the shortest paths can be got through the result of the basic ant colony algorithm. This information is given in Table 5.

4.3 Transfer probability criterion

The direction of movement of each artificial ant in a node is determined by the state transition criteria. The transition probabilities of all the optional paths of each ant are calculated using the transition probability:

         (4)

where P_j (i, k) is the probability of street k selected by ant i at node j; T_j(i, k) is the pheromone strength of route k which is selected by ant i at node j; d_k is the length of route k; R_j(i) is the set of all candidate routes that ant j can select at node i; α and β are constants and represent the relative importance of pheromone and the relative importance of the length of the streets, respectively.

Assume the number of routes is n. In selecting process, for an ant j, when it locates on node i, it will choose a route k according to the following transition criteria:

1) Sum

Calculate the sum of the probability of all routes at node j. S can be expressed as

                              (5)

Fig. 2 Flow chart of laying shortest path from substation to load points

Table 5 Information of shortest path

2) Select

Generate random number r between 0 and S.

3) Loop

Go through the node j and sum the probability q_k. q_k can be expressed as

When the sum q_k is greater than r, the route k where it stops is selected.

Clearly, the route with larger probability will be selected probably. Figure 3 shows the sketch map of the route selected. The route (k=3) is the fittest route.

Fig. 3 Sketch map of route selected: (1) P_j(i, 1)=0.1; (2) P_j(i, 2)=0.2; (3) P_j(i, 3)=0.4; (4) P_j(i, 4)=0.3

4.4 Pheromone updating rules

4.4.1 Pheromone initialization based on shortest path

In the routing process, the pheromone on the road is an important basis for the selection of ants. The more the pheromone in the path, the more probability the route is selected. During basic ant colony algorithm, the initial value of pheromone is set to be a constant, so that the ants have equal probability to select each route. In this work, we used the substation–load shortest path to achieve the pheromone initialization suit for distribution network planning. Its realization process is as follows:

Step 1: Initialize the pheromone of the streets matrix route[ ] according to

                                    (6)

where T_k is the initial pheromone on route k; H₀ is the initial amount of pheromone of each route, and it is a constant.

Step 2: Calculate the number of times of numl shortest paths (numl is the total number of load points) through each route. Each time the route k is passed, the route[k].r_flag plus 1. The number of shortest paths through the route k is marked by route[k].r_flag.

(7)

where T(k,0) is the initial pheromone amount of route k; ε is a constant, which is used to adjust the importance of the shortest path information.

This pheromone initialization makes full use of the shortest path information. On one hand, the ant has a larger probability to find routes that have higher concentration of pheromone in the solution space, thus ensuring fewer routes with more loads, which greatly reduces the random search. On the other hand, in the wiring design, the length and the capacity of line are restricted, and some loads out of range cannot be considered, leaving the entire program affected. If we adopts the shortest path, the whole wiring process can drop out of endless loop to avoid this.

4.4.2 Principle of local pheromone dynamically updating

In the view of the above initialization pheromone method, a matching pheromone dynamically updating principle is put forward. This principle makes the superiority of the initialization information that contains the shortest path information play an important role in network planning. It is not only in the initial stage, but also during the whole process of wiring.

After pheromone initialization, the strength of pheromone in each route is different and unequal. For example, the total number of shortest paths is numl, and each path has its own specific way. The end of each shortest path carries a load. One street may be passed by a number of different shortest paths, and when the number is larger, the pheromone content of the streets is higher. So, it means that one ant that passes a high pheromone content route may have a high probability to take more loads in shorter path. Otherwise, the possibility is less.

Thus, our principle of local pheromone dynamically updating is also set around this point. When an artificial ant has completed a journey, we immediately adjust pheromone intensity. Specific operations are as follows:

1) Record the load_ID which has been visited by one ant to the array, takeLoad[s], where s is the amount of load visited by the ant.

2) Extract the routes of the shortest path of each load in takeLoad[s].

3) Calculate the number of times of each route which is passed through by the shortest paths.

4) Use Eq. (8) to update

         (8)

where t represents the current time, (t+1) represents the next time; T(k, t) represents the pheromone of route k at t time; T(k, t+1) represents the pheromone when the ant has completed a journey at time (t+1); ε is a constant, consistent with Eq. (7). route[k].r_flag marks the number of the shortest paths through the route k.

4.4.3 Global pheromone updating

According to the minimum value of objective function, the best planning is determined and then the global pheromone is updated using the following equation:

1) When ant j doesn’t pass route k

                       (9)

2) When ant j passes route k

               (10)

        (11)

where τ₁ is the volatile factor of the pheromone, which is similar with ε in Eq. (8); τ₁ is a constant; (1-τ₁) is the remaining pheromone of route k after its global pheromone updating; ΔT_best represents the variation of pheromone under the best planning.

Ant colony algorithm is a random search method. Therefore, we pre-set enough number of cycles. When program reaches this default total number of cycles, the search process terminates. From the above, the flow chart is shown in Fig. 4.

Fig. 4 Flow chart of distribution network planning

5 Experiments and analysis

The examples in this work were under several prerequisites. Firstly, the location of substation, the supply area of power, and the distribution of loads were given. Secondly, the planning region was new, and the network rolled out of radial wiring pattern. Thirdly, the cross-sectional areas of all wires were the same.

Through several tests, the colony size was set to be 150, and the iteration number (loops of program) was 20.

5.1 Case 1

The planning area was powered by two substations of 10 kV. No.1 substation (2×50 MV·A) pays 21 loads altogether 42 036.26 kW. No. 2 substation (2×40 MV·A) pays 33 loads altogether 54 829.19 kW. The network planning is shown in Fig. 5.

Fig. 5 Distribution network planning solution of Case 1

Suppose is predictive load value, and load_e is rated value. If is greater than load_e, we calculated : On one hand, the remainder of the result as the value of ; On the other hand, as the number of lines which need to be separated wiring. In Case 1, there are seven lines needed to be separated wiring, which means that there are seven shortest paths in addition for great loads.

After calculation, the ideal situation should be: The total number of the lines is 32, and No. 1 substation outlets 14 lines, No. 2 substation outlets 18 lines. After auto-routing, a total number of 36 lines is received. This is slightly more than the ideal situation. The total length of the whole lines is 42.25 km and the average length of each line is 1.17 km. In the case of the average, each line carries 2 699.04 kW. So, this planning meets the requirements of actual situation. The planning method based on the ant colony algorithm [12] has a total of 36 lines, the average length of each line is 1.61 km, and the load each line carries 2 690.70 kW by average. The method in this work carries more loads by using relatively shorter lines, showing better performance than the method based on the ant colony algorithm.

5.2 Case 2

This planning area is powered by 1 substation  (3?50 MV·A), and there are 74 loads; the forecast of total load is 102.2 MW. The network planning is shown in Fig. 6.

Fig. 6 Distribution network planning solution of Case 2

Compared to Case 1, this case is more complex. The planning lays a total number of 36 lines. The total length of the lines is 85.50 km, and the average length of each line is 2.085 km. In the case of the average, each line carries 2 492.11 kW. The lines could carry up to six loads, and reaches 3 024 kW, which is close to full load of 3 200 kW. This routing is reasonable and meets the requirements. This case further validates that the proposed algorithm is effective.

6 Conclusions

1) The medium-voltage distribution network planning method has been proposed based on the shortest paths, when the load and power supply area (the new supply region) are known. The shortest paths along streets between substation and load points are found by the basic ant colony algorithm.

2) This method innovatively makes use of the shortest paths into initialization pheromone concentration of the streets. And the shortest paths play an important role in the updating principle of local pheromone.

3) The geographic information and load information are fully used to construct rules of updating local and global pheromone. The task of distribution network planning is completed effectively.

References

[1] WANG Sai-yi, WANG Cheng-shan. Urban MV distribution network planning based on multi-objective model [J]. Electric Power, 2006, 39(11): 46-50. (in Chinese)

[2] WANG Tong-wen, XU Wen-ge, GUAN Lin. Methods for optimal programming of the electric power grid structure [J]. Relay, 2005, 33(21): 58-61. (in Chinese)

[3] QUINTANA V H, TENRAZ H K, HIPEL K W. Two-stage power system distribution planning algorithm [J]. IEE Proceedings- Generation, Transmission and Distribution, 1993, 140(1): 17-29.

[4] NI Qiu-long, HUANG Ming-xiang. Power distribution network planning using branch exchange based simulated annealing algorithm [J]. Proceedings of the EPSA, 2000, 12(4): 31-35. (in Chinese)

[5] M?GUEZ E, CIDR?S J, D?AZ-DORADO E, GARC?A- DORNELAS J L. Improved branch-exchange algorithm for large-scale distribution network planning [J]. IEEE Transactions on Power System, 2002, 17(4): 931-936.

[6] MIRANDA V, RANITO J V, PROCENCA L M. Genetic algorithms in optimal multistage distribution network planning [J]. IEEE Trans on Power Systems, 1994, 9(4): 1927-1933.

[7] HSIAO Y T, CHIEN C Y. Multiobjective optimal feeder reconfiguration [J]. IEE Proceedings-Generation, Transmission and Distribution, 2001, 148(4): 333-336.

[8] NARA K, HAYASHI Y, YAMAFUJI Y, TANAKA H, HAGIHARA J, MUTO S, TAKAOA S, SAKURAOKA M. A Tabu search algorithm for determining distribution tie lines [C]// International Conference on Intelligent Systems Applications to Power Systems Proceedings. New York: IEEE, 1996: 266-270.

[9] BOUCHARD D E, SALAMA M M A, CHIKHANI A Y. Optimal feeder routing and optimal substation sizing and placement using guided evolutionary simulated annealing [C]// Proceedings of the Canadian Conference on Electrical and Computer Engineering. Canada, 1995: 688-691.

[10] DANIEL L C, KHAN I H, RAVICHANDRAN S. Distribution network reconfiguration for loss reduction using ant colony system algorithm [C]// Proceedings of INDICON 2005: An International Conference of IEEE India Council. Chennai, India, 2005: 619-622.

[11] RIVAS-D?VALOS F, IRVING M R. The edge-set encoding in evolutionary algorithms for power distribution network planning problem part II: Multi-objective optimization planning [C]// Proceedings-Electronics, Robotics and Automotive Mechanics Conference. Cuernavaca, Morelos, Mexico, 2006: 251-257.

[12] LU Jie. The Research of urban medium-voltage distribution network planning based on the ant colony algorithm [D]. Tianjin: Tianjin University, 2008. (in Chinese)

[13] HAFFNER S,PEREIRA L F A,PEREIRA L A, BARRETO L S.Multistage model for distribution expansion planning with distributed generation-Part II: Numerical results [J]. IEEE Transactions on Power Delivery, 2008, 23(2): 915- 923.

[14] NAVARRO A, RUDNICK H. Large-scale distribution planning-Part II: Macro-optimization with Voronoi’s diagram and Tabu search [J]. IEEE Transactions on Power System, 2009, 24(2): 752-758.

[15] BEMARDON D P, GARCIA V J, FERREIRA A S Q, CANHA L N. Multicriteria distribution network reconfiguration considering subtransmission analysis [J]. IEEE Transactions on Power Delivery, 2010, 25(4): 2684-2691.

[16] COSSENT R, G?MEZ T, OLMOS L, MATEO C, FR?AS P. Assessing the impact of distributed generation on distribution network costs [C]// 6th International Conference on the European Energy Market. Leuven, Belgium: IEEE, 2009: 1-8.

[17] CARLOS M D, TOM?S G S R, ?LVARO S M, JES?S PASCUAL P G, ANTONIO C M. A reference network model for large-scale distribution planning with automatic street map generation [J] . IEEE Transactions on Power Systems, 2011, 26(1): 190-197.

[18] DORIGO M, MANIEZZO V, COLORNI A. Ant system: Optimization by a colony of cooperating agents [J]. IEEE Transactions on System, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29-41.

[19] TAN Guan-zheng, HE Huan, SLOMAN A. Ant colony system algorithm for real-time globally optimal path planning of mobile robots [J]. Acta Automatica Sinica, 2007, 33(3): 279-285.

(Edited by YANG Bing)

Foundation item: Project(2009CB219703) supported by the National Basic Research Program of China; Project(2011AA05A117) supported by the National High Technology Research and Development Program of China

Received date: 2011-08-30; Accepted date: 2012-01-05

Corresponding author: LU Zhi-ying, Associate Professor, PhD; Tel: +86-13820573798; E-mail: luzy@tju.edu.cn