Online Mechanism Design for Vehicle-to-Grid Car Parks

Enrico H. Gerding, Sebastian Stein, Sofia Ceppi, Valentin RobuIJCAI 2016

Introduction

As renewable energy sources like solar and wind become more prevalent, the power grid faces increasing challenges in balancing intermittent supply with demand. Electric vehicles (EVs) offer a potential solution through "Vehicle-to-Grid" (V2G) technology, essentially acting as a massive, distributed battery. However, managing a V2G car park involves significant informational hurdles. Drivers have private preferences regarding their departure times and the costs associated with battery degradation from discharging. Without proper incentives, strategic drivers might misreport their needs to minimize costs, potentially destabilizing the grid management system.

A Framework for Truthful V2G Management

This research addresses these challenges by formalizing V2G management as an online mechanism design problem. The goal is to design scheduling and payment systems that are "truthful," meaning drivers are financially incentivized to report their actual constraints and costs rather than gaming the system.

The authors propose three heuristic online scheduling algorithms:

  1. Algorithm 1 (Threshold-based): A reactive approach that charges when prices are low and discharges when they are high, without considering future price predictions.
  2. Algorithm 2 (MDP-based): Uses a Markov Decision Process to optimize utility based on the probability distributions of future grid prices.
  3. Algorithm 3 (Internal Trading): An extension of the MDP approach that allows EVs within the car park to trade energy with each other, bypassing the price spread (the difference between buying and selling rates) offered by the utility grid.

Crucially, the researchers prove that Algorithms 1 and 2 satisfy "monotonicity" under certain conditions, ensuring that honesty remains the optimal strategy for participants.

Performance and Scalability

The proposed mechanisms were evaluated using a simulated dataset of 100 cars on average over 24-hour cycles. The simulation incorporated realistic parameters for battery capacity, charging rates, and market price fluctuations.

Average Aggregator Utility as a function of the number of agents. Algorithms 2 and 3 maintain profitability as the system scales.

As shown in the figure above, Algorithms 2 and 3 achieve positive profit for the car park aggregator, even without charging drivers for the electricity they consume. The V2G revenue alone is sufficient to cover operational costs and driver compensation. In contrast, simpler methods like Algorithm 1 or the "No V2G" baseline result in net losses as the number of agents increases.

The Value of Flexibility

A key insight from the study is that the flexibility provided by longer parking durations significantly enhances the system's utility. This is not merely because a car can hold more energy, but because it provides the aggregator with more "option value"—the ability to wait for the most favorable market prices to either charge or discharge.

Impact of maximum parking duration on average aggregator utility. Longer stays provide more opportunities for profitable V2G operations.

The data indicates that as the maximum duration of stay increases, the utility for the MDP-based algorithms (2 and 3) grows substantially. This highlights that car parks can derive significant value from drivers who stay for extended periods, such as during a full workday.

Conclusion and Future Directions

By treating battery degradation as a primary cost and ensuring truthfulness through mechanism design, this framework provides a robust path toward viable V2G car parks. The results demonstrate that sophisticated, prediction-aware algorithms can turn a car park into a profitable grid-balancing asset. Future work will focus on relaxing the assumption of linear battery degradation and testing these heuristics against real-world charging data from diverse locations like transit hubs and shopping centers.

Summary updated

BibTeX
@inproceedings{gerding2016online,
  author = {Enrico H. Gerding and Sebastian Stein and Sofia Ceppi and Valentin Robu},
  title = {{Online Mechanism Design for Vehicle-to-Grid Car Parks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure