Agg ega ing Ene gy Flexibili ies unde Cons ain s
Emmanouil Valsoma zis and To ben Bach Pede sen
Aalbo g Uni e si y
Email: {e alsoma, bp}@cs.aau.dk
Albe o Abell´
o
Uni e si a Poli `
ecnica de Ca alunya
Email: [email p o ec ed]
Ka ja Hose
Aalbo g Uni e si y
Email: [email p o ec ed]
Abs ac —The lexibili y o indi idual ene gy p osume s (p o-
duce s and/o consume s) has d awn a lo o a en ion in ecen
yea s. Agg ega ion o such lexibili ies p o ides p osume s wi h
he oppo uni y o di ec ly pa icipa e in he ene gy ma ke
and a he same ime educes he complexi y o scheduling
he ene gy uni s. Howe e , agg ega ed lexibili y should suppo
no mal g id ope a ion. In his pape , we build on he lex-o e
(FO) concep o model he inhe en lexibili y o a p osume
(e.g., a single lexible consump ion de ice such as a clo hes
washe ). An FO cap u es lexibili y in bo h ime and amoun
dimensions. We de ine he p oblem o agg ega ing FOs aking in o
accoun g id powe cons ain s. We also p opose wo cons ain -
based agg ega ion echniques ha e icien ly agg ega e FOs while
e aining lexibili y. We show h ough a comp ehensi e e alua ion
ha ou echniques, in con as o s a e-o - he-a echniques,
espec he cons ain s imposed by he elec ical g id. Mo eo e ,
ou echniques also educe he scheduling inpu size signi ican ly
and imp o e he quali y o scheduling esul s.
I. INTRODUCTION
One o he main goals o he Sma G id is he ene gy use in-
c ease om Renewable Ene gy Sou ces (RES). Howe e , due
o RES being cha ac e ized by ola ile powe p oduc ion (e.g.,
wind powe ), Sma G id akes ad an age o he p osume s’
inhe en lexibili y o be e ma ch ene gy demand wi h supply,
e med Demand Response (DR), and hus enables an inc eased
sha e o RES ene gy.
In ou wo k, we model lexible demand/supply de ices
( e e ed o as loads o simpli ica ion) using he lex-o e
(FO) concep [1]. An FO explici ly cap u es he lexibili y
in ene gy and ime o a load, as p esen ed in he ollowing
example.
Example 1. The owne (consume ) o an elec ic ehicle (EV)
wan s o cha ge his EV a 20:00 and ha e i cha ged by 7:00
he ollowing day. The EV akes 3hou s o be cha ged and
equi es 15kWh. Thus, he EV can s a i s cha ging be ween
20:00 and 4:00.
The numbe o loads ha a e lexible has ecen ly inc eased
due o new echnological achie emen s (e.g., EVs and hea
pumps). The exis ence o app op ia e in o ma ion and com-
munica ion echnology (ICT) in as uc u e [2] and a sui able
hie a chical con ol a chi ec u e, o e he capabili y o ma ke
ac o s o command he DR [3]. Mo eo e , he es ablishmen
o a lexibili y ma ke [4] will p o ide lexibili y wi h he
oppo uni y o be aded [5]. Howe e , he ene gy cap u ed
by indi idual FOs om small load de ices canno be di ec ly
aded in he ma ke [6]. Fo ins ance, he powe equi ed o
pa icipa e in he ancilla y se ice ma ke in Denma k is in
he magni ude o ew hund eds o kW whe e he consump ion
capaci y o an EV is ew kW [6]. Thus, in o de o ade lexi-
bili y, i is essen ial o agg ega e FOs and p oduce commodi ies
ha can be aded in he eme ging ene gy lexibili y ma ke s.
Fu he mo e, agg ega ion o FOs, applied be o e scheduling,
is essen ial o educe he highly complex Uni Commi men
(UC) p oblem [7]. Acco ding o he UC p oblem, FOs a e
scheduled, i.e., he ope a ional ime and amoun is de ined,
based on an objec i e unc ion.
On he o he hand, lexible loads and, consequen ly, hei
co esponding FOs a e connec ed o an elec ical g id. How-
e e , he g id is cha ac e ized by powe capaci y limi a ions
and he high powe equi emen s o new de ices, such as EVs,
migh lead o g id conges ions. G id sensi i e load loca ions
(bo lenecks) a e in di e en ol age elemen s. They could be
in low (local dis ibu ion) and in high ol age elemen s (sup a-
egional dis ibu ion). Fo ins ance, a bo leneck migh be a
dis ibu ion ans o me (0.4-1kV) wi h a maximum powe
alue o ew hund ed kW. Such a ans o me migh se e om
ew (e.g., in No h Ame ica) o se e al hund ed households
(e.g., in Eu ope) [8].
In ou wo k, we ollow he mapping applied in [9] and
map a bo leneck o he oo o a ee, see R in Figu e 1.
The oo is cha ac e ized by an amoun cons ain ha de ines
he ole able ope a ional powe ange. Fo ins ance, he powe
o a dis ibu ion ans o me (0.4kV) shall be in he in e al
[-300kW, 300kW] [3]. We also map all FOs, which belong
o he bo leneck, o he lea nodes, see 1 in Figu e 1. The
le mos ci cle in he igu e illus a es an FO co esponding
o he load o an EV. The x-axis ep esen s ime and he y-
axis ep esen s powe . The ene gy equi ed o cha ging he
EV is exp essed by h ee slices (one pe ime uni ). The da k-
shadowed pa s ep esen he minimum ene gy equi emen s.
The ligh -shadowed pa s ep esen op ional cha ging le els.
Fo ins ance, he EV owne is sa is ied when cha ging le el is
in he ange [60%,100%]. Mo eo e , as we see in he igu e,
cha ging o he EV can s a a ime 1 a he ea lies ( es)
and a ime 5 a he la es ( ls). Thus, he FO p o ile, which
consis s o he h ee slices, can be ime-shi ed.
Using adi ional agg ega ion echniques [10], he FOs a e
agg ega ed esul ing in agg ega ed FOs (AFOs). As illus a ed
in Figu e 1, he ou FOs 1 a e agg ega ed in o wo AFOs 2 .
Each p o ile o an AFO is p oduced by summing up one o
mo e p o iles o he 4 FOs. Wi hou conside ing cons ain s,
loads migh be placed a he same ime since i may be mo e
bene icial, e.g., om a inancial poin o iew. Howe e , his
could lead o iola ions. Fo ins ance, we see ha he powe
© 2016 IEEE. Pe sonal use o his ma e ial is pe mi ed. Pe mission om IEEE mus be ob ained o all o he uses, in any cu en o u u e media, including
ep in ing/ epublishing his ma e ial o ad e ising o p omo ional pu poses,c ea ing new collec i e wo ks, o esale o edis ibu ion o se e s o lis s, o euse
o any copy igh ed componen o his wo k in o he wo ks. DOI 10.1109/Sma G idComm.2016.7778808
R
AFOs
T ading
Scheduling
Viola ion No mal ope a ion
T adi ional
(Ou solu ion)
agg ega ion
300kW
-300kW
ICT in as uc u e
2
0.4kV
AFOs
T ading
Scheduling
300kW
-300kW
0
+
-
0
+
-
2'
33'
0
+
-
0
-
+
0
-
+
0
+
-
Cons ain -based
agg ega ion
De ices/FOs
-
0
1
44'
0
+
n as uc u e
0
-
0
+
-300kW
300kW
-300kW
300kW
es ls
powe alue
ime
15
Powe
Fig. 1: T adi ional s Cons ain -based agg ega ion.
o he le AFO ( i s da k-shadowed slice in 2 ) exceeds he
cons ain imposed by he g id. A e being agg ega ed, he
AFOs a e aded and scheduled, see 3 . Scheduling ans o ms
AFOs in o assignmen s and o ms he oo powe alue.
Howe e , i is impossible o schedule he ou pu o adi ional
agg ega ion and o espec he cons ain . Thus, scheduling
leads o a cons ain iola ion due o inapp op ia e agg ega ion,
see 4 whe e he powe alue exceeds 300kW in he i s ime
slo ( ed ci cle). Consequen ly, FO agg ega ion echniques ha
ake in o accoun g id cons ain s a e equi ed. In his pape ,
we p opose such cons ain -based agg ega ion which p oduces
AFOs ha can be u he scheduled and suppo a no mal g id
ope a ion, see 2' - 4' in Figu e 1.
Con ibu ions. Fi s , we demons a e he p oblems ha
occu wi h adi ional FO agg ega ion. Second, we in oduce
he objec i es o cons ain -based FO agg ega ion and p opose
wo heu is ic agg ega ion echniques ha educe he inpu by
mo e han 90% while e aining lexibili y. Thi d, we e alua e
he p oposed echniques in complex use case scena ios. We
show ha ou echniques lead o no mal g id ope a ion whe e
he exis ing s a e-o - he-a app oaches lead o g id cons ain
iola ions a mo e han 15% o he examined ime ho izon. Fi-
nally, we show ha in cases whe e scheduling canno p o ide
a schedule ha espec s g id cons ain s wi hin a ce ain ime
pe iod, ou agg ega ion echniques e icien ly na ow down he
solu ion space and hus lead o alid scheduling esul s.
The emainde o he pape is s uc u ed as ollows. Sec-
ion II in oduces ele an concep s and de ini ions. Sec ion III
discusses he p oblems o adi ional agg ega ion and in o-
duces cons ain -based agg ega ion objec i es. In Sec ion IV,
he wo cons ain agg ega ion solu ions a e p oposed. Thei
expe imen al e alua ion is desc ibed in Sec ion V. In Sec-
ion VI ela ed wo k is discussed. Finally, he pape concludes
and poin s o u u e wo k in Sec ion VII.
II. BACKGROUND AND PRELIMINARIES
Based on [10] and using wo disc e e dimensions, i.e., ime
and amoun , we de ine he ollowing.
De ini ion 1. An FO is a uple = (T( ), P ( )) whe e
T( )is he s a ime lexibili y in e al and P( )is he
amoun p o ile. T( ) = [ es, ls]whe e es and ls a e he
ea lies s a ime and la es s a ime, espec i ely. The
amoun p o ile is a sequence o (m∈N>0) consecu i e slices,
P( ) = hs(1), . . . , s(m)iwhe e a slice s(i)is an amoun
ange [amin, amax]. The du a ion o slices is 1 ime uni . Fo
ins ance, Figu e 2 illus a es FO = ([1,5],h[3,5],[2,3]i).
We dis inguish wo ypes o lexibili ies
Fig. 2: A lex-o e
associa ed wi h an FO ha
a e used as indi idual mea-
su es aking in o accoun
ime and amoun sepa a ely.
We conside ime lexibili y
( )o an FO o be he
di e ence be ween i s la es
and ea lies s a ime, i.e.,
( ) = ls − es. Mo e-
o e , we conside amoun
lexibili y a ( )o an FO
o be he di e ence be ween
he sum o all he maxi-
mum and minimum alues o all i s slices, i.e., a ( ) =
Ps∈P( )(s.amax −s.amin). Time lexibili y is measu ed in
ime uni s and amoun lexibili y in amoun uni s.
An FO cap u es all possible amoun demands and/o sup-
plies o a de ice o a gi en ime ho izon. Howe e , du ing
he scheduling p ocess, an FO is assigned o a speci ic amoun
a a speci ic ime esul ing in an assignmen o he FO de ined
as ollows:
De ini ion 2. An assignmen o an FO is a sequence o
|P( )| ∈ N>0consecu i e slices, as =hs(1), ..., s(|P( )|)i.
Each slice is a 2- uple, s(i)=( s, am), i ∈[1,|P( )|]. The i s
elemen , s, indica es he ac ual s a ing ime and he second
one, am, he ac ual amoun o he slice. The du a ion o each
slice is 1 ime uni .
The s a ing ime o he i s slice o he assignmen mus
be wi hin he s a ime lexibili y in e al o he FO, i.e.,
. es ≤as .s(1). s≤ . ls. Each slice o he assignmen
has an amoun alue in he ange o he co esponding slice
o he FO, i.e., .s(i).amin ≤a .s(i).am ≤ .s(i).amax,
∀i= [1 . . . |P( )|]. The e is a ini e numbe o assignmen s
o an FO. We deno e he se o all he assignmen s o an FO
by L( ).
III. PROBLEM FORMULATION
In his sec ion, we discuss how agg ega ion is applied
h ough adi ional agg ega ion and in oduce he concep o
cons ain -based agg ega ion.
A. T adi ional FO agg ega ion
We conside , based on [10], adi ional agg ega ion o FOs
o be he unc ion ha gi en a se o FOs e u ns an agg ega ed
one, aking in o accoun he ime and amoun lexibili ies o
he FOs. Gi en a se o FOs, he e a e di e en alignmen s
′
1
2
3
4
5
123
123
123123
123
123
1
2
3
4
1
2
3
4
1
2
3
4
5
1
2
3
4
1
2
3
4
cons ain
cons ain
cons ain
cons ain
cons ain
cons ain
(a) (b)
Fig. 3: Di e en alignmen examples o agg ega ion.
ha lead o di e en AFOs due o hei ime lexibili y. In pa -
icula , gi en |F|FOs wi h ime lexibili y ( 1),..., ( |F|)
espec i ely, he numbe o he agg ega ion esul s (AFOs) ha
can be p oduced is: Q|F|
i=1 ( i)+1. Fo ins ance, he 2 FOs,
1and 2in Figu e 3, can be di e en ly aligned and esul
in di e en AFOs. Thus, o 1and 2wi h bo h ob aining 3
di e en s a imes, he e a e 3·3=9alignmen s ha lead o
9 agg ega ion esul s (AFOs). We show 2 o hem in Figu e 3.
The ime lexibili y in e al o an AFO is de e mined by
he chosen alignmen s. In pa icula , he amoun p o ile o an
FO does no ha e any speci ied s a ing ime un il he FO is
assigned. Howe e , an FO cap u es all he di e en s a ing
imes in he s a ime lexibili y in e al, see De ini ion 1. As
a esul , when agg ega ion is applied, FOs ha pa icipa e in
agg ega ion a e aligned (a s a ing ime among he in e al is
chosen o e e y FO) and he amoun anges o each aligned
slice a e summed, see Figu e 3. We deno e he agg ega ion
ha aligns FOs acco ding o hei ea lies s a ime as S a
Alignmen (SA) agg ega ion, see Figu e 3a. Acco ding o
SA agg ega ion, he ea lies s a ing ime o he AFO is he
minimum ea lies s a ing ime o he non-agg ega ed FOs.
The la es s a ing ime o he AFO is he sum o i s ea lies
s a ing ime and he minimum ime lexibili y among he
FOs. As a esul , he AFO espec s all he s a ing ime
in e als o he non-agg ega ed FOs ha p oduced i . Fo
ins ance, he AFO a
12 in Figu e 3 has ea lies s a ing ime 1
( a
12. es =min( 1. es, 2. es)). The la es s a ing ime ( ls)
o a
12 is equal o 3 ( a
12. ls = a
12. es +min( ( 1), ( 2))).
B. Cons ain agg ega ion objec i es and complexi y
As men ioned in Sec ion I, he alue o a node (ac ual
load) is gi en by he assignmen s o he FOs ha belong o
he node. In pa icula , du ing scheduling each FO is u ned
in o an assignmen and he esul is a se o assignmen s.
Consequen ly, he sum o he slice amoun s wi h he same
ime o ms he node alue a ha ime. Howe e , in o de o
gua an ee a no mal g id ope a ion, he ac ual loads o he g id
mus be wi hin he bounds imposed by he cons ain , e.g.,
[-300kW, 300kW]. Fo ins ance, concu en ly cha ging a high
numbe o EVs can lead o ans o me o e load.
We assume ha FOs 1and 2in Figu e 3 belong o a node
wi h cons ain alue 2. Mo eo e , we see ha he agg ega ion
esul ( a
12 las ow column a) o SA does no enable an
assignmen ha espec s he cons ain . When scheduling is
applied on a
12, he e a e se e al po en ial assignmen s o a
12,
e.g., as a1
12 = (1,3) and as a2
12 = (2,4), see Figu e 3a.
Howe e , he cons ain alue is 2and he amoun s o all he
assignmen s a e g ea e han he cons ain . They should ha e
been wi hin he ange [-2,2]. Con e sely, we see ha when
FO agg ega ion akes in o accoun he cons ain , i p oduces
AFO b
12 (Figu e 3b) ha con ains assignmen s which espec
he cons ain , e.g., as b
12 =h(2,2),(3,1)i. In his pape ,
we e alua e an agg ega ion esul h ough he objec i es o
cons ain -based agg ega ion.
Cons ain -based FO agg ega ion has 3objec i es. The p o-
duced AFOs (1) shall enable scheduling esul s ha espec he
cons ain o he node whe e he FOs belong (ha d cons ain ).
Mo eo e , (2) agg ega ion should e ain as much lexibili y as
possible and (3) a he same ime educe he numbe o FOs
ha belong o a speci ic node.
1) Respec node cons ain s. All node cons ain s should
be espec ed. A node cons ain iola ion co esponds o a g id
mal unc ion a he poin whe e he node is. Tha esul s in
se ice cu o o FOs ha belong o he iola ed node and
hus he p osume s migh no be se ed.
2) Minimize lexibili y losses. Flexibili y o FOs is im-
po an o scheduling because he mo e lexible FOs a e, he
mo e deg ees o eedom he scheduling has o ind he op imal
solu ion. Mo eo e , AFOs cap u e la ge lexibili ies and can
mo e easily be aded in he ene gy ma ke . We use lexibili y
as a quali y measu e o e alua e ou p oposed echniques, as
AFOs migh lose lexibili y du ing agg ega ion.
3) Minimize he numbe o AFOs. FOs a e pa o he
scheduling inpu ha akes place a e agg ega ion. The e o e,
i is impo an o cons ain agg ega ion o educe he numbe
o FOs, because i di ec ly educes he complexi y o he
subsequen scheduling. Mo eo e , unless FOs a e agg ega ed
o cap u e la ge ene gy amoun s, hey canno be aded in he
ene gy ma ke .
The abo e-men ioned objec i es migh be con adic o y and
canno be sa is ied simul aneously. In pa icula , as he numbe
o AFOs is educed, ime lexibili y losses migh inc ease
and ime lexibili y migh be used o espec he cons ain .
Fo ins ance, we see in Figu e 3a ha 1and 2ha e ime
lexibili y 2. Howe e , AFO b
12 has ( b
12)=1.
Cons ain agg ega ion complexi y. Due o space limi a-
ions, we illus a e he compu a ional complexi y o cons ain -
based agg ega ion h ough an example. In ou example, gi en
a se o FOs, we compu e he o al solu ion space, i.e., he
numbe o all he po en ial agg ega ion esul s.
Example 2. Gi en a se Fo 4FOs, 1, 2, 3, 4,
wi h ( 1)=3, ( 2)=2, ( 3)=4, ( 4)=5, he e a e
B4=P4
k=1 4
k=1
1! (−1)11
004+1
2! P2
j=0 2
jj4+
1
3! P3
j=0 3
jj4+1
4! P4
j=0 4
jj4= 1+7+6+1 = 15, pa i ions
o F[11]. Mo eo e , he e a e Q4
i=1 ( i)=3·2·4·5 = 60
alignmen s. Thus, he e a e 15·60 = 900 possible agg ega ion
esul s.
Adding a i h FO o he se wi h ( 5)=5, he e a e
B5=52 pa i ions o Fand Q5
i=1 ( i) =60 ·5=300 align-
men s. Thus, he e a e 52 ·300 = 15600 possible agg ega ion
esul s. The e o e, we can no ice a combina o ial explosion o
he agg ega ion esul s depending on he size o he inpu and
i s a e age ime lexibili y.
IV. CONSTRAINT-BASED FO AGGREGATION
Due o he high complexi y o cons ain -based agg ega ion,
we analyze wo a ia ions o a g eedy solu ion o ackle he
p oblem. In pa icula , he g eedy app oaches p ocess FOs
ha belong o a node inc emen ally by e alua ing bina y
agg ega ions. E alua ion is based on di e en me ics in o de
o examine whe he u he agg ega ion is a o ed o no . The
me ics ake in o accoun bo h he capaci y limi a ions o he
node and he objec i e o he ma ke ac o who con ols he
FOs o he node.
A. Cons ain and a ge ela ed dis ances
As men ioned in Sec ion I, in o de o gua an ee a no mal
g id ope a ion, he node alue shall be wi hin he bounds
imposed by he cons ain . In his pape , we handle he
cons ain as a unc ion.
De ini ion 3. We de ine a (cons an ) posi i e cons ain unc-
ion c( ) = y, ∈Z,y∈N0, whe e is he ime and y he
amoun .
Fo ins ance, gi en a cons ain unc ion c( )=300, he alid
amoun ange is [-300, 300]. In cases whe e he node alue
is ou side he cons ain bounds, a node iola ion occu s, see
o ins ance 4 in Figu e 1. When his happens, he elec ical
g id is no eliable and he dis ibu ion sys em ope a o , who is
esponsible o he g id, needs o expand and upda e he powe
sys em in as uc u e. Upda ing he g id is a e y expensi e
and ime consuming p ocedu e. In ou wo k, since he node
alue is o med by he assignmen s o he FOs, we co ela e an
assignmen o he cons ain unc ion. We conside he dis ance
o each slice o an assignmen (posi i e o nega i e) o be ze o
when i is wi hin he ange because no g id p oblems occu .
O he wise, we ake in o accoun he dis ance o he cons ain
unc ion.
De ini ion 4. We de ine he dis ance o a slice o an assign-
men ,Dc(as .s(i)), o a cons ain unc ion cas equal o
ze o i he absolu e slice amoun is smalle o equal o c.
O he wise, Dc(as .s(i))is equal o he di e ence be ween
he absolu e amoun alue o he slice and he cons ain ,
i.e., Dc(as .s(i)) = max(0,|s(i).am| − c(s(i). s)) whe e
as =hs(1), ..., s(|P( )|)iand i∈[1,|P( )|]. Consequen ly,
we de ine dis ance o an assignmen as ,Dc(as ), o a
cons ain unc ion c o be he sum o all i s slice dis ances o
c, i.e., Dc(as ) = P|P( )|
i=1 Dc(as .s(i)).
The objec i e o he ma ke ac o con olling he FOs o
a node, e.g., an agg ega o , is o mula ed h ough a a ge
unc ion. Ta ge exp esses he op imal schedule, wi hou con-
side ing he cons ain , and can be used o ep esen an op imal
business goal, e.g., op imal p ice/amoun co ela ion. Ta ge
migh con adic he cons ain and i could lead o AFOs
wi h assignmen s ha iola e he cons ain , see o ins ance
2 in Figu e 1. We de ine bo h he a ge unc ion and he
assignmen dis ance o he a ge unc ion as ollows:
De ini ion 5. We de ine a (cons an ) signed a ge unc ion
g( ) = a, whe e ∈Zis he ime and a∈Z he amoun .
De ini ion 6. We de ine he dis ance o an assignmen as
o a a ge unc ion g,Dg(as ), as equal o he sum o he
absolu e di e ences be ween gand he amoun alues o all he
slices o he assignmen , i.e., Dg(as ) = Pm
i=1 |g(s(i). s)−
s(i).am|, as =hs(1), ..., s(m)i.
In ou wo k, we ake in o accoun bo h he capaci y lim-
i a ions o he g id and he ma ke ac o ’s objec i e. Thus,
we conside bo h he dis ance o he cons ain and he a ge
unc ion o e alua e ou esul s. In pa icula , we ake in o
accoun he sum o he dis ances ( a ge and cons ain ) and we
use weigh s (coe icien s) o p io i ize he cons ain iola ion.
O cou se, when cons ain is espec ed, only he dis ance o
he a ge unc ion is aken in o accoun .
De ini ion 7. We de ine he dis ance o an assignmen as
o a a ge unc ion gand a cons ain unc ion c,Dg,c(as ),
as he weigh ed sum o i s a ge and cons ain dis ances
wi h weigh s αand β espec i ely, i.e., Dg,c(as ) = α·
Dg(as ) + β·Dc(as ),α, β ∈R.
As men ioned in Sec ion II, since an FO cap u es a se
o assignmen s (L( )), he e is a leas one assignmen o
ha has he smalles dis ance.
De ini ion 8. We de ine he a ge o cons ain dis ance o
a FO o a a ge unc ion gand a cons ain unc ion c,
Dg,c( ), as he minimum dis ance among all i s assignmen s
o gand c, i.e., Dg,c( ) = minas ∈L( )Dg,c(as ).
Example 3. Fo ins ance, gi en α= 1,β= 10,c( ) = 2,
and g( ) = 3, an assignmen o a
12 in Figu e 3 wi h he
minimum dis ance is: as a
12 = [1,3] whe e Dg,c(as a
12 ) =
1·0+10·1 = 10 = Dg,c( a
12 ). On he con a y, an assignmen
o b
12 wi h he minimum dis ance is: as b
12 =h[1,2],[1,2]i
whe e Dg,c(as b
12 )=1·(1 + 1) + 10 ·0 = 2 = Dg,c( b
12 ).
B. Agg ega ion echniques
We now p esen ou 2heu is ic cons ain -based FO ag-
g ega ion echniques. Bo h he echniques a e a ia ions o
he same abs ac G eedy algo i hm (Algo i hm 1). They s a
by selec ing (Line 2) he FO ( nom) wi h he maximum a -
ge o cons ain dis ance (max ∈SF (Dg,c( )). The eason is
ha apa om educing he numbe o he AFOs, agg ega ion
shall also p oduce FOs ha a e close o he a ge in o de
o imp o e scheduling esul s. Thus, s a ing agg ega ion wi h
FOs wi h high “dis ances” (used ins ead o a ge cons ain
dis ance o simpli ica ion) is desi able and inc eases he
chance o educing he o e all dis ance. Then, he selec ed FO,
nom, is emo ed om he ini ial se (Algo i hm 1, Line 2).
Algo i hm 1 Abs ac G eedy
Inpu : SF - se o FOs; g,c - a a ge and a cons ain unc ion
Ou pu : SF - se o AFOs
1: mp ←null; a←null;
2: nom ←Selec NomFO(SF); SF ←SF nom;
3: while ∃ ∈SF no agg ega ed do
4: { a, mp} ←Bes Agg ega ion(SF, nom)
5: i Dg,c( a)<Dg,c( nom) hen
6: SF ←SF mp; nom ← a
7: else
8: Anno a eAsAFO( nom)
9: SF ←SF ∪ nom
10: nom ←Selec NomFO(SF); SF ←SF nom;
11: e u n SF
Algo i hm 2 Simple G eedy ex ends G eedy (same inpu and
ou pu as G eedy)
1: unc ion Bes Agg ega ion(SF , nom)
2: mp←Closes ToZe oDis ance(SF )
3: a←Bina yAgg ega ion( nom, mp)
4: e u n { a, mp}
A e wa ds, algo i hm con inues un il all FOs a e agg ega ed
(Line 3). The wo a ia ions o G eedy examine di e en FOs
o p oduce an AFO, i.e., a(Line 4). I he e is an AFO
( a) wi h smalle dis ance han nom, he algo i hm con inues
agg ega ion wi h he agg ega ed one and emo es mp om
he ini ial se SF (Line 6). O he wise, i anno a es nom as
AFO and con inues by selec ing ano he nom om he non-
agg ega ed ones (Lines 8–10). The algo i hm s ops when all
he FOs a e anno a ed as AFOs (Line 3) and e u ns se SF
wi h he AFOs (Line 11).
Simple G eedy (SG). Apa om nom, SG also selec s
a single FO mp o examine whe he i will agg ega e hem
o no (Algo i hm 2, Line 2). In pa icula , i selec s he FO
( mp) among he se ha has he closes o ze o dis ance o
inc ease he chances o educing he dis ance o nom. Then, in
each s ep, i examines all he po en ial agg ega ions be ween
he wo FOs, i.e, nom and mp o iden i y he AFO ha
educes he dis ance o nom (Algo i hm 2, Line 3).
Exhaus i e G eedy (EG). EG explo es a la ge solu ion
space han SG. In pa icula , du ing each s ep, i examines
all he po en ial bina y agg ega ions be ween nom and all
he FOs in se SF (Algo i hm 3, Line 3) compa ed o SG
Algo i hm 3 Exhaus i e G eedy ex ends G eedy
1: unc ion Bes Agg ega ion(SF , nom)
2: a← nom; mp ←null;
3: o each ∈SF do
4: y←Bina yAgg ega ion( nom, )
5: i Dg,c( y)< Dg,c( a) hen
6: a← y; mp ← ;
7: e u n { a, mp}
Algo i hm 4 Bes bina y agg ega ion unc ion
Inpu : nom, mp - FOs
Ou pu : a- an AFO
1: unc ion Bina yAgg ega ion( nom, mp)
2: a← nom
3: o each alignmen al o { nom,, mp}do
4: x←AGG-2- o-1( nom, mp, al)
5: i Dg,c( x)<Dg,c( a) hen
6: a← x
7: e u n a
ha examines only he bina y agg ega ions among nom and
one FO om SF. EG hen s o es he AFO wi h he smalles
dis ance (Line 6). When he compa isons inish, i e u ns he
AFO wi h he minimum dis ance ( a) and he FO ( mp) ha
pa icipa ed in he p oduc ion o a(Line 7).
Cons ain alloca ion ea u e. Since agg ega ion should
lead o a alid schedule, i is desi able o examine, a e each
s ep, whe he he node cons ain is espec ed o no . Howe e ,
his would equi e o schedule du ing each s ep he cu en
FOs/AFOs, i.e., sol e he UC p oblem. Due o he ac ha he
UC p oblem is an NP-comple e p oblem [12], ou agg ega ion
algo i hms ins ead ac p e en i ely in e ms o cons ain
handling. In pa icula , i is possible o bo h algo i hms o
conside a cons ain alue lowe han he o iginal one. Fo
ins ance, we ypically alloca e he cons ain o 50% o i s
o iginal alue. As a esul , he alloca ion ea u e obs uc s
agg ega ion o iola e he cons ain . Consequen ly, in cases
whe e mo e han one AFOs ha e slice amoun s close o he
cons ain , i inc eases he chance o scheduling o o m a
node alue ha espec s he cons ain .
V. EXPERIMENTAL EVALUATION
A. Expe imen al se up
We expe imen ally e alua e he p oposed echniques in
complex conges ion scena ios. Ou expe imen s a e based
on powe cha ac e is ics om eal loads (e.g., [13], [14])
ha show simila use beha io and a e complemen ed wi h
po en ial lexibili y, e.g., [15]. One amoun uni co esponds
o 0.5kW. The g id powe capaci y cons ain used in he
expe imen s ep esen s medium ol age g ids, e.g., [16]. We
use a mixed po olio o FOs ha ep esen s a a ie y o
de ices and cha ac e is ics ega ding lexibili y and powe
demand/supply. In pa icula , we gene a e 6 da ase s o FOs
wi h di e en sizes o be able o examine he scalabili y o he
echniques in e ms o inpu . The sizes o he da ase s ollow
an a i hme ic p og ession wi h bo h ini ial e m and common
di e ence equal o 500 FOs. Thus, he las da ase has 3000
FOs. In o de o c ea e imbalances and conges ion si ua ions,
he numbe o he nega i e FOs is 10% o e e y da ase .
In pa icula , 40% o he posi i e FOs ep esen elec ical
ehicles (EVs), 30% ep esen hea pumps (HPs), and 30%
clo hes washe s (CWs). The nega i e FOs ep esen wind
u bines (WT) and pho o ol aics (PV) ha a e less lexible

500 1500 3000
Flex-o e s inpu
-4000
-2000
0
2000
4000
6000
8000
Peaks (amoun )
a ge cons ain In. SA SAG SG EG
500 1000 1500 2000 2500 3000
Flex-o e s inpu
0
500
1000
1500
2000
Agg ega ed lex-o e s (ou pu )
SA
SAG
SGR
EGR
In. SAG SG EG In. SAG SG EG
0
4
8
12
In. SAG SG EG
0
4
8
12
Time lexibili y
3K FOs
500 FOs 1500 FOs
500 1000 1500 2000 2500 3000
Flex-o e s inpu
0
20
40
60
80
P ocessing ime (seconds)
SA
SAG
SG
EG
(a) Peaks (b) #agg ega ed FOs (c) Time lexibili y box-plo s (d) P ocessing ime
Fig. 4: 500 −3K FOs, a ge =3.5K, cons ain =3K, cons ain agg ega ion alloca ion = 1.5K, Dg,c( )=1·Dg+ 10000 ·Dc
De ice EST #slices Min amoun s a
EV (day) 6 5 4 U∗{5,7}U{0,2}
EV (nigh ) N∗(18,1),[17,20] N(10,1),[8,12] U{3,4}U{5,7}U{0,2}
CW (day) N(16,1),[15,17] U{1,3}U{2,4}U{3,4},U{1,2}0
CW (nigh ) N(20,1),[19,21] N(8,1),[5,10] U{2,4}U{3,4},U{1,2}0
HP (day) N(13,1),[12,14] N(3,1),[1,5] U{4,7}U{5,8}U{0,2}
HP (nigh ) 17 3 U{3,6}U{5,8}U{0,2}
WT, PV (day) N(14,1),[13,15] U{3,4}U{4,10}U{8,10}U{0,2}
WT, PV (nigh ) N(23,1),[22,24] U{1,4}U{5,8}U{8,10}U{0,2}
TABLE I: Flex-o e s cha ac e is ics, U∗: uni o m dis ibu ion, N∗: Gaussian dis ibu ion
0 10 20 30
Time ho izon
-4000
-2000
0
2000
4000
Node alue (amoun )
a ge
cons ain
In.
SAG
EG
Viola ions
Fig. 5: 3K FOs inpu
wi h longe p o iles. We alloca e FOs du ing day ime and
nigh ime o all he de ices (50%-50%). De ails abou he
cha ac e is ics o he da ase s a e shown in Table I.
Mo eo e , o compa ison easons we use wo baseline
agg ega ion echniques. We compa e ou echniques wi h S a
Alignmen (SA) agg ega ion [10] (see Sec ion III-A whe e all
he FOs a e agg ega ed in o one FO). We also use a S a
Alignmen wi h G ouping (SAG) agg ega ion echnique whe e
a g ouping phase is used in ad ance [10]. Consequen ly, FOs
wi h he same ea lies s a ime and he same ime lexibili y
a e g ouped oge he and SA is applied on each g oup. As a
esul , o each g oup o FOs, a single AFO is p oduced.
In o de o examine whe he an agg ega ion esul allows
he cons ain o be espec ed o no , we implemen ed a
s ochas ic scheduling echnique based on he E olu iona y
Algo i hm (EA) p oposed in [17]. EA is applied on a se o
FOs (agg ega ed o no ) and o ms he node alue wi h he
possible minimum dis ance o a ge and cons ain unc ion.
We see in Figu e 5 how he node alue is o med when EA
is applied on he esul s o each agg ega ion echnique along
wi h he cons ain and he a ge unc ion alues.
The expe imen s we e conduc ed on a 2.9 GHz In el co e
i7 p ocesso wi h wo co es, physical memo y o 8 GB, and
MacOS. The echniques a e implemen ed in Ja a 1.8.
B. Use case
We examine ou echniques in a case whe e a ge is g ea e
han he cons ain so ha a bo leneck appea s. Ta ge is 3500
and cons ain is 3000 (e.g., 6.6kV - 11kV subs a ion [16]). We
also use he cons ain alloca ion ea u e. Thus, he cons ain
alue used by he agg ega ion echniques is 1500. We se he
a ge coe icien o 1and we use a e y high alue o he
cons ain coe icien (10000) when he dis ance is compu ed,
in o de o p io i ize he cons ain espec .
In Figu e 4a, we see how he highes and he lowes node
alues (amoun peaks) a e o med when EA is applied on he
ini ial (“In.” label) non-agg ega ed se and on he agg ega ion
esul o each echnique. Fo a be e illus a ion we show he
cases whe e he inpu is 500,1500 and 3000 FOs. We see
in Figu e 4a ha when he inpu size is 500, he peaks o med
by EA (scheduling) a e qui e a away om he cons ain and
as he inpu size is inc eased, he peaks app oach and inally
exceed he cons ain . In he same igu e, we also obse e ha
when he inpu size is small (500), all he echniques lead
o scheduling ha espec s he cons ain . When he size is
inc eased o 1.5K FOs, SA iola es he cons ain , and in he
las case o 3K FOs only EG espec s he cons ain .
Rega ding he numbe o he AFOs, we see ha SA p o-
duces only one AFO in all he inpu cases (Figu e 4b) and
i s ime lexibili y is always 1, i.e., he minimum among all
he FOs. We also no ice ha SAG, due o he g ouping ha
applies, p oduces a low numbe o AFOs and also achie es
a simila o he ini ial ime lexibili y dis ibu ion among he
AFOs, see Figu e 4c. Howe e , he agg ega ion esul o SAG
iola es he cons ain when he inpu is inc eased o 2.5K and
3K (shown in Figu e 4a). Fu he mo e, in Figu e 5, we see how
he node alue is o med based on EA when he agg ega ion
inpu is 3K. In he same igu e, we no ice ha SAG no only
iola es he cons ain , bu he e is also iola ion in 5ou o
he 28 scheduling poin s (app oxima ely in he 18% o he
ime ho izon).
Rega ding SG, he numbe o AFOs scales linea ly wi h
he inpu size and achie es a ime lexibili y highe han EG.
Howe e , EG is he only algo i hm ha o ms a node alue
ha espec s he cons ain in all he inpu cases. I main ains
he numbe o AFOs low (93% inpu educ ion on a e age)
and uses ime lexibili y o lead o a schedule ha espec s he
cons ain . Tha is why i has he lowes a e age ime lexibili y
and a dis ibu ion wi h low bounda ies, see Figu e 4c.
Rega ding he p ocessing ime, EG is he slowes algo i hm
due o he high numbe o compa isons i equi es. I shows a
simila o linea g ow h a e beha io , see Figu e 4d. SG is as
since i only compa es jus wo FOs in e e y s ep. Simila ly,
SA and SAG a e he as es algo i hms due o he e y low
numbe o agg ega ions hey pe o m.
Expe imen al summa y. We obse e ha SG is as and
espec s he cons ain while SA does no . When size inc eases
(>2K FOs), bo h SG and SAG iola e he cons ain . On he
o he hand, EG examines a la ge solu ion space and leads
o esul s ha espec he cons ain when he inpu size is
la ge, see Figu e 5, case o 3K FOs. I is indica i e ha
e en when we apply EA on he ini ial se o 3K FOs o
10 minu es, i s ill canno p o ide a esul ha espec s he
cons ain , see Figu e 5 label “In.”. On he con a y, EG uses
app oxima ely 67 seconds o i s execu ion and EA applied
a e wa ds p oduces he i s esul ha espec s he cons ain
in app oxima ely wo seconds. Tha means ha EG is able o
p o ide il e ed inpu s o scheduling so ha ini ially unsol able
cases can be sol ed. Howe e , when he inpu is la ge, EG
equi es high p ocessing imes. I equi es 24.08 minu es o
p ocess a da ase o 10K FOs.
VI. RELATED WORK
The ole o an agg ega o ha handles lexible loads has
been in es iga ed in many p e ious wo ks, e.g., [18], [19].
Such wo ks use highly complex models and ocus on con-
olling and scheduling me hods. Thei main cha ac e is ic is
ha he agg ega o ope a es as an agg ega ed load con olle
ha ies o ollow a powe e e ence and e en ually ackles
he scheduling p oblem o o e DR and ancilla y se ices,
e.g., [20]. On he con a y, in ou wo k we use a low com-
plexi y gene ic model o ep esen ene gy lexibili ies, namely
lex-o e s (FOs). Mo eo e , he main goal o ou echniques
is o p oduce lexible and non-scheduled AFOs ha can be
aded as commodi ies in eme ging ene gy lexibili y ma ke s.
Thus, ou p oposed echniques, SG and EG, p oduce AFOs
ha can lead o no mal g id ope a ion and use a gene ic a ge
unc ion ha can cap u e o e all business case scena ios.
Fu he mo e, he e is an ex ensi e li e a u e ackling he
uni commi men (UC) p oblem (scheduling), e.g., [21], [22].
In [17] he agg ega ion o FOs be o e scheduling showed
an imp o emen o scheduling esul s compa ed o applying
scheduling indi idually. Ou wo k can be also applied in
ad ance o scheduling p ocess and no only educes he com-
plexi y o he UC p oblem, bu in addi ion, pa ially handles
scheduling goals as i “ il e s” in alid esul s and imp o es
hei quali y.
VII. CONCLUSION AND FUTURE WORK
This pape in oduces cons ain -based agg ega ion o e a
gene ic da a model ha cap u es lexibili ies in ime and
amoun dimensions. I p oposes wo echniques ha ake in o
accoun he powe capaci y cons ain limi a ions imposed
by he g id. Mo eo e , he pape e alua es he p oposed
echniques in complex conges ion scena io. The expe imen al
e alua ion shows ha he p oposed echniques can e icien ly
agg ega e FOs and a he same ime enable scheduling o
espec he g id cons ain s, unlike exis ing echniques.
In ou u u e wo k, we will ocus on enhancing ou ech-
niques by au oma ing he se ing o agg ega ion pa ame e s
h ough sampling echniques. Mo eo e , we will ex end ou
p oposed algo i hms o in es iga e he inancial pe spec i e o
cons ain -based agg ega ion on he u u e ene gy ma ke .
ACKNOWLEDGMENT
This wo k was suppo ed in pa by he To alFlex p ojec
sponso ed by he Fo skEL p og am o Ene gine .dk.
REFERENCES
[1] M. Boehm, L. Dannecke , A. Doms, E. Do gan, B. Filipiˇ
c, U. Fische ,
W. Lehne , T. B. Pede sen, Y. Pi a ch, L. ˇ
Sikˇ
snys, and T. Tuˇ
sa , “Da a
managemen in he mi abel sma g id sys em,” in EnDM, 2012.
[2] M. Albano, L. L. Fe ei a, L. M. Pinho, and A. R. Alkhawaja, “Message-
o ien ed middlewa e o sma g ids,” Compu e S anda ds & In e aces,
ol. 38, 2015.
[3] I. Diaz De Ce io Mendaza, I. Szczesny, J. Pillai, and B. Bak-Jensen,
“Demand esponse con ol in low ol age g ids o echnical and
comme cial agg ega ion se ices,” Sma G id, 2015.
[4] L. Fe ei a, L. Siksnys, P. Pede sen, P. S luka, C. Ch ysoulas,
T. le Guilly, M. Albano, A. Skou, C. Teixei a, and T. Pede sen,
“A owhead complian i ual ma ke o ene gy,” in ETFA, 2014, pp.
1–8.
[5] B. Neupane, T. B. Pede sen, and B. Thiesson, “E alua ing he alue o
lexibili y in ene gy egula ion ma ke s,” in e-Ene gy. ACM, 2015.
[6] B. Biegel, M. Wes enholz, L. H. Hansen, J. S ous up, P. Ande sen,
and S. Ha bo, “In eg a ion o lexible consume s in he ancilla y se ice
ma ke s,” Ene gy, ol. 67, 2014.
[7] N. Padhy, “Uni commi men -a bibliog aphical su ey,” Powe Sys ems,
ol. 19, 2004.
[8] R. Mi a, V. A ya, B. Sulli an, R. Muelle , H. S o ey, and G. Labu ,
“Using analy ics o minimize e o s in he connec i i y model o a powe
dis ibu ion ne wo k,” in e-Ene gy. ACM, 2015.
[9] D.-J. Won and S.-I. Moon, “Op imal numbe and loca ions o powe
quali y moni o s conside ing sys em opology,” Powe Deli e y, ol. 23,
2008.
[10] L. Siksnys, E. Valsoma zis, K. Hose, and T. Pede sen, “Agg ega ing and
disagg ega ing lexibili y objec s,” TKDE, ol. 27, 2015.
[11] M. Aigne , “A cha ac e iza ion o he bell numbe s,” Disc e e Ma he-
ma ics, 1999.
[12] X. Guan, Q. Zhai, and A. Papalexopoulos, “Op imiza ion based me hods
o uni commi men : Lag angian elaxa ion e sus gene al mixed in ege
p og amming,” in Powe Enginee ing Socie y Gene al Mee ing, 2003.
[13] J. Acos a, K. Combe, S. Djokic, and I. He nando-Gil, “Pe o mance
assessmen o mic o and small-scale wind u bines in u ban a eas,”
Sys ems Jou nal, ol. 6, 2012.
[14] M. an de Kam and W. an Sa k, “Sma cha ging o elec ic ehicles
wi h pho o ol aic powe and ehicle- o-g id echnology in a mic og id;
a case s udy,” Applied Ene gy, ol. 152, 2015.
[15] I. Sajjad, G. Chicco, and R. Napoli, “Demand lexibili y ime in e als
o agg ega e esiden ial load pa e ns,” in Powe Tech, 2015.
[16] W. P. Dis ibu ion, “Gene a ion capaci y egis e ,” h ps://www.
wes e npowe .co.uk/Connec ions/Gene a ion/Gene a ion-Capaci y-Map/
Gene a ion-capaci y- egis e .aspx, accessed: 2016-05-05.
[17] T. Tuˇ
sa , L. ˇ
Sikˇ
snys, T. B. Pede sen, E. Do gan, and B. Filipiˇ
c, “Using
agg ega ion o imp o e he scheduling o lexible ene gy o e s,” in
BIOMA, 2012.
[18] X. Geng and P. Kha goneka , “Elec ic ehicles as lexible loads:
Algo i hms o op imize agg ega e beha io ,” in Sma G idComm, 2012.
[19] H. Hao, B. Sanandaji, K. Poolla, and T. Vincen , “Agg ega e lexibili y
o he mos a ically con olled loads,” Powe Sys ems, ol. 30, 2015.
[20] H. Cai, A. Hu e , E. Oli e o, P. Rodui , and P. Fe ez, “Load shi ing
o e ia y con ol powe p o ision,” in POWERENG, 2015.
[21] T. Logen hi an, D. S ini asan, and A. M. Khambadkone, “Mul i-agen
sys em o ene gy esou ce scheduling o in eg a ed mic og ids in a
dis ibu ed sys em,” Elec ic Powe Sys ems Resea ch, ol. 81, 2011.
[22] T. Logen hi an, D. S ini asan, A. Khambadkone, and H. N. Aung,
“Mul iagen sys em o eal- ime ope a ion o a mic og id in eal- ime
digi al simula o ,” Sma G id, ol. 3, 2012.