PaperlayerView exact revision on arXiv

Source-linked AI summary

Electric Vehicle Charge Scheduling Mechanism to Maximize Cost Efficiency and User Convenience

Hwei-Ming Chung, Wen-Tai Li, Chau Yuen, Chao-Kai Wen, Noel Crespi

arXiv:1803.04750v2math.OC

TL;DR

EV charge scheduling must balance charging cost with vehicle-owner convenience, while future arrivals make globally optimal scheduling impractical. The paper proposes online centralized and low-complexity distributed algorithms; simulations report shorter charging times than comparison methods and reduced data transmission for the distributed method.

  • Problem

    EV scheduling must balance charging cost and user convenience, while unknown future arrivals make the globally optimal schedule impractical.

    Source: §I · p. 2, §III · p. 3

  • Method

    The paper formulates a bi-objective scheduling problem and proposes an online centralized Pareto-optimal algorithm plus a low-complexity distributed algorithm.

    Source: §I · p. 2

  • Results

    30% lower average charging time is reported for the proposed methods than for the cost-minimization and user-convenience-maximization methods; distributed transmission data is 33.25% lower than centralized.

    Source: §I · p. 2, C. Evaluation in Terms of Charging Time · p. 7

  • Takeaways & Limitations

    The distributed algorithm has a reported performance degradation of only 2% versus the centralized algorithm while reducing transmission data and computation complexity.

    Source: §I · p. 2, §VI · p. 9

    The globally optimal scheduling scheme is impractical because information about EVs arriving in the future is unavailable.

    Source: §III · p. 3

Abstract

from arXiv · show

This paper investigates the fee scheduling problem of electric vehicles (EVs) at the micro-grid scale. This problem contains a set of charging stations controlled by a central aggregator. One of the main stakeholders is the operator of the charging stations, who is motivated to minimize the cost incurred by the charging stations, while the other major stakeholders are vehicle owners who are mostly interested in user convenience, as they want their EVs to be fully charged as soon as possible. A bi-objective optimization problem is formulated to jointly optimize two factors that correspond to these stakeholders. An online centralized scheduling algorithm is proposed and proven to provide a Pareto-optimal solution. Moreover, a novel low-complexity distributed algorithm is proposed to reduce both the transmission data rate and the computation complexity in the system. The algorithms are evaluated through simulation, and results reveal that the charging time in the proposed method is 30% less than that of the compared methods proposed in the literature. The data transmitted by the distributed algorithm is 33:25% lower than that of a centralized one. While the performance difference between the centralized and distributed algorithms is only 2%, the computation time shows a significant reduction.

I. INTRODUCTION

The paper frames EV charge scheduling as a trade-off between charging cost and user convenience, then proposes centralized and distributed algorithms for coordinating stations. Its micro-grid model places station sub-aggregators under a central aggregator and accounts for EV availability and deadlines.

I. INTRODUCTION

  • Prior work often treated cost minimization and user-convenience maximization separately, while this work focuses on online scheduling across multiple parking stations with rate limits and load constraints.The paper identifies reaching consensus between the two stakeholders as a challenge.Source: §I · p. 1
  • The paper formulates a micro-grid-scale bi-objective problem that balances charging cost with user convenience for two stakeholder groups.User convenience is based on EV charging state and total charging time.Source: §I · p. 2
  • An online centralized algorithm seeks a Pareto-optimal solution, reducing average charging time without affecting the main objective value.The paper motivates online scheduling because future station loads are unavailable, making globally optimal scheduling impractical.Source: §I · pp. 1–2
  • 33.25% lower transmission data rate is reported for the distributed algorithm than for the centralized algorithm in the case study.The distributed method is proposed to reduce transmission and computation complexity while retaining comparable performance.Source: §I · p. 2

A. System Model

  • A central aggregator controls M parking stations through station sub-aggregators, which relay EV information for scheduling over a time horizon.The model tracks EV availability by time slot and assumes each EV may finish before, but not after, its deadline.Source: A. System Model · p. 2, §I · p. 2

B. Charging Cost

The section defines charging cost for the parking-station owner and user convenience as complementary scheduling metrics. Convenience reflects the relationship between an EV’s minimum charging time and the time remaining before its deadline.

B. Charging Cost

  • The charging cost for the parking-station owner is evaluated using a cost function adopted from.The function g(zt) returns the electricity cost for total load zt in time slot t.Source: B. Charging Cost · p. 3

C. User Convenience

  • User convenience is defined as the inverse product of an EV’s minimum required charging time and its remaining time before the deadline.The minimum required time is the earliest feasible number of slots to finish charging; the remaining time is measured against the EV’s deadline.Source: C. User Convenience · p. 3
  • The study’s second performance metric maximizes the sum of users’ convenience values.The stated intuition gives higher charging priority to EVs needing less electricity and closer to their deadlines.Source: C. User Convenience · p. 3

D. Problem Formulation

The formulation jointly considers charging cost and user convenience, whose trade-off prevents simultaneous joint minimization. Because future arrivals are unknown, the paper develops an online approach that first minimizes cost, then maximizes convenience among cost-optimal schedules.

D. Problem Formulation

  • The bi-objective formulation treats charging cost J1 and user convenience J2 as the two objectives.The constraints limit total load and charging rates and enforce battery-capacity and final-charge requirements.Source: D. Problem Formulation · p. 3
  • Because future EV arrivals are unavailable and charging cost trades off against user convenience, the globally optimal schedule is impractical and joint minimization is impossible.The paper therefore develops an online algorithm to obtain a Pareto-optimal solution.Source: §III · p. 3

A. Problem Transformation

  • The first phase uses lexicographic ordering to minimize electricity cost while temporarily ignoring user convenience.It solves P1 to identify optimal load values z⋆_t.Source: A. Problem Transformation · p. 3
  • Once the optimal load values are fixed, multiple EV charging schedules can preserve the same charging cost.The charging times can be rescheduled without changing the cost associated with those fixed load values.Source: A. Problem Transformation · p. 4
  • The second phase maximizes user convenience among feasible schedules that remain optimal for P1.With z⋆_t fixed, feasible P2 solutions are P1-optimal.Source: A. Problem Transformation · p. 4
  • An optimal P2 solution is Pareto-optimal for the original bi-objective problem.The result follows because it is optimal for P1 while maximizing convenience among the feasible P1-optimal solutions.Source: A. Problem Transformation · p. 4

B. Scheduling Algorithm Description

The centralized scheduling algorithm forecasts future base load, minimizes charging cost, then allocates available charging power to prioritize user convenience. It updates battery state and is described as producing a Pareto-optimal solution.

B. Scheduling Algorithm Description

  • Seasonal ARIMA forecasts future base load for the algorithm’s cost-optimization phase.The paper selects it as a stable forecasting method and notes its performance when data are correlated.Source: B. Scheduling Algorithm Description · p. 4
  • The central aggregator solves P1 with an interior-point method to obtain the optimal charging load value z⋆_t.The algorithm’s stated input is EV information and its output is a feasible schedule for Problem P.Source: B. Scheduling Algorithm Description · p. 4
  • The algorithm uses the available charging power to charge EVs in decreasing order of user convenience, at maximum rates where possible.It selects as many EVs as possible while matching the selected charging load to the available power.Source: B. Scheduling Algorithm Description · p. 4
  • After charging decisions are made, the algorithm updates EV state-of-charge information.The procedure is identified as UCM and produces charging decisions for time slot t.Source: B. Scheduling Algorithm Description · p. 4
  • The proposed algorithm determines a Pareto-optimal solution, with an EV’s finish time set when its state of charge reaches the target.The paper states that the proof is provided in Appendix A.Source: B. Scheduling Algorithm Description · p. 4

IV. LOW-COMPLEXITY DISTRIBUTED ALGORITHM

The distributed algorithm addresses the centralized method’s growing computation complexity and high transmission burden. Its charging-cost procedure uses a flat load profile where constraints permit and redistributes load when charging-rate limits bind.

IV. LOW-COMPLEXITY DISTRIBUTED ALGORITHM

  • The centralized algorithm’s computation complexity grows exponentially with the number of EVs, and sending all information to the aggregator creates a heavy transmission burden.The distributed algorithm is proposed to reduce computation complexity and transmission data rate.Source: §IV · p. 4

A. Low-Complexity Charging-Cost Minimization Algorithm

  • When constraints are removed, the cost-minimization solution has a flat total-load profile across time slots.The total charging power must still meet the required demand.Source: A. Low-Complexity Charging-Cost… · pp. 4–5
  • When the charging-power constraint is active, the flat profile may fail because load cannot exceed the EVs’ combined maximum charging rates in a time slot.The excess is redistributed to earlier-deadline time slots, while the portion within the limit remains flat.Source: A. Low-Complexity Charging-Cost… · p. 5
  • The LCCM procedure has each sub-aggregator calculate a time window and total demand, then sends those values to the central aggregator.The central aggregator constructs a time window from the sub-aggregators’ windows because it does not know each EV’s exact charging limit.Source: A. Low-Complexity Charging-Cost… · p. 5

B. Low-Complexity Distributed Algorithm Description

DCSA divides scheduling into two phases: the central aggregator first determines available charging power, then sends it to the sub-aggregators.

B. Low-Complexity Distributed Algorithm Description

  • DCSA first solves P1 centrally, with the central aggregator applying LCCM to determine z*_t and broadcasting the resulting available power to all sub-aggregators.The sub-aggregators prepare parameters and send them to the central aggregator in this first phase.Source: B. Low-Complexity Distributed… · p. 5
  • Algorithm 3 is presented as the distributed charge scheduling algorithm, with a feasible schedule for Problem P as its output.Source: B. Low-Complexity Distributed… · p. 5

1 Forecast the base load and broadcast to all SAs

After the central aggregator broadcasts available power, sub-aggregators coordinate EV charging without further communication from it. DUCM iteratively identifies a convenience threshold, assigns charging power, and updates EV state of charge.

1 Forecast the base load and broadcast to all SAs

  • DUCM coordinates sub-aggregators without further central-aggregator communication, charging EVs above the minimum convenience threshold at maximum rate and assigning residual power to the corresponding EV.Source: §1 · pp. 5–6
  • The first sub-aggregator initializes the minimum convenience threshold by averaging bounds set to 1 and 0, then passes threshold and charging variables along the chain.The message includes total power for EVs above the threshold, the largest convenience below it, and that EV's number.Source: §1 · p. 5
  • The last sub-aggregator adjusts the bounds and sends them to the first; iterations continue until the minimum convenience level is obtained.Source: §1 · pp. 5–6
  • After each charging decision, EV state of charge is updated, and reaching the target state of charge marks the EV's finish time.Source: §1 · p. 6

V. SIMULATION RESULTS

The simulations evaluate the proposed algorithms under a six-station setup with randomly assigned Nissan Leaf EVs and randomized arrival, deadline, and initial-charge conditions. They also specify load-forecast comparisons and the error metric used.

V. SIMULATION RESULTS

  • The simulation uses six sub-aggregators and Nissan Leaf 2016 EVs with 30 kWh batteries and a 6.6 kW maximum charging rate.EV arrival times and deadlines are randomized between 18:00 and 07:00; initial state of charge is uniform on [0, 1], with target state of charge 1.Source: §V · p. 6
  • The load-forecast comparison is seasonal ARIMA [16] versus the average from 11/30 to 12/16 [4].Source: Figure 4 · p. 6
  • Forecasting error is measured by MAPE, and the peak constraint limits z_t for comparison with [9].Computation-speed simulations used an Intel i7-3770, a DUCM tolerance of 10^-4, and 100 Monte Carlo runs.Source: §V · p. 6
  • The proposed centralized and distributed algorithms are compared with the cost-minimization method and the user-convenience-maximization method [9].Source: §V · p. 6

A. Forecasting Accuracy

The evaluation reports forecasting accuracy and assesses charging cost, charging time, computation, and competing methods; results highlight shorter charging times and low-complexity distributed scheduling.

A. Forecasting Accuracy

  • Seasonal ARIMA forecasts France’s 12/17–12/18-noon load with 1.79% error, versus 4.52% for the previous-day average method, a reported 2.73% improvement.The comparison uses actual French load data from 11/30/2015 through 12/16/2015.Source: A. Forecasting Accuracy · p. 6

B. Evaluation in Terms of Charging Cost

  • Method [9] has much higher charging cost than the three cost-aware algorithms; CSA and DCSA differ by 2%.The cost difference between method and CSA is attributed to forecasting accuracy; CSA’s charging-cost result is unavailable above 2,000 EVs because of computational complexity.Source: Figure 5 · p. 7, B. Evaluation in Terms of Charging Cost · p. 7

C. Evaluation in Terms of Charging Time

  • 30% shorter average charging time: CSA and DCSA take 9.08 and 8.88 hours, versus 12.74 and 12.88 for the cost-minimizing and convenience-maximizing methods.For the 10th EV, CSA and DCSA charge at the maximum rate for a few slots, while method spreads demand across the charging period until the deadline.Source: Figure 6 · p. 7, C. Evaluation in Terms of Charging Time · p. 7, Figure 7 · p. 7

D. Evaluation in Terms of Computation Time

  • With the same available power, the distributed algorithm achieves the same performance as the centralized one; DUCM converges after 10 iterations and makes a decision in under one second for 2,000 EVs.DUCM needs more time for 2,000 EVs because of iterations between all SAs.Source: D. Evaluation in Terms of Computation… · p. 8

E. Comparisons with different methods

  • DCSA’s total charging cost is almost the same as method ’s, and its post-charging peak load is the same; its total user convenience is slightly higher because it considers more parameters.Source: E. Comparisons with different methods · p. 8

F. Evaluation in Terms of Data Rate

The distributed method reduces message transmission relative to the centralized algorithm, with the reduction varying by setting; the conclusion describes it as a low-complexity alternative with comparable performance.

F. Evaluation in Terms of Data Rate

  • 33.25% fewer transmitted data units with DCSA than CSA in the evaluated 200-EV, six-sub-aggregator case.The reduction varies across settings; the authors note it remains considerable in most scenarios where EV count exceeds charging-station count and sliding-window length.Source: Table IV · p. 9, F. Evaluation in Terms of Data Rate · p. 9

VI. CONCLUSION

  • The distributed algorithm offers performance comparable to the centralized algorithm while significantly reducing computation complexity and transmitted messages.The conclusion describes the centralized algorithm as potentially having high computational complexity and data transmission rate.Source: §VI · p. 9

APPENDIX

The appendix argues that the proposed algorithm selects a Pareto-optimal solution by prioritizing charging-cost minimization and then user convenience.

A. Proof of Pareto Optimality

  • The proposed algorithm’s solution is Pareto-optimal: it first minimizes charging cost, then selects the highest-convenience charging pattern at that cost.The proof states that the competing solution cannot improve user convenience while retaining the same optimal cost.Source: A. Proof of Pareto Optimality · p. 10, Figure 10 · p. 10
  • The selected point is not the only option on the Pareto front; other charging-station or EV-owner preferences could lead to exploring alternatives.The appendix excludes the two extreme solutions: one does not meet user requirements, and the other represents uncontrolled immediate charging at higher cost.Source: A. Proof of Pareto Optimality · p. 11

2 Lbase

The derivation invokes Jensen’s inequality and then introduces a representation of the optimal solution.

2 Lbase

  • The derivation invokes Jensen’s inequality before introducing a representation of the optimal solution.Source: §2 · p. 11
Loading 1803.04750v2…