Page - 206 - in Emerging Technologies for Electric and Hybrid Vehicles

Energies 2016,9, 594 integer restrictions for thevaluesof x andhasanasymptotic timecomplexityofO(M). However, thisalgorithmhasa largeconstantsince it reliesonmedianfinding[20]. Therefore, thealgorithmis in practiceonly fast forarelatively largeM. 3.2.OnlineOptimization When the power consumption in future intervals is knownbeforehand, the aforementioned algorithmscanbeused tocalculate theoptimal chargingpower foreach future interval. However, inmostcases, these futurevaluesarenotknownandmustbepredicted.Obviously,predictionerrors mayleadtonon-optimaldecisions,andthe impactof sucherrorsatahouse level is rarelyconsidered in the literature. Furthermore, it is ingeneraldifficult topredict thepowerconsumptionforall future charging intervalsat thebeginningof theplanning. Therefore,wetakeadifferentapproachthatdoes notneedthisdetailed information. Central inourapproach is theobservation that for theaforementionedalgorithms,asinglevalue Zuniquelycharacterizes theoptimalsolution. Forall feasible instancesofProblem1, thereexistsaZ suchthat theoptimalsolutionx1, . . . ,xM canbeconstructedbysetting xm :=max(0,min(Z−pm+qm, x¯)) . (5) Note that this calculation, for time intervalm, canbedelayeduntil thebeginningof the time interval, and, thuswecandelay thepredictionof pm to this time. The sketched approach is in principle interval based; however, it can easily be adapted to aneventbasedapproachthat recalculates thechargingpowerwhenever thepowerconsumptionof thehouseholdchangesandall results in this sectionarealsovalid for theeventbasedapproach. Asaconsequenceof theabove, themainchallengeofourapproach is thatwedonotknowZ and, therefore, thisvaluemustbepredicted.However, comparedtoapproaches thatpredictspower foreach interval, thisapproachhas twoadvantages,namely, thatonlyasinglevalueZ ispredicted (insteadof thecompletevector p), andthat theresultingerrorduetoanincorrectpredictioncanbe boundedaswediscuss in thenextsection. 3.3. Predictions Aswe, ingeneral,donotknowZ,weuseapredictionofZ,whichwedenoteby Zˆ.When Zˆ<Z, Equation(5)chooseschargingpowers thatarenotsufficient tocharge thecarupto thedesired level. This canberesolvedbychargingat themaximumpower x¯ (or someotherpre-set chargingpower) startingfromthe intervalwhere thisbecomes theminimumchargingpower that isneededtocharge theEVwithin the remaining intervals. Note that thismayresult in largepeaksandhighcosts (i.e., highobjectivevalues)at theendof thechargingperiod,aswediscuss lateron.Onthecontrary, in the situationwhere Zˆ>Z, thealgorithmcharges faster thanrequiredresulting insometimeintervalsat theendof theplanningperiodwith loworzerochargingpowervalues. Algorithm1takes these twocases intoaccountandguarantees that theSoCtarget is reachedin bothsituations. Note thatAlgorithm1produces thesame(optimal) solutionasEquation (5)when Zˆ=Z. Before thefirst invocationof thealgorithm, thevariableT,whichexpresses theamountof energyalreadycharged, is initializedtozero. Then, iterativelybeforeeach intervalm, thisalgorithmis usedtocalculate thechargingpowerxm for this interval.Hence,at thebeginningof them-th interval, T=∑mi=1xm expresses theamountalreadychargedupto this intervalof the totalC tobecharged. Figure2 illustratesan instancewith Zˆ=1.1Zand q= 0,whichshowsthat thepredictionerror is spreadoutevenlyoverall intervalswherechargingtakesplace,but thechargingstopsbefore the deadline. Theratiobetweentheobjectivevalueof theoptimalsolutionandof theonlinealgorithm using Zˆ is1.008 in thisexample.Onthewebsite [21], an interactivedemonstrationofAlgorithm1can befound. 206