PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Coordinated Charging Decision Algorithm for Electric Vehicles without Future Information

Wanrong Tang, Suzhi Bi, Ying Jun, Zhang

arXiv:1310.3580v4cs.DS

TL;DR

Offline PEV charging methods assume future profiles are known, although arrival times, demands, and their distributions may be unknown beforehand. ORCHARD mimics the offline optimal charging decision to minimize total cost using online information. ORCHARD is 2.39-competitive with q = 1.46; simulations show an average performance gap as small as 14%, reducible to 6% when the speeding factor is chosen for the charging-demand pattern.

Abstract

from arXiv · show

The large-scale integration of plug-in electric vehicles (PEVs) to the power grid spurs the need for efficient charging coordination mechanisms. It can be shown that the optimal charging schedule smooths out the energy consumption over time so as to minimize the total energy cost. In practice, however, it is hard to smooth out the energy consumption perfectly, because the future PEV charging demand is unknown at the moment when the charging rate of an existing PEV needs to be determined. In this paper, we propose an Online cooRdinated CHARging Decision (ORCHARD) algorithm, which minimizes the energy cost without knowing the future information. Through rigorous proof, we show that ORCHARD is strictly feasible in the sense that it guarantees to fulfill all charging demands before due time. Meanwhile, it achieves the best known competitive ratio of 2.39. To further reduce the computational complexity of the algorithm, we propose a novel reduced-complexity algorithm to replace the standard convex optimization techniques used in ORCHARD. Through extensive simulations, we show that the average performance gap between ORCHARD and the offline optimal solution, which utilizes the complete future information, is as small as 14%. By setting a proper speeding factor, the average performance gap can be further reduced to less than 6%.

I. INTRODUCTION

PEV charging coordination must cope with charging profiles revealed only after arrival, unlike offline schedules that assume future information. ORCHARD addresses this setting with a feasible online algorithm, while the paper also formulates the charging model and situates it against speed-scaling work.

A. Background and Contributions

  • Offline charging methods assume future PEV profiles are known in advance, an assumption the paper says does not hold in practice.Uncontrolled charging also raises concerns about voltage instability, transmission congestion, and generation and transmission costs.Source: A. Background and Contributions · p. 1

A PEV’s charging profile is revealed only after it arrives at the charging station or connects to the charging pole.

  • Arrival times, demands, and their distributions may be unknown beforehand, and prior online work lacked performance analysis or demand-completion guarantees.The paper notes that – generally lacked performance analysis, while did not guarantee demands would be met before departure.Source: A PEV’s charging profile is revealed… · p. 1
  • ORCHARD mimics the offline optimum, guarantees feasible demands are met by their due times, and achieves a 2.39 competitive ratio.The paper also reports an average performance gap as small as 14%, reducible to less than 6% with a proper speeding factor.Source: A PEV’s charging profile is revealed… · pp. 1–2

B. Related Work

  • PEV charging differs from speed scaling through individual maximum charging-rate limits and a general polynomial cost function.The paper describes speed scaling as a special case of PEV charging in both objective and constraints.Source: B. Related Work · p. 2

A. Problem Formulation

  • The model schedules randomly arriving PEVs with random charging demands that must be fulfilled before departure, subject to feasible-demand and charging-rate constraints.Each PEV’s charging rate is bounded by its maximum rate; feasibility also accounts for its available parking time and battery capacity.Source: A. Problem Formulation · p. 2

B. Model Transformation

The model transformation replaces continuous-time charging decisions with a finite set of interval-based variables. Arrival and departure events partition time, and an optimal schedule can use constant charging rates within each interval.

B. Model Transformation

  • Arrival and departure events partition time into intervals during which the set of parked PEVs does not change.The total charging rate is constant within each interval in an optimal schedule.Source: B. Model Transformation · p. 3
  • An optimal solution exists in which each PEV’s charging rate remains constant during every interval it occupies.This interval-wise constancy allows the continuous-time problem to be represented with finitely many variables.Source: B. Model Transformation · p. 3
  • The finite formulation assigns interval rates subject to each PEV’s demand and maximum-rate constraints.The constraints require sufficient interval energy to meet demand and bound each rate between zero and the PEV’s maximum rate.Source: B. Model Transformation · p. 3

III. ONLINE ALGORITHM

The paper evaluates online charging against the offline optimum and introduces OA as an intuitive, suboptimal scheme. ORCHARD is reported as strictly feasible and best-known in competitive ratio, while OA repeatedly optimizes for currently known PEVs.

III. ONLINE ALGORITHM

A. Online PEV Charging and Performance Metric

  • 2.39 is ORCHARD’s competitive ratio, while its average simulated performance ratio is less than 1.06.The competitive ratio is a worst-case measure, and average performance ratios can be much smaller.Source: A. Online PEV Charging and Performance… · p. 3

B. Online Optimal Available (OA) Algorithm

  • At each PEV arrival, OA optimizes a schedule assuming no further arrivals, then follows it until a new PEV arrives and triggers re-optimization.The optimization uses the residual demands and departure times of PEVs already present; the resulting time intervals have constant charging rates.Source: B. Online Optimal Available (OA)… · p. 4

C. The ORCHARD Algorithm

ORCHARD recomputes an Optimal Available (OA) schedule when a PEV arrives or finishes charging, then speeds up that schedule while respecting each vehicle’s maximum rate. Its rates remain feasible because they are no smaller than OA’s and do not exceed the vehicles’ limits.

C. The ORCHARD Algorithm

  • At each arrival or charging completion, ORCHARD updates current PEV information and solves the OA problem again.With the speed-up factor, a PEV may finish before its OA-calculated departure time, so completion also triggers a re-solve.Source: C. The ORCHARD Algorithm · p. 4
  • The algorithm sets its total rate to the smaller of q times OA’s total rate and the sum of current PEVs’ maximum rates.This caps the aggregate at the charging capacity of the PEVs currently present.Source: C. The ORCHARD Algorithm · pp. 4–5
  • ORCHARD distributes the selected total rate across current PEVs while keeping each rate at least its OA rate and at most its maximum.The per-PEV rates sum to the selected aggregate rate.Source: C. The ORCHARD Algorithm · p. 5
  • ORCHARD remains feasible because each charging rate is no smaller than OA’s and does not exceed the PEV’s maximum rate.The aggregate rate equals the total selected in Step 3.Source: C. The ORCHARD Algorithm · p. 5

D. Derivation of Competitive Ratio

The competitive-ratio proof uses an amortized local analysis with a time-dependent potential function. It establishes a 2.39 competitive ratio when the speed-up factor q is 1.46.

D. Derivation of Competitive Ratio

  • The proof uses amortized local competitiveness and a time-dependent potential function Φ(t).The potential is zero before the first PEV arrives and after the last deadline.Source: D. Derivation of Competitive Ratio · p. 5
  • The analysis compares ORCHARD’s and the offline algorithm’s remaining demand over deadline intervals, then constructs time points maximizing average interval demand.The sequence of time points supports the proof’s potential-function analysis.Source: D. Derivation of Competitive Ratio · p. 5
  • 2.39 is ORCHARD’s competitive ratio when q = 1.46.The proof selects q = 1.46 and β2 = 2.7 to obtain the lowest competitive ratio.Source: D. Derivation of Competitive Ratio · pp. 7–8
  • The proof handles four cases for the initial intensity gap and combines interval bounds to establish its key inequality.When the online remaining demand is below the offline demand, the proof obtains g0 = 0; it then considers the other cases.Source: D. Derivation of Competitive Ratio · pp. 6–7

IV. A LOW COMPLEXITY SOLUTION ALGORITHM TO PROBLEM (5) AND (9)

The paper proposes a low-complexity routine for solving Problems (5) and (9), replacing generic convex optimization methods.

IV. A LOW COMPLEXITY SOLUTION ALGORITHM TO PROBLEM (5) AND (9)

  • A low-complexity routine exploits the shared convex-objective-over-a-polyhedron structure of Problems (5) and (9), and has much lower computational complexity than generic convex optimization algorithms.Problem (9) must be solved whenever a PEV arrives or finishes charging.Source: §IV · p. 8

A. KKT Optimality Conditions

The KKT conditions characterize the optimal total charging rates across intervals. They imply that the convex cost encourages balancing aggregate rates, subject to individual PEV charging limits.

A. KKT Optimality Conditions

  • When a PEV’s rate is strictly between zero and its maximum in an interval, the optimal total rate is the same across intervals spanned by that PEV.This is one of the stated necessary and sufficient conditions for the optimal total charging rate.Source: A. KKT Optimality Conditions · p. 8
  • If a PEV is uncharged in an interval, that interval’s optimal total rate is no smaller than in an interval where it receives a positive rate.Conversely, when a PEV charges at its maximum rate, the interval’s optimal total rate is no larger than in an interval where its rate is below maximum.Source: A. KKT Optimality Conditions · p. 8
  • Because the objective is convex, charging can shift from higher-rate intervals to lower-rate ones when the PEV is available, until a rate limit is reached.The stated balancing interpretation underlies the interval conditions.Source: A. KKT Optimality Conditions · p. 8

B. Algorithm Description

ORCHARD balances charging load by shifting demand from high-intensity intervals to neighboring intervals that eligible PEVs can use. It repeatedly selects the interval set with the highest total charging rate, assigns rates, and updates the remaining schedule.

B. Algorithm Description

  • The algorithm ranks intervals by intensity within each time window and considers candidate sets formed from the highest-intensity intervals.A time window runs from a PEV arrival to a PEV departure; each window contributes candidate interval sets for load transfer.Source: B. Algorithm Description · p. 9
  • For each candidate set, it calculates each PEV’s residual demand after charging at its upper bound outside that set, then balances residual demand across the set.Previously scheduled rates are included in the total rate calculation; they are initially zero.Source: B. Algorithm Description · p. 9
  • It selects the candidate set with the highest total charging rate and assigns that rate across its intervals.PEVs with nonnegative residual demand are scheduled in the selected set; PEVs already scheduled are excluded from later iterations.Source: B. Algorithm Description · p. 9
  • Rates fixed for a scheduled PEV in intervals outside the selected set remain part of those intervals’ load in subsequent iterations.For PEVs not scheduled in the selected set, rates in overlapping intervals are set to zero.Source: B. Algorithm Description · p. 9
  • After excluding the scheduled PEVs and selected intervals, the algorithm merges remaining intervals into a new duration and repeats until all PEV rates are scheduled.The allocation seeks to move demand from heavily loaded intervals to lower-intensity neighboring intervals available to a PEV.Source: B. Algorithm Description · p. 9

C. Optimality and Complexity

The iterative algorithm produces a globally optimal charging schedule, supported by a monotonicity lemma and a KKT-condition argument. Its operation complexity is O(N^5), below the O(N^7) bound stated for a generic interior-point method in this problem.

C. Optimality and Complexity

  • The proposed algorithm always outputs a globally optimal schedule.The proof establishes that the highest total charging rate found in iteration m is no smaller than that in iteration m + 1, then shows the algorithm satisfies the KKT conditions.Source: C. Optimality and Complexity · p. 10
  • O(N^5) is the algorithm’s upper-bound operation complexity, compared with O(N^7) for the generic interior-point method in this problem.The analysis counts at most 2N−1 outer iterations and at most N(N + 1)/2 time windows per iteration.Source: C. Optimality and Complexity · p. 10

A. Performance Ratio Evaluation

Across the simulated traffic scenarios, ORCHARD performs best among the four online algorithms and stays close to the offline optimum. Its average extra cost is below 14%, with a 10% performance gain over OA in heavy traffic.

A. Performance Ratio Evaluation

  • Less than 14% average extra cost versus the offline optimum makes ORCHARD the best of the four online algorithms across all scenarios.In heavy traffic, ORCHARD has a 10% performance gain compared with OA.Source: A. Performance Ratio Evaluation · p. 11, Table II · p. 11
  • ORCHARD’s average charging-rate curve follows closely with the offline optimal curve, unlike the more aggressive or conservative EG and AVG curves.The figure compares total charging rates for five algorithms across three scenarios.Source: A. Performance Ratio Evaluation · p. 11, Figure 4 · p. 11
  • The simulations use three traffic scenarios, each with 10^5 cases, and compare ORCHARD with the offline optimum and other online algorithms.The scenarios represent light, moderate, and heavy traffic; the default ORCHARD speeding factor is q = 1.46.Source: A. Performance Ratio Evaluation · pp. 10–11

B. Setting a Proper q

The average-optimal speeding factor varies with traffic: higher peak-to-flat load scenarios favor larger q. The conclusions also report that a reduced-complexity replacement for standard convex optimization can bring the average gap to the offline optimum below 6% with a proper speeding factor.

B. Setting a Proper q

  • Ψ∗ achieves a lowest average ratio of 1.050, about 8% lower than at q = 1.46; optimal q is generally larger under heavy, unpredictable traffic, as in scenario 3.Empirically, q is chosen as 1.8, 2.1, and 2.3 when peak load is about 2, 6, and 10 times flat load, respectively.Source: B. Setting a Proper q · p. 11

VI. CONCLUSIONS

  • A proper speeding factor reduces the average gap between ORCHARD and the offline optimum from as much as 14% to less than 6%.The paper also proposes a reduced-complexity algorithm to replace ORCHARD’s standard convex optimization techniques.Source: §VI · p. 12
Loading 1310.3580v4…