Seite - 207 - in Emerging Technologies for Electric and Hybrid Vehicles

Energies 2016,9, 594 Algorithm1OnlineEVplanningfor timeintervalm. xm=max ( 0,min ( Zˆ−pm+qm, x¯ )) xm=min(xm,C−T) {neededforZ< Zˆ} ifT+xm+(M−m)x¯<C then {neededforZ> Zˆ} xm :=min{C−T, x¯} endif T=T+xm 18:00 07:00 200 400 600 Zˆ Time NoEV( p) House+EV( p+ x) House+EV(prediction) Figure2.OptimalEVplanningandEVplanningusingtheprediction Zˆ. In the following,weconsider thecase that Zˆ≥Z. For thiscase,wederiveaboundontheratio betweentheobjectivevalueof theoptimalsolutionandtheobjectivevalueof thesolutionthatuses theprediction Zˆ,whichonlydependsonZand Zˆ. Toeasethediscussion,weuseC(Z)andC(Zˆ) todenotetheobjectivevalueof theoptimalsolution andtheobjectivevalueof thesolutionthatuses theprediction Zˆ, respectively. Toderiveboundsonthe ratioC(Zˆ)/C(Z),weneedthe following lemma. Lemma1. Let x be an optimal solution to an instancewhere xm < x¯ (for allm), and let ZΣ=∑Mm=1zm. Then,wehave: C(Z)≥ √ ZZΣ. Proof. Assumethatintheoptimalsolutionwehaveazm<Z forsomem. Thisimpliesthatpm−qm<Z andthealgorithmtried tofill this intervaluptoZ, butdidnotsucceed. Theonlyreasonfor this is that themaximumamountofchargingwasnotsufficient toreachZ. Asaconsequence, thealgorithmwill charge x¯ in this interval,which isacontradictiontoxm< x¯ forallm. Hence,wehave C(Z)= √√√√ M∑ m=1 z2m ≥ √√√√ M∑ m=1 zmZ = √ ZZΣ This lemma isused toderiveaboundon the ratiobetween theobjectivevalueof theoptimal solution,andtheobjectivevalueof thesolutionbasedontheprediction Zˆ. 207