# An Improved Substation Locating and Sizing Method Based on the Weighted Voronoi Diagram and the Transportation Model

Authors: Shiju Wang; Zhiying Lu; Shaoyun Ge; Chengshan Wang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Substation locating and sizing is an important component of urban power networks. In this paper, an improved method based on the weighted Voronoi diagram and transportation model for substation planning is proposed, which can optimize the location, capacity, and power supply range for each substation with the minimum investment which contains the cost of the lines, substations, and annual operation expense. The weighted Voronoi diagram (WVD) whose weights can be adaptively adjusted can calculate the location and the capacity for each substation with good performance of global convergence and better convergence speed. Transportation model can simulate the best correspondence relationship between the loads and substations. The impact of geographical factors is also considered in this paper. Large amount of experiments show that the improved method can get more reasonable and more optimized planning result within shorter time than the original WVD and other algorithms.


---

## Body

## 1. Introduction

In a primary distribution network planning problem, the determination of total number, size, and location of new distribution substations is among one of the most important tasks of planners who are responsible for supplying the loads securely, keeping the medium voltage level in defined limits and thereby minimizing losses [1].Decision of the optimum location and numbers of new substations to be constructed is challenging in many cases [2–4]. Determination of the location of new substations generally depends on several conditions including geographical constraints of the region that horizontal load growth occurs in, possession of the areas (private or public property), and other economic aspects. Thus, possible alternative locations of the new substations were generally predetermined considering those constraints first. Then, a proper selection was made between all possible substations to ensure an optimum expansion which satisfied N-1 security criteria and voltage drop constraints and minimized technical losses at the primary network level.Substation locating and sizing is a multivariable, multiobjective, large-scale, nonlinear optimization problem. Substation locating and sizing problem of every voltage level is to take the minimum investment which contains the cost of the lines and substations and annual operation expense as objective function [5–8]. The solutions researchers put forward can be divided into three types: mathematical optimization [9–11], heuristic optimization [12, 13], and modern intelligent optimization [14, 15]. Using mathematical methods to solve programming problems had strict optimality but could hardly get a feasible optimized solution when faced with complex and large-scale problems [16].In recent years, some intelligent optimization technology like simulated annealing algorithms [17, 18] and GA [19, 20] have been gradually applied to this problem.In [21], a simulated annealing algorithm determines substations’ location, capacity, and regional division with better solution quality and efficiency than existing exact algorithms, but it can hardly meet large-scale problems in computing time because of parameter selection and annealing requirements. A tabu search algorithm [22, 23] is also applied in substation locating and sizing. These methods not only have some disadvantages such as long computing time, slow convergence, and local searching ability but also cause load factor beyond the substation control because the power supply range division only uses near allocation. In [24], the author proposed a model using linear functions to express the total cost function. The problem is formulated as a mixed integer linear programming (MILP) problem to avoid the use of nonlinear programming, thus avoiding the possibility of getting trapped in local solutions, but it has not taken the geographic information factors into account. Some other articles [25–28] also raised a lot of ways to solve the substation planning problem, but their computing times were too long.All planning methods mentioned above were realized by using coordinate geometry. Recently, some scholars tried to introduce the geometric Voronoi diagram into power systems. In [16] Voronoi diagram and tabu search algorithms were used to solve low-voltage distribution planning problems. Weighted Voronoi diagram was used to solve substation locating and sizing problems [31]. This method can get reasonable locations for substations, which has good computational stability, and can substantially reduce the program computing time and improve the efficiency of substation locating and sizing.The Voronoi diagram brought a new idea to solving substation locating and sizing problems, but it also had a shortcoming: under the premise of the lowest investment costs, the Voronoi diagram cannot ensure that all substations meet the load rate requirements. According to the planning guidance, long-term overload operation leads to the temperature rise of transformers and causes accelerated aging of the insulation, which is unreasonable.In this work, the problems and main works of this study are introduced first, and then the Voronoi diagram, realized on the basis of improved weighting by adding an adaptive control process of load ratio, was used to get a reasonable substation site planning. On this basis, the transportation model was used to calculate the power supply, which could get a reasonable load rate for each substation. In addition, geographic factors, like rivers, mountains, and lakes, which may have affected substation locations, were also considered in this study. Finally, an example was made to test the method.


## 2. Problems and Main Works of This Study

The problem of optimal substation location can be described as follows. When the load distribution of the target year is known, the number, capacity, location, and power supply range of the construction substations are determined to minimize the cost of substation, network investment, and annual operating costs under the constraint meeting the load carried by the substations. This problem is stated mathematically as(1)
min
⁡
C
=
∑
i
=
1
n
[
f
(
S
i
)
·
r
0
(
1
+
r
0
)
m
s
(
1
+
r
0
)
m
s
-
1
+
u
(
S
i
)
]
dddddddd
+
α
[
r
0
(
1
+
r
0
)
m
l
(
1
+
r
0
)
m
l
-
1
]
∑
i
=
1
N
∑
k
∈
J
i
l
i
k
dddddddd
+
β
∑
i
=
1
N
∑
k
∈
J
i
P
i
k
2
l
i
k
s
.
t
.
∑
k
∈
J
i
P
i
k
≤
S
i
γ
i
cos
⁡
φ
i
=
1,2
,
…
,
N
,
s
.
t
.
J
1
∪
J
2
∪
⋯
∪
J
N
=
J
,
s
.
t
.
l
i
k
≤
R
i
,
where N is the total number of existing and newly constructed substations, n is the number of newly constructed substations, f
(
S
i
) is the investment cost of substation i, u
(
S
i
) is the operation cost of newly constructed substation i, S
i is the capacity of substation i, γ
i is the load rate of substation i, J
i is the load collection carried by substation i, J is the collection of all load points, N
i is the total number of feeders for substation, l
i
k is the length of feeder k added from substation i, P
i
k is the load (active power) carried by feeder k of substation i, m
s is the depreciation years of the substations, m
l is the depreciation years of the substations’ low side, r
0 is the discount rate, cos φ is the power factor, R
i is the limit of the power supply radius of substation i, α is the investment cost per unit length of feeder, and β
=
β
1
β
2
β
3
/
U
2
cos
⁡
2
φ feeder loss conversion factor. β
1 is the line resistance per unit length; β
2 is the unit energy consumption discount factor; β
3is the line loss hours per year; U is the line voltage of the substation low-voltage side.The main problems and solutions are as follows.(1)
The convergence, rationality, and running time of the algorithm were challenged by the constant expansion of the grid. The substation locating and sizing is not a one-time job and is conducted several times with the intervention of experts. The previous algorithm can hardly meet these requirements. In this paper, the weighted Voronoi diagram has been used in substation locating and sizing and two suggestions have been made for improvement: self-adjustment of the weights and capacity optimization.
(2)
Geographical factors, like rivers, lakes, and mountains, had a great impact on substation locating and sizing. It is unreasonable if the substations were located on these locations. In this paper, a method was proposed to solve the problem.
(3)
The power supply range of each substation is usually conformed after substation locating by the WVD, but facts have proved that it can hardly meet the load rate demand in a finite number of iterations; that is, the load rates of some substations are always bigger than their maximum. In this paper, transportation model has been used to calculate the power supply range of each substation after substation siting by the WVD (Figure4).


## 3. Substation Siting by the Improved Weighted Voronoi Diagram (WVD)

### 3.1. The Weighted Voronoi Diagram

Given a control point set on the planeP
=
{
p
1
,
p
2
,
…
,
p
n
}, 3
≤
n
<
∞, the weighted Voronoi diagram of any point can be defined as
(2)
V
(
p
i
,
ω
i
)
=
{
x
∈
V
(
p
i
,
ω
i
)
∣
ω
i
d
(
x
,
p
i
)
≤
ω
j
d
(
x
,
p
j
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
j
=
1,2
,
…
,
n
,
j
≠
i
}
,
where d
(
x
,
p
i
), d
(
x
,
p
j
) is the Euclidean distance between x and p
i, p
j and ω
i is the weight of p
i.It corresponds to an ordinary Voronoi diagram whenω
i
=
1
(
i
=
1,2
,
…
,
n
). The weighted Voronoi diagram is an extended form.The weighted Voronoi diagram reflects the effect on power supply range of an uneven load and the different nominal capacity and load rate of each substation.The distance between a space point and the other points in the Voronoi polygon was the smallest, corresponding to the center-location limit. In addition, deleting or adding a vertex could only affect part of the Voronoi diagram that only the power supply area and network wiring need adjusting when a new substation was constructed, which complied with the characteristics of the network-reconstruction project.


### 3.2. Substation Location Based on Self-Adjusted Weighted Voronoi Diagram

#### 3.2.1. Determination of the Initial Weight

Step 1.
The average power supply radiusr
1
(
i
) of each substation was calculated according to the rated capacity S
(
i
) of each identified substation and the average load density p
m of the whole planning area:
(3)
r
1
(
i
)
=
S
(
i
)
γ
cos
⁡
φ
p
m
π
(
i
≤
n
)
,
where γ is the maximum load rate meeting the “N-1” principle of the main transformer and cos
⁡
φ is the power factor of substations.Step 2.
The substation sites were used as vertices to construct a Voronoi diagram whose weight is 1 to determine the loadl
(
i
) carried by each substation and calculate the power supply radius r
2
(
i
):
(4)
r
2
(
i
)
=
l
(
i
)
p
m
π
(
i
≤
n
)
.Step 3.
The initial weightω
0
(
i
) was determined according to (3) and (4):
(5)
ω
0
(
i
)
=
r
2
(
i
)
r
1
(
i
)
=
l
(
i
)
S
(
i
)
γ
cos
⁡
φ
(
i
≤
n
)
.


#### 3.2.2. Self-Adjustment of the Weights

The power supply range of each substation changes with its weight, and its location changes with its power supply range. Therefore, the self-adjustment of the weights will finally lead to the change of locations. The change of weight follows these rules:we delimit capacity ratioC
k
(
i
):
(6)
C
k
(
i
)
=
l
k
(
i
)
S
(
i
)
γ
cos
⁡
φ
,
where k is the time of iterations and l
k
(
i
) is the load carried by the substation after the kth iteration:
(7)
C
0
(
i
)
=
[
ω
0
(
i
)
]
2
.
Fork
=
1,
ifC
0
(
i
)
>
a, then ω
1
(
i
)
=
ω
0
(
i
)
+
Δ
ω
k
(
i
);
ifC
0
(
i
)
<
b, then ω
1
(
i
)
=
ω
0
(
i
)
-
Δ
ω
k
(
i
);
else,ω
1
(
i
)
=
ω
0
(
i
).
Fork
≥
2,
ifC
k
-
2
(
i
)
>
a and C
k
-
1
(
i
)
>
a, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
+
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
>
a and C
k
-
1
(
i
)
<
b, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
-
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
<
b and C
k
-
1
(
i
)
>
a, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
+
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
<
b and C
k
-
1
(
i
)
<
b, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
-
Δ
ω
k
(
i
);
else,ω
k
(
i
)
=
ω
k
-
1
(
i
).a and b are two adjustable parameters which affect the convergence speed. Since the value of C
k
(
i
) should be close to 1, a and b should also be close to 1. In this work, we set a
=
1.1 and b
=
0.87 which withstood many tests. Δ
ω
k
(
i
) is the amount of weight adjusted and it changes less and less with the increasing of k. In this paper, it was delimited as
(8)
Δ
ω
k
(
i
)
=
1
-
C
k
-
1
(
i
)
k
(
k
=
1,2
,
…
)
.Step 1.
Use the substation sites as the vertices and construct the weighted Voronoi diagram according to the weight of each substation to determine the power supply range and calculate the capacity ratioC
k
(
i
) of each substation (k is the current number of iterations, and i represents substation i).Step 2.
Self-adjustment of the weights.Step 3.
Repeat Step1, until every substation’s capacity ratio C
k
(
i
) is between b and a.


#### 3.2.3. Capacity Optimization

In previous papers, the substation capacities were usually determined in advance, and then substation locating and sizing was conducted in this limitation. This method was easy to be conducted, but it was too restrictive and not conducive to find the optimal solution. In this work, some underselected capacities were given, in which the biggest one was the initial capacity for every substation. The capacity was adjusted according to the load it carried when the location was determined. By this way, we can get the best capacity combination.


#### 3.2.4.  Algorithm Flow

Step 1 (determination of the substation amountn).
Based on the load forecasting of the target year, the capacities of existing substations, and the underselected capacities, the maximum numbern
max
⁡ and the minimum number n
min
⁡ of new substations were determined by the following two formulas:
(9)
n
max
⁡
=
∑
P
-
∑
P
e
(
S
γ
)
min
⁡
cos
⁡
φ
,
n
min
⁡
=
∑
P
-
∑
P
e
(
S
γ
)
max
⁡
cos
⁡
φ
,
where ∑
P is the total active load, ∑
P
e is the total active power of existing substations, (
S
γ
)
min
⁡ is the minimum economic capacity (underselected capacity S
×
load rate γ), and (
S
γ
)
max
⁡ is the maximum economic capacity.Step 2 (parameter initialization).
n
=
n
min
⁡. Use the maximum capacity as the initial capacity.Step 3 (determination of the initial sites).
The location of the initial site affected the convergence speed of the algorithm. The scattered site speeded up the convergence of the algorithm.Step 4 (the weighted Voronoi diagram).
Calculate the power supply range for every substation by the WVD.Step 5 (sites adjustment).
The sites were adjusted in this way:(10)
x
i
t
+
1
=
∑
j
∈
J
i
P
j
x
j
∑
j
∈
J
i
P
j
,
y
i
t
+
1
=
∑
j
∈
J
i
P
j
y
j
∑
j
∈
J
i
P
j
,
where i is the ith substation, J
i is the power supply range of substation i, j is the jth load in J
i, t is the number of cycles, P
j is the active load of j, x
j is the abscissa of load j, and y
j is the ordinate of load j. Judgment: if this inequality is satisfied, ∑
i
=
1
n
(
x
i
t
+
1
-
x
i
t
)
2
+
(
y
i
t
+
1
-
y
i
t
)
2
≥
n
d, then go to Step 4; otherwise, go to next step. d is precision parameter which could be adjusted by experts according to the requirement.Step 6.
Capacity optimization.Step 7 (cost account).
Ifn
<
n
max
⁡, then n
=
n
+
1; go to Step 3; therefore, output the plan whose cost is the lowest.


### 3.3. Substation Locating and Sizing Taking into Account the Geographic Factors

Substation locating and sizing should take into account the geological conditions of the land and the overall planning of the city, especially the long-range planning of the city land. Substations should not be located in some areas, such as areas prone to landslides or mudslides, the downwind of highly polluted areas, mountains, waterways, and lakes, and we call them forbidden areas.In many cases, the location of the substation was greatly restricted. The present substation locating and sizing method was an unconstrained automatic addressing program without considering the geographic factors, which is absolutely unreasonable. On one hand, in this case, the substation site had to be moved to the feasible region manually by people, which led to the increase of people’s work and higher demands of people’s quality; on the other hand, it could hardly ensure the lowest cost of the planning result.A method of substation locating and sizing taking into account the geographic information factors has been proposed in [29]. This method described the geographic factors by land value. Specifically, the land value of areas that cannot build substation is infinity, which could effectively solve this problem. However, such a method could encounter some problems in engineering practice. This method marked the areas that can build substations, but usually this kind of areas is too common; therefore, we had to spend a lot of time to outline the areas, which wasted a lot of time. In this work, the areas that could not build substation were marked in advance, and the location of substations avoided these areas automatically by the program. We can achieve the planning result with the minimum cost by this method.


#### 3.3.1. The Positional Relationship of Substation and Area

Make sure that the substation is in the current area by these two principles.Principle 1. Suppose the substation as the origin and then draw a line across the substation and make sure it is parallel to the x-axis. If both sides of this line had odd points of intersection, then the substation was in line with this principle.Principle 2. Draw a line across the substation and make sure it is parallel to the y-axis. If both sides of this line had odd points of intersection, then the substation was in line with this principle.Figure1 and Table 1 show that example A and example C are in accordance with the two principles; therefore, these two substations were located in the corresponding area.Table 1
The number of Points of intersection.
e.g.
X
-
X
+
Y
-
Y
+
A
1
1
1
1
B
0
0
0
2
C
1
3
1
1
D
2
2
2
0
E
1
2
2
0Positional relationship between the substation and the area.


#### 3.3.2. Sites Adjustment

If the forbidden areas are not considered, the location of the substation is the best location in this iteration. If the substation is located in the forbidden areas, it should be moved out of these areas with the minimum cost increase. The unit cost growth of every movement direction is different, which is related to the loads and distance between the substation and the loads, but one thing is certain that the farther the substation moves on a direction, the more the cost increases, so the least-cost site on every direction is right on the boundary of the forbidden area.The boundary of the forbidden area is formed by many line segments. We can get a point on each line segment by (11), and on this line segment this point is the best location for the substation to move on. We chose the one with the lowest cost from these points as the final site. The mathematical model is
(11)
min
⁡
⁡
C
=
∑
j
∈
J
P
j
d
j
,
d
j
=
(
x
-
x
j
)
2
+
(
y
-
y
j
)
2
,
y
=
a
x
+
b
,
x
1
<
x
<
x
2
,
where C is the weighted distance, J is the power supply range of the substation, and j is the jth load in J. P
j is the active load of j. d
j is the distance between the mobile substation and load j, x
j is the abscissa of load j, y
j is the ordinate of load j, and x
1 and x
2 are the vertexes of the segment. x is the abscissa of the mobile substation and y is the ordinate of the mobile substation. a is the boundary’s slope and b is the boundary’s intercept.


### 3.4. Flow Chart

Figure2 is the flow chart of the substation siting by the improved weighted Voronoi diagram.Figure 2
Substation siting by the improved weighted Voronoi diagram.


## 3.1. The Weighted Voronoi Diagram

Given a control point set on the planeP
=
{
p
1
,
p
2
,
…
,
p
n
}, 3
≤
n
<
∞, the weighted Voronoi diagram of any point can be defined as
(2)
V
(
p
i
,
ω
i
)
=
{
x
∈
V
(
p
i
,
ω
i
)
∣
ω
i
d
(
x
,
p
i
)
≤
ω
j
d
(
x
,
p
j
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
j
=
1,2
,
…
,
n
,
j
≠
i
}
,
where d
(
x
,
p
i
), d
(
x
,
p
j
) is the Euclidean distance between x and p
i, p
j and ω
i is the weight of p
i.It corresponds to an ordinary Voronoi diagram whenω
i
=
1
(
i
=
1,2
,
…
,
n
). The weighted Voronoi diagram is an extended form.The weighted Voronoi diagram reflects the effect on power supply range of an uneven load and the different nominal capacity and load rate of each substation.The distance between a space point and the other points in the Voronoi polygon was the smallest, corresponding to the center-location limit. In addition, deleting or adding a vertex could only affect part of the Voronoi diagram that only the power supply area and network wiring need adjusting when a new substation was constructed, which complied with the characteristics of the network-reconstruction project.


## 3.2. Substation Location Based on Self-Adjusted Weighted Voronoi Diagram

### 3.2.1. Determination of the Initial Weight

Step 1.
The average power supply radiusr
1
(
i
) of each substation was calculated according to the rated capacity S
(
i
) of each identified substation and the average load density p
m of the whole planning area:
(3)
r
1
(
i
)
=
S
(
i
)
γ
cos
⁡
φ
p
m
π
(
i
≤
n
)
,
where γ is the maximum load rate meeting the “N-1” principle of the main transformer and cos
⁡
φ is the power factor of substations.Step 2.
The substation sites were used as vertices to construct a Voronoi diagram whose weight is 1 to determine the loadl
(
i
) carried by each substation and calculate the power supply radius r
2
(
i
):
(4)
r
2
(
i
)
=
l
(
i
)
p
m
π
(
i
≤
n
)
.Step 3.
The initial weightω
0
(
i
) was determined according to (3) and (4):
(5)
ω
0
(
i
)
=
r
2
(
i
)
r
1
(
i
)
=
l
(
i
)
S
(
i
)
γ
cos
⁡
φ
(
i
≤
n
)
.


### 3.2.2. Self-Adjustment of the Weights

The power supply range of each substation changes with its weight, and its location changes with its power supply range. Therefore, the self-adjustment of the weights will finally lead to the change of locations. The change of weight follows these rules:we delimit capacity ratioC
k
(
i
):
(6)
C
k
(
i
)
=
l
k
(
i
)
S
(
i
)
γ
cos
⁡
φ
,
where k is the time of iterations and l
k
(
i
) is the load carried by the substation after the kth iteration:
(7)
C
0
(
i
)
=
[
ω
0
(
i
)
]
2
.
Fork
=
1,
ifC
0
(
i
)
>
a, then ω
1
(
i
)
=
ω
0
(
i
)
+
Δ
ω
k
(
i
);
ifC
0
(
i
)
<
b, then ω
1
(
i
)
=
ω
0
(
i
)
-
Δ
ω
k
(
i
);
else,ω
1
(
i
)
=
ω
0
(
i
).
Fork
≥
2,
ifC
k
-
2
(
i
)
>
a and C
k
-
1
(
i
)
>
a, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
+
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
>
a and C
k
-
1
(
i
)
<
b, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
-
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
<
b and C
k
-
1
(
i
)
>
a, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
+
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
<
b and C
k
-
1
(
i
)
<
b, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
-
Δ
ω
k
(
i
);
else,ω
k
(
i
)
=
ω
k
-
1
(
i
).a and b are two adjustable parameters which affect the convergence speed. Since the value of C
k
(
i
) should be close to 1, a and b should also be close to 1. In this work, we set a
=
1.1 and b
=
0.87 which withstood many tests. Δ
ω
k
(
i
) is the amount of weight adjusted and it changes less and less with the increasing of k. In this paper, it was delimited as
(8)
Δ
ω
k
(
i
)
=
1
-
C
k
-
1
(
i
)
k
(
k
=
1,2
,
…
)
.Step 1.
Use the substation sites as the vertices and construct the weighted Voronoi diagram according to the weight of each substation to determine the power supply range and calculate the capacity ratioC
k
(
i
) of each substation (k is the current number of iterations, and i represents substation i).Step 2.
Self-adjustment of the weights.Step 3.
Repeat Step1, until every substation’s capacity ratio C
k
(
i
) is between b and a.


### 3.2.3. Capacity Optimization

In previous papers, the substation capacities were usually determined in advance, and then substation locating and sizing was conducted in this limitation. This method was easy to be conducted, but it was too restrictive and not conducive to find the optimal solution. In this work, some underselected capacities were given, in which the biggest one was the initial capacity for every substation. The capacity was adjusted according to the load it carried when the location was determined. By this way, we can get the best capacity combination.


### 3.2.4.  Algorithm Flow

Step 1 (determination of the substation amountn).
Based on the load forecasting of the target year, the capacities of existing substations, and the underselected capacities, the maximum numbern
max
⁡ and the minimum number n
min
⁡ of new substations were determined by the following two formulas:
(9)
n
max
⁡
=
∑
P
-
∑
P
e
(
S
γ
)
min
⁡
cos
⁡
φ
,
n
min
⁡
=
∑
P
-
∑
P
e
(
S
γ
)
max
⁡
cos
⁡
φ
,
where ∑
P is the total active load, ∑
P
e is the total active power of existing substations, (
S
γ
)
min
⁡ is the minimum economic capacity (underselected capacity S
×
load rate γ), and (
S
γ
)
max
⁡ is the maximum economic capacity.Step 2 (parameter initialization).
n
=
n
min
⁡. Use the maximum capacity as the initial capacity.Step 3 (determination of the initial sites).
The location of the initial site affected the convergence speed of the algorithm. The scattered site speeded up the convergence of the algorithm.Step 4 (the weighted Voronoi diagram).
Calculate the power supply range for every substation by the WVD.Step 5 (sites adjustment).
The sites were adjusted in this way:(10)
x
i
t
+
1
=
∑
j
∈
J
i
P
j
x
j
∑
j
∈
J
i
P
j
,
y
i
t
+
1
=
∑
j
∈
J
i
P
j
y
j
∑
j
∈
J
i
P
j
,
where i is the ith substation, J
i is the power supply range of substation i, j is the jth load in J
i, t is the number of cycles, P
j is the active load of j, x
j is the abscissa of load j, and y
j is the ordinate of load j. Judgment: if this inequality is satisfied, ∑
i
=
1
n
(
x
i
t
+
1
-
x
i
t
)
2
+
(
y
i
t
+
1
-
y
i
t
)
2
≥
n
d, then go to Step 4; otherwise, go to next step. d is precision parameter which could be adjusted by experts according to the requirement.Step 6.
Capacity optimization.Step 7 (cost account).
Ifn
<
n
max
⁡, then n
=
n
+
1; go to Step 3; therefore, output the plan whose cost is the lowest.


## 3.2.1. Determination of the Initial Weight

Step 1.
The average power supply radiusr
1
(
i
) of each substation was calculated according to the rated capacity S
(
i
) of each identified substation and the average load density p
m of the whole planning area:
(3)
r
1
(
i
)
=
S
(
i
)
γ
cos
⁡
φ
p
m
π
(
i
≤
n
)
,
where γ is the maximum load rate meeting the “N-1” principle of the main transformer and cos
⁡
φ is the power factor of substations.Step 2.
The substation sites were used as vertices to construct a Voronoi diagram whose weight is 1 to determine the loadl
(
i
) carried by each substation and calculate the power supply radius r
2
(
i
):
(4)
r
2
(
i
)
=
l
(
i
)
p
m
π
(
i
≤
n
)
.Step 3.
The initial weightω
0
(
i
) was determined according to (3) and (4):
(5)
ω
0
(
i
)
=
r
2
(
i
)
r
1
(
i
)
=
l
(
i
)
S
(
i
)
γ
cos
⁡
φ
(
i
≤
n
)
.


## 3.2.2. Self-Adjustment of the Weights

The power supply range of each substation changes with its weight, and its location changes with its power supply range. Therefore, the self-adjustment of the weights will finally lead to the change of locations. The change of weight follows these rules:we delimit capacity ratioC
k
(
i
):
(6)
C
k
(
i
)
=
l
k
(
i
)
S
(
i
)
γ
cos
⁡
φ
,
where k is the time of iterations and l
k
(
i
) is the load carried by the substation after the kth iteration:
(7)
C
0
(
i
)
=
[
ω
0
(
i
)
]
2
.
Fork
=
1,
ifC
0
(
i
)
>
a, then ω
1
(
i
)
=
ω
0
(
i
)
+
Δ
ω
k
(
i
);
ifC
0
(
i
)
<
b, then ω
1
(
i
)
=
ω
0
(
i
)
-
Δ
ω
k
(
i
);
else,ω
1
(
i
)
=
ω
0
(
i
).
Fork
≥
2,
ifC
k
-
2
(
i
)
>
a and C
k
-
1
(
i
)
>
a, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
+
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
>
a and C
k
-
1
(
i
)
<
b, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
-
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
<
b and C
k
-
1
(
i
)
>
a, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
+
Δ
ω
k
(
i
);
ifC
k
-
2
(
i
)
<
b and C
k
-
1
(
i
)
<
b, then ω
k
(
i
)
=
ω
k
-
1
(
i
)
-
Δ
ω
k
(
i
);
else,ω
k
(
i
)
=
ω
k
-
1
(
i
).a and b are two adjustable parameters which affect the convergence speed. Since the value of C
k
(
i
) should be close to 1, a and b should also be close to 1. In this work, we set a
=
1.1 and b
=
0.87 which withstood many tests. Δ
ω
k
(
i
) is the amount of weight adjusted and it changes less and less with the increasing of k. In this paper, it was delimited as
(8)
Δ
ω
k
(
i
)
=
1
-
C
k
-
1
(
i
)
k
(
k
=
1,2
,
…
)
.Step 1.
Use the substation sites as the vertices and construct the weighted Voronoi diagram according to the weight of each substation to determine the power supply range and calculate the capacity ratioC
k
(
i
) of each substation (k is the current number of iterations, and i represents substation i).Step 2.
Self-adjustment of the weights.Step 3.
Repeat Step1, until every substation’s capacity ratio C
k
(
i
) is between b and a.


## 3.2.3. Capacity Optimization

In previous papers, the substation capacities were usually determined in advance, and then substation locating and sizing was conducted in this limitation. This method was easy to be conducted, but it was too restrictive and not conducive to find the optimal solution. In this work, some underselected capacities were given, in which the biggest one was the initial capacity for every substation. The capacity was adjusted according to the load it carried when the location was determined. By this way, we can get the best capacity combination.


## 3.2.4.  Algorithm Flow

Step 1 (determination of the substation amountn).
Based on the load forecasting of the target year, the capacities of existing substations, and the underselected capacities, the maximum numbern
max
⁡ and the minimum number n
min
⁡ of new substations were determined by the following two formulas:
(9)
n
max
⁡
=
∑
P
-
∑
P
e
(
S
γ
)
min
⁡
cos
⁡
φ
,
n
min
⁡
=
∑
P
-
∑
P
e
(
S
γ
)
max
⁡
cos
⁡
φ
,
where ∑
P is the total active load, ∑
P
e is the total active power of existing substations, (
S
γ
)
min
⁡ is the minimum economic capacity (underselected capacity S
×
load rate γ), and (
S
γ
)
max
⁡ is the maximum economic capacity.Step 2 (parameter initialization).
n
=
n
min
⁡. Use the maximum capacity as the initial capacity.Step 3 (determination of the initial sites).
The location of the initial site affected the convergence speed of the algorithm. The scattered site speeded up the convergence of the algorithm.Step 4 (the weighted Voronoi diagram).
Calculate the power supply range for every substation by the WVD.Step 5 (sites adjustment).
The sites were adjusted in this way:(10)
x
i
t
+
1
=
∑
j
∈
J
i
P
j
x
j
∑
j
∈
J
i
P
j
,
y
i
t
+
1
=
∑
j
∈
J
i
P
j
y
j
∑
j
∈
J
i
P
j
,
where i is the ith substation, J
i is the power supply range of substation i, j is the jth load in J
i, t is the number of cycles, P
j is the active load of j, x
j is the abscissa of load j, and y
j is the ordinate of load j. Judgment: if this inequality is satisfied, ∑
i
=
1
n
(
x
i
t
+
1
-
x
i
t
)
2
+
(
y
i
t
+
1
-
y
i
t
)
2
≥
n
d, then go to Step 4; otherwise, go to next step. d is precision parameter which could be adjusted by experts according to the requirement.Step 6.
Capacity optimization.Step 7 (cost account).
Ifn
<
n
max
⁡, then n
=
n
+
1; go to Step 3; therefore, output the plan whose cost is the lowest.


## 3.3. Substation Locating and Sizing Taking into Account the Geographic Factors

Substation locating and sizing should take into account the geological conditions of the land and the overall planning of the city, especially the long-range planning of the city land. Substations should not be located in some areas, such as areas prone to landslides or mudslides, the downwind of highly polluted areas, mountains, waterways, and lakes, and we call them forbidden areas.In many cases, the location of the substation was greatly restricted. The present substation locating and sizing method was an unconstrained automatic addressing program without considering the geographic factors, which is absolutely unreasonable. On one hand, in this case, the substation site had to be moved to the feasible region manually by people, which led to the increase of people’s work and higher demands of people’s quality; on the other hand, it could hardly ensure the lowest cost of the planning result.A method of substation locating and sizing taking into account the geographic information factors has been proposed in [29]. This method described the geographic factors by land value. Specifically, the land value of areas that cannot build substation is infinity, which could effectively solve this problem. However, such a method could encounter some problems in engineering practice. This method marked the areas that can build substations, but usually this kind of areas is too common; therefore, we had to spend a lot of time to outline the areas, which wasted a lot of time. In this work, the areas that could not build substation were marked in advance, and the location of substations avoided these areas automatically by the program. We can achieve the planning result with the minimum cost by this method.


### 3.3.1. The Positional Relationship of Substation and Area

Make sure that the substation is in the current area by these two principles.Principle 1. Suppose the substation as the origin and then draw a line across the substation and make sure it is parallel to the x-axis. If both sides of this line had odd points of intersection, then the substation was in line with this principle.Principle 2. Draw a line across the substation and make sure it is parallel to the y-axis. If both sides of this line had odd points of intersection, then the substation was in line with this principle.Figure1 and Table 1 show that example A and example C are in accordance with the two principles; therefore, these two substations were located in the corresponding area.Table 1
The number of Points of intersection.
e.g.
X
-
X
+
Y
-
Y
+
A
1
1
1
1
B
0
0
0
2
C
1
3
1
1
D
2
2
2
0
E
1
2
2
0Positional relationship between the substation and the area.


### 3.3.2. Sites Adjustment

If the forbidden areas are not considered, the location of the substation is the best location in this iteration. If the substation is located in the forbidden areas, it should be moved out of these areas with the minimum cost increase. The unit cost growth of every movement direction is different, which is related to the loads and distance between the substation and the loads, but one thing is certain that the farther the substation moves on a direction, the more the cost increases, so the least-cost site on every direction is right on the boundary of the forbidden area.The boundary of the forbidden area is formed by many line segments. We can get a point on each line segment by (11), and on this line segment this point is the best location for the substation to move on. We chose the one with the lowest cost from these points as the final site. The mathematical model is
(11)
min
⁡
⁡
C
=
∑
j
∈
J
P
j
d
j
,
d
j
=
(
x
-
x
j
)
2
+
(
y
-
y
j
)
2
,
y
=
a
x
+
b
,
x
1
<
x
<
x
2
,
where C is the weighted distance, J is the power supply range of the substation, and j is the jth load in J. P
j is the active load of j. d
j is the distance between the mobile substation and load j, x
j is the abscissa of load j, y
j is the ordinate of load j, and x
1 and x
2 are the vertexes of the segment. x is the abscissa of the mobile substation and y is the ordinate of the mobile substation. a is the boundary’s slope and b is the boundary’s intercept.


## 3.3.1. The Positional Relationship of Substation and Area

Make sure that the substation is in the current area by these two principles.Principle 1. Suppose the substation as the origin and then draw a line across the substation and make sure it is parallel to the x-axis. If both sides of this line had odd points of intersection, then the substation was in line with this principle.Principle 2. Draw a line across the substation and make sure it is parallel to the y-axis. If both sides of this line had odd points of intersection, then the substation was in line with this principle.Figure1 and Table 1 show that example A and example C are in accordance with the two principles; therefore, these two substations were located in the corresponding area.Table 1
The number of Points of intersection.
e.g.
X
-
X
+
Y
-
Y
+
A
1
1
1
1
B
0
0
0
2
C
1
3
1
1
D
2
2
2
0
E
1
2
2
0Positional relationship between the substation and the area.


## 3.3.2. Sites Adjustment

If the forbidden areas are not considered, the location of the substation is the best location in this iteration. If the substation is located in the forbidden areas, it should be moved out of these areas with the minimum cost increase. The unit cost growth of every movement direction is different, which is related to the loads and distance between the substation and the loads, but one thing is certain that the farther the substation moves on a direction, the more the cost increases, so the least-cost site on every direction is right on the boundary of the forbidden area.The boundary of the forbidden area is formed by many line segments. We can get a point on each line segment by (11), and on this line segment this point is the best location for the substation to move on. We chose the one with the lowest cost from these points as the final site. The mathematical model is
(11)
min
⁡
⁡
C
=
∑
j
∈
J
P
j
d
j
,
d
j
=
(
x
-
x
j
)
2
+
(
y
-
y
j
)
2
,
y
=
a
x
+
b
,
x
1
<
x
<
x
2
,
where C is the weighted distance, J is the power supply range of the substation, and j is the jth load in J. P
j is the active load of j. d
j is the distance between the mobile substation and load j, x
j is the abscissa of load j, y
j is the ordinate of load j, and x
1 and x
2 are the vertexes of the segment. x is the abscissa of the mobile substation and y is the ordinate of the mobile substation. a is the boundary’s slope and b is the boundary’s intercept.


## 3.4. Flow Chart

Figure2 is the flow chart of the substation siting by the improved weighted Voronoi diagram.Figure 2
Substation siting by the improved weighted Voronoi diagram.


## 4. Adjustment of the Substation Power Supply Range Based on the Transportation Model

Theoretically, the load rate of a transformer should be between 0 and 1 and had some effect on the utilization and life of the transformer.The load rate of a transformer should not be too low. In order to take full advantage of the transformer, the actual running load rate should be as close toγ as possible, where γ is the maximum load rate meeting the “N-1” principle of the main transformer.The load rate of a transformer should not be too high. Theoretically, the actual running load rate should not exceedγ even when the transformer carried the maximum load. Based on the “N-1” principle, the load rate of the substation with 2 transformers should not be higher than 0.65 and the load rate of the substation with 3 transformers should not be higher than 0.87. Long time of overload running will not only shorten the life of the transformer but also make great damage to the transformer.We concluded that the transformer was fully and reasonably utilized when the load rate was as close as possible to but no larger thanγ.In the previous studies, some methods have taken into account the cost but paid little attention to the load rate of the transformer, which led to the result that some substations’ load rates were too high. Some methods, including the weighted Voronoi diagram, have taken into account the load rate of the transformer, but the total capacity of the substations in the planning result may be much bigger than the plan needs, which led to the increase of the investment.Taking into account the issues above, we proposed two improvements based on the WVD.(1)
Capacity optimization mentioned in Section3: it ensured that the total capacity of the substations would not be much bigger than the plan needs.
(2)
Transportation model: it could estimate the power supply range for every substation and ensure that the load rate of every substation would be as close as possible to but not more thanγ.


### 4.1. The Transportation Model

The transportation model is a method of simulating real life situations with mathematical equations, graphs, images, and diagrams to describe the character of real system and future behavior. A transportation problem model is composed of decision variables, constraint conditions, and objective functions, all of which are calculated together to find an optimum solution.Transport model which is shown in Figure3: A
i
(
i
=
1,2
,
…
,
m
) represents that there are m production origins. B
j
(
j
=
1,2
,
…
,
n
) denotes that there are n sale places. a
i is the production supplied by A
i and b
j is the needs of B
j. The unit cost from A
i to B
j is c
i
j.Figure 3
Transportation model.Figure 4
Power supply range by the transport model.In transport model, it becomes a balance problem of production and needs when total production∑
i
=
1
m
a
i is equal to total needs ∑
j
=
1
n
b
j. In this case, x
i
j is the traffic transported from A
i to B
j. The transport model is as follows:
(12)
min
⁡
z
=
∑
j
=
1
n
∑
i
=
1
m
c
i
j
x
i
j
,
∑
j
=
1
n
x
i
j
=
a
i
(
i
=
1,2
,
…
,
m
)
,
∑
i
=
1
m
x
i
j
=
b
j
(
j
=
1,2
,
…
,
n
)
,
x
i
j
≥
0
(
i
=
1,2
,
…
,
m
;
j
=
1,2
,
…
,
n
)
,
where ∑
i
=
1
m
a
i
=
∑
j
=
1
n
b
j. Obviously, it is a linear programming problem and there are many methods to solve it. But transportation structure itself has certain particularity, so people often use the minimum element method or maximum variance method to solve it.


### 4.2. Algorithm Flow

Step 1 (preparation of the data).
The location and the capacity of every substation which are calculated by the WVD should be prepared.Step 2.
Calculation of the power supply range for every substation by the transportation model.Step 3 (check).
The distance between the load and its corresponding substation should be shorter than the maximum allowable power distance of the substation. The load whose distance did not meet this requirement should be connected to the nearest substation and then we use Step2 for the remaining loads.Step 4.
Cost settlement takes place and record the relationship between loads and substations.


## 4.1. The Transportation Model

The transportation model is a method of simulating real life situations with mathematical equations, graphs, images, and diagrams to describe the character of real system and future behavior. A transportation problem model is composed of decision variables, constraint conditions, and objective functions, all of which are calculated together to find an optimum solution.Transport model which is shown in Figure3: A
i
(
i
=
1,2
,
…
,
m
) represents that there are m production origins. B
j
(
j
=
1,2
,
…
,
n
) denotes that there are n sale places. a
i is the production supplied by A
i and b
j is the needs of B
j. The unit cost from A
i to B
j is c
i
j.Figure 3
Transportation model.Figure 4
Power supply range by the transport model.In transport model, it becomes a balance problem of production and needs when total production∑
i
=
1
m
a
i is equal to total needs ∑
j
=
1
n
b
j. In this case, x
i
j is the traffic transported from A
i to B
j. The transport model is as follows:
(12)
min
⁡
z
=
∑
j
=
1
n
∑
i
=
1
m
c
i
j
x
i
j
,
∑
j
=
1
n
x
i
j
=
a
i
(
i
=
1,2
,
…
,
m
)
,
∑
i
=
1
m
x
i
j
=
b
j
(
j
=
1,2
,
…
,
n
)
,
x
i
j
≥
0
(
i
=
1,2
,
…
,
m
;
j
=
1,2
,
…
,
n
)
,
where ∑
i
=
1
m
a
i
=
∑
j
=
1
n
b
j. Obviously, it is a linear programming problem and there are many methods to solve it. But transportation structure itself has certain particularity, so people often use the minimum element method or maximum variance method to solve it.


## 4.2. Algorithm Flow

Step 1 (preparation of the data).
The location and the capacity of every substation which are calculated by the WVD should be prepared.Step 2.
Calculation of the power supply range for every substation by the transportation model.Step 3 (check).
The distance between the load and its corresponding substation should be shorter than the maximum allowable power distance of the substation. The load whose distance did not meet this requirement should be connected to the nearest substation and then we use Step2 for the remaining loads.Step 4.
Cost settlement takes place and record the relationship between loads and substations.


## 5. Case Analysis

We chose four substation capacity scales for planning a 110 kV substation: 2 × 40 MVA, 2 × 50 MVA, 3 × 40 MVA, and 3 × 50 MVA. The regionR had a size of 118.08 km2. The total forecasted load of the target year was 2648.43 MW. This planning region was a new underplanning region without any constructed substation.This example was simulated by using a WVD algorithm and the ordinary Voronoi diagram algorithm, whose results are shown in Figures5 and 6. Their actual load rates are shown in Table 2.Table 2
Load rate.
Substation number
Conventional algorithm [29]
The original WVD [30]
Transportation model
1
0.86
0.76
0.80
2
0.72
0.72
0.87
3
0.82
0.85
0.87
4
0.98
0.78
0.81
5
0.88
0.84
0.87
6
0.76
0.76
0.87
7
0.84
0.84
0.87
8
0.91
0.63
0.87
9
0.93
0.79
0.87
10
0.86
0.85
0.77
11
0.89
0.64
0.87
12
0.86
0.87
0.81
13
0.88
0.63
0.80
14
0.89
0.80
0.87
15
0.90
0.73
0.80
16
0.71
0.87
0.87
17
0.90
0.75
0.87
18
0.87
0.82
0.85
19
0.87
0.79
0.82
20
0.53
0.71
0.87
21
0.85
0.86
0.87
22
0.90
0.75
0.84
23
0.78
24
0.83
Cost (million dollars)
157.58
157.12
146.98
Running Time of the Program (s)
89
4
5
Conditions: Windows XP Core (TM) 2 Duo CPU 2.0 GHz  RAM 2.0 GB.Figure 5
Planning result by the improved WVD.Figure 6
Planning result by the original WVD.Figure7 shows that the final plan by the improved WVD has 22 newly constructed substations and their capacities are all 3 × 50 MVA while the plan by the original WVD has 24 newly constructed substations as shown in Figure 6. When the areas A, B, and C which cannot build substations are added, as shown in Figure 7, 7 substations are removed from these areas and in addition it should be noted that the other substations have also changed their locations.Figure 7
Planning result by adding the areas that cannot build substations.From Table2, we have the following.(1)
The load rate: the load rates of the conventional algorithm are uneven. Some of them are too large and some of them are too small, which is unreasonable. The load rates of the original WVD are all under 0.87, but some of them are too small. The load rates of our proposed method are as close as possible to but not more than 0.87, which meets the load rate requirements.
(2)
The cost: the cost of the conventional algorithm is the highest, which is attributed to cost of the long cables caused by the unreasonable power supply range. The cost of the original WVD is higher because it needs more substations. The cost of this paper’s method is the lowest.
(3)
The running time of the program: the speed of the original WVD and this paper’s method are much faster than the conventional algorithm.


## 6. Conclusion

In this paper, an improved substation locating and sizing method based on the weighted Voronoi diagram (WVD) and the transportation model was proposed. There are three main improvements: the self-adjustment weight and the capacity optimization based on the WVD. We could get more reasonable substation sites and capacity collocation by them. The transportation model was used to calculate the power supply, which could get a reasonable load rate for each substation. In addition, geographic factors were also considered in this study; the substations can be moved out of the forbidden areas automatically.The proposed method is a more comprehensive and more integrated approach to the substation locating and sizing, which has been applied to practical engineering. This work will lay the foundation for power wiring.



---

*Source: 810607-2014-05-04.xml*