Transcript ppt

Peak Shaving and Price Saving
Algorithms for self-generation
David Craigie
_______________________________________________________
Supervised by: Prof. Andy Philpott Dr Golbon Zakeri
Today
• Demand side management
• Contracting & Self-Generation
• The Peak Shaving Problem
• The Peak Shaving Algorithm
• Example using UoA demand data
• The stochastic problem
• Conclusions
• Future Work
• Questions
1/25
Demand Side Management
• Conservation
• Load Shifting
• Contracting
• Self-Generation
2/25
Contracting & Self-Generation
• CFDs don’t alter optimal self-generation
strategy:
Charge (in period t) =
where
dt pt  dc ( pc  pt )
dt = demand realised in period t
pt = spot market price in period t
dc = swap volume
pc = strike price
(based on Mercury Energy’s Swap Contracts)
3/25
The Peak Shaving Problem
The deterministic peak shaving problem can be stated:
Given a load profile, price profile and a capacity of
generation, find the optimal allocation of a limited
quantity of generator fuel with a sunk cost in order
to minimize the cost of electricity consumption.
Or:
Allow for an unlimited amount of fuel but at a given
unit cost. However, the algorithm is the same in
either case, only the stopping criterion changes.
4/25
The Peak Shaving Problem
5/25
• Objective:
N
min  di  e.si  pi  c.md
where:
di =
pi =
si =
e =
c =
N =
md =
i 1
demand in period i
spot market price in period i
fuel used in period i
generator efficiency
maximum demand charge
number of periods
average of m highest load realisations during N
By setting e = 1 and removing constant terms:
N
min   pi si  c.md
i 1
[MWh]
[$/MWh]
[L]
[MWh/L]
[$/MWh]
[MWh]
The Peak Shaving Problem
•
Constraints:
(i)
Total fuel allocation cannot exceed available quantity:
N
 si  T
i 1
(ii)
Fuel allocation in any period cannot exceed generator capacity:
si  k
(iii)
i 1, 2, ... , N
The maximum demand quantity must be equal to the greatest sum of m
demands after generation:
md 
 (d j  s j )
jM i
i  1, 2, ... , N Cm
where Mi is the set giving the ith way of choosing m periods from a
possible N.
6/25
The Peak Shaving Algorithm
The combinatorial number of maximum demand
constraints makes the Peak Shaving Problem
intractable for the RSM.
However, we can use a greedy algorithm that will
give the same solution as the RSM but without the
computational cost.
At every iteration the algorithm will choose a period
to allocate fuel to that will give the maximum
savings. It will cease allocation to that period when
either capacity of the generator is reached, fuel
supply is exhausted or savings need to be
recalculated.
7/25
Peak Shaving Example
8/25
Suppose we will be charged for the average of the
highest 2 load realizations in the following five period
demand profile, at a rate of $30/MWh:
Initial Load Profile
14
Load (MWh)
12
10
8
6
4
2
0
1
2
3
4
5
period
p1=72
p2=68
5
Initial Cost =
p3=60
[$/MWh]
p4=65
p5=85
 d i pi + 15(12+11) = $3,317
i 1
Peak Shaving Example
9/25
Suppose we have 16MWh worth of fuel, but the capacity
in any one period is 4MWh. We seek the allocation of fuel
among the 5 periods that will obtain the greatest savings:
Iteration 1
Period
Load
Price
MD
Saving
Range
Alloc.
1
6
72
N
72
4
0
2
10
68
N
68
4
0
3
12
60
Y
75
2
0
4
11
65
Y
80
1
0
5
5
85
N
85
4
0
Decision: Allocate 4MWh to period 5 (12MWh remaining)
Peak Shaving Example
10/25
Iteration 2
Period
Load
Price
MD
Saving
Range
Alloc.
1
6
72
N
72
4
0
2
10
68
N
68
4
0
3
12
60
Y
75
2
0
4
11
65
Y
80
1
0
5
1
85
N
0
0
4
Decision: Allocate 1MWh to period 4 (11MWh remaining)
Current Load Profile:
Load Profile after 2 Iterations
14
Load (MWh)
12
10
8
6
4
2
0
1
2
3
period
4
5
Peak Shaving Example
11/25
Iteration 3
Period
Load
Price
MD
Saving
Range
Alloc.
1
6
72
N
72
4
0
2
10
68
N
68
4
0
3
12
60
Y
75
2
0
4
10
65
N
65
3
1
5
1
85
N
0
0
4
74*
3
{2,4}
*Saving for {2,4} = 1/2 x (68 + 65) + 1/2 x 15
Decision: Allocate 2MWh to period 3 (9MWh remaining)
Load Profile after 3 Iterations
12
Load (MWh)
10
8
6
4
2
0
1
2
3
period
4
5
Peak Shaving Example
12/25
Iteration 4
Period
Load
Price
MD
Saving
Range
Alloc.
1
6
72
N
72
4
0
2
10
68
N
68
4
0
3
10
60
N
60
2
2
4
10
65
N
65
3
1
5
1
85
N
0
0
4
{2,4}
74
2
{2,3,4}
74.33*
2
*Saving for {2,3,4} = 1/3 x (68 + 65 + 60) + 2/3 x 15
In general the savings from an n-period MD set tie are:
1/n x (p1+ p2 + … + pn) + (n-1/n) x c
Thus the best tie to consider will be the highest priced n
periods where n maximizes the above expression
Decision: Allocate 2MWh to periods 2,3 and 4 (3MWh
remaining)
Peak Shaving Example
13/25
Iteration 5
Period
Load
Price
MD
Saving
Range
Alloc.
1
6
72
N
72
3
0
2
8
68
N
68
2
2
3
8
60
N
0
0
4
4
8
65
N
65
1
3
5
1
85
N
0
0
4
74
1
{2,4}
Decision: Allocate 1MWh to periods 2 and 4 (1MWh remaining)
Iteration 6
Period
Load
Price
MD
Saving
Range
Alloc.
1
6
72
N
72
1
0
2
7
68
N
68
1
3
3
8
60
Y
0
0
4
4
7
65
N
0
0
4
5
1
85
N
0
0
4
Decision: Allocate 1MWh to period 1 - STOP
Peak Shaving Example
14/25
Before:
Initial Load Profile
14
Load (MWh)
12
10
8
6
4
2
0
1
2
3
4
5
4
5
period
Cost = $3,317
After:
Final Load Profile
14
Load (MWh)
12
10
8
6
4
2
0
1
2
3
period
Cost = $2,081
UoA Example
15/25
Using demand data from 18 Symonds St (Engineering
Building) for the month of August (1488 periods) and
price data from OTA reference node.
Using a 100kW generator at 3.6kWh/L with 14000L of
fuel. Maximum demand charge of $8/kWh multiplied by
the average of the 10 highest load realisations.
Before: $36,164
After: $32,102
Change in max load periods
590
load (kWh)
580
570
560
Before
550
After
540
530
520
1
2
3
4
5
6
7
8
9
10 11 12 13 14
Dual Simplex Approach
We can solve a relaxed version of the LP by removing all
the maximum demand constraints. This solution will
(most likely) be infeasible in the original problem, but we
know at least one of the constraints it violates, so we can
add that constraint and resolve using the Dual Simplex
Algorithm.
We continue to add constraints until they cease to change
the solution. By doing this we will obtain all the binding
constraints from the optimal solution of the original
problem.
Depending on how many of the maximum demand
constraints are binding in the optimal solution of the
original LP, this may be a faster approach.
16/25
Dual Simplex Approach
Iteration 1:
min 
N
p
i 1
i
s
i

T
si

k
i 1
Iteration 2:
 c.md
si
N
s.t.
17/25
i  1,2, ... , N
N
min   p i s i  c.md
i 1
N
s.t.
s
i 1
i
si
 T

md 
i  1,2, ... , N
k

jM i
(d j  s j )
Iteration 3:
N
min   p i s i
 c.md
i 1
N
s.t.
s
i 1
i
si
etc…
 T

md 
i  1,2, ... , N
k

jM i
md 

jM k
(d j  s j )
(d
j
 sj)
Stochastic Problem
18/25
Scenario tree for prices (3 periods only)…
S21
S31
S1
S22
S32
Stochastic Problem
19/25
N = 3, m = 2. Complete Stochastic LP formulation:
min    ij sij  c1 md1  c 2 md 2
i, j
s.t.
s1  s 21  s31  T
s1  s 22  s32  T
sij  k
i, j
md1  (d1  s1 )  (d 2  s 21 )
md1  (d1  s1 )  (d 3  s31 )
md1  (d 2  s 21 )  (d 3  s31 )
md 2  (d1  s1 )  (d 2  s 22 )
md 2  (d1  s1 )  (d 3  s32 )
md 2  (d 2  s 22 )  (d 3  s32 )
Stochastic Problem
20/25
Use Dual Simplex approach:
Iteration 1: min   s  c md  c md
 ij ij 1 1 2 2
i, j
s.t.
s1  s 21  s31  T
s1  s 22  s32  T
Iteration 2:
sij  k
i, j
min   ij sij  c1md1  c2 md2
i, j
s.t.
s1  s21  s31  T
s1  s22  s32  T
sij  k
i, j
md1  (d1  s1 )  (d 2  s21 )
etc…
md2  (d1  s1 )  (d 3  s31 )
Stochastic Problem
21/25
Dynamic Programming Approach:
(dt  st ) p j  c. max{ md , (dt  st )}  c.md 
Vt ( St , md , i)  min   ij 

st

V
(
S

s
,
max{
md
,
(
d

s
)},
j
)
j
t
t
 t 1 t t

where :
St  fuel remaining at start of period t
md  maximum demand realised so far
d t  demand in period t
pi  spot market price in state i
ij  the probability of transition from state i to state j
c  maximum demand charge
st  fuel allocated in period t (decision variable)

Stochastic Problem
22/25
Dynamic Programming Approach:
(dt  st ) p j  c. max{ md , (dt  st )}  c.md 
Vt ( St , md , i)  min   ij 

st

V
(
S

s
,
max{
md
,
(
d

s
)},
j
)
j
t
t
 t 1 t t

This approach works when the size of the maximum
demand set is 1 (as in the recursion above) or close to
1. However when m=10, we need to store 10
demands and consequently the state space “explodes”
(curse of dimensionality).
To overcome this problem, we might consider storing
the 1st and 10th highest demands and interpolating
between these.

Conclusions
• Under normal market conditions, self generation using
diesel generators is not economical.
• However, if fuel is needed as a backup supply and is
approaching expiration there is an optimal way to use
it.
• Formulated as an LP the Peak Shaving problem is
intractable for the RSM.
• A relatively simply greedy algorithm exists that will
determine the optimal allocation.
• Alternatively, a dual simplex approach can be
employed.
• The stochastic problem is significantly larger and
requires a large number of constraints if formulated
using an SLP or an enormous state space if formulated
as a DP.
23/25
Future Work
•
Is the stochastic problem more sensitive to demand or price
uncertainty? Are we better to use the SLP and trim the scenario
tree, or the DP and interpolate the state space?
•
Is back-up generation really worth it? Given that peak shaving can
reduce the cost of this security of supply, how risk averse does
one need to be for back-up generation to be a sensible strategy.
•
The level of contracting does not alter the optimal self generation
plan but the converse is not necessarily true. Does the added
security of back-up generation alter the optimal contract – spot
mix.
•
Other demand side questions:
– Would a liquid hedge market enable large consumers to more
effectively manage price risk and at less cost?
– Can better contracts be negotiated by consumers acting as a
group?
– What about demand side bids?
– Every little bit counts: Are there optimal conservation
strategies? How valuable are they?
24/25
25/25
Thank You For Listening. Questions?