Smoothed Least-laxity-first Algorithm for EV Charging

Yorie Nakahira, Niangjun Chen, Lijun Chen, Steven H. LowE-energy 2017 · DOI

Introduction

The rapid proliferation of electric vehicles (EVs) presents a significant challenge for power grid stability. "Uncontrolled" charging, where vehicles draw maximum power immediately upon connection, can lead to voltage instability and transformer overloads. Effective charging station management requires intelligent scheduling algorithms that can leverage the inherent flexibility of EV charging—where the duration of a vehicle's stay often exceeds the time required for a full charge.

The primary difficulty lies in the "online" nature of the problem: charging stations must make scheduling decisions without knowledge of future vehicle arrivals. While "offline" algorithms with perfect foresight provide a theoretical benchmark, they are impractical for real-world deployment. Conversely, existing online algorithms often rely on complex predictive models, require significant computational resources, or produce "chatter"—rapidly oscillating charging rates that can degrade battery health.

Methodology: The sLLF Algorithm

This research introduces the Smoothed Least-Laxity-First (sLLF) algorithm. The core concept revolves around laxity, defined as the remaining time a vehicle stays at the station minus the time required to complete its charge at the maximum rate. Laxity represents the "scheduling margin" available for each vehicle.

From LLF to sLLF

The classic Least-Laxity-First (LLF) heuristic prioritizes vehicles with the smallest laxity. While simple, LLF frequently causes charging rates to oscillate as laxity values fluctuate and cross one another. sLLF addresses this by formulating the scheduling task as a small optimization problem at each time step. Instead of a simple sort-and-charge approach, sLLF aims to maximize the minimum resulting laxity across all connected vehicles. By employing a strictly concave, "smoothed" objective function, the algorithm ensures steady charging rates and eliminates damaging "bang-bang" control behavior.

Resource Augmentation Framework

To evaluate performance, the authors utilize a Resource Augmentation framework. This method measures the additional power capacity ($\epsilon$) an online algorithm requires to match the performance of an optimal offline algorithm with zero foresight.

Experimental Setup

The sLLF algorithm was rigorously tested against massive real-world datasets from 2016, encompassing over 52,000 charging sessions:

  • CAGarage: Data from the Caltech Adaptive Charging Network (ACN) testbed.
  • Google mtv & Google svl: Data from Google’s corporate charging facilities in Mountain View and Sunnyvale, CA.

These datasets provide a realistic representation of the high variability in user behavior, including diverse arrival times, stay durations, and energy requirements.

Results and Discussion

Robustness and Performance

sLLF demonstrates exceptional robustness across varying conditions. Unlike standard heuristics such as Earliest-Deadline-First (EDF) or Equal Sharing (ES), sLLF maintains a high success rate even as the "sojourn time ratio" (the ratio of stay duration to required charging time) decreases or becomes highly variable.

Success rate performance across different metrics: (a) sensitivity to sojourn time ratio and (b) sensitivity to minimum normalized laxity.

As shown in Figure 1, sLLF (red line) and Online Linear Programming (OLP, yellow line) consistently outperform other methods. Notably, sLLF remains stable where others fail as the minimum normalized laxity approaches zero.

The Efficiency of Resource Augmentation

A key finding of the study is the "0.07 magic number." The researchers found that sLLF achieves 100% feasibility—successfully meeting the energy demands of every vehicle by their departure time—with only a 7% increase ($\epsilon = 0.07$) in power resources compared to the offline optimal.

Success rate vs. resource augmentation ($\epsilon$). sLLF reaches 100% success rate with minimal additional power capacity.

In contrast, other common algorithms require significantly more resources to guarantee the same level of success, with some needing up to a 461% increase in power capacity. Furthermore, sLLF is computationally efficient, with a complexity of $O(|V_t| + \log(1/\delta))$, making it significantly faster and more scalable than OLP methods.

Conclusion and Future Directions

The sLLF algorithm provides a practical, high-performance solution for online EV charging scheduling. By smoothing the laxity-based objective, it achieves near-optimal results without the hardware-damaging oscillations of previous methods.

Future research will focus on addressing user uncertainty regarding departure times, integrating explicit battery degradation models, and extending the algorithm to handle three-phase power systems in industrial settings.

Summary updated

BibTeX
@inproceedings{nakahira2017smoothed,
  author = {Yorie Nakahira and Niangjun Chen and Lijun Chen and Steven H. Low},
  title = {{Smoothed Least-laxity-first Algorithm for EV Charging}},
  booktitle = {E-energy},
  year = {2017},
  doi = {10.1145/3077839.3077864},
}
Figure