As electric vehicle (EV) adoption accelerates, charging infrastructure has become a significant bottleneck. A primary cause of inefficiency is "overstaying" — when a vehicle remains in a charging spot long after its battery is full. This paper, originally presented at IJCAI-16, proposes a mathematical framework to determine the optimal overstay penalty: one high enough to discourage spot-hogging but low enough to avoid deterring risk-averse drivers.
The Overstaying Problem
Charging service providers face a delicate balancing act. While high penalties could eliminate overstaying, they introduce a "risk-aversion" problem. Drivers often cannot predict the exact duration of their errands or appointments. If the fear of a steep fine is too great, they may avoid the facility entirely, leading to underutilization. The researchers sought to identify the "Goldilocks" penalty that maximizes both station utilization and revenue.
Modeling User Behavior and Queueing Dynamics
The authors developed a novel framework that integrates human behavior modeling with queueing theory. Users are characterized by three primary variables: the required charging time ($T_c$), the desired parking duration ($T_a$), and a maximum penalty threshold ($C_{max}$). A driver will only use the facility if they estimate the potential penalty will not exceed their personal "pain threshold."
The facility itself is modeled as an $M/G/N/N$ queue (Poisson arrivals, general service time, $N$ spots, and no waiting room). This allows for the calculation of steady-state utilization and throughput under various penalty schemes. To handle real-world scenarios where customer behavior distributions are unknown, the authors introduced UCB-PC, an online learning algorithm that identifies the optimal penalty rate through exploration and exploitation.
Key Insights and Results
A significant finding is the alignment between revenue and utilization. The penalty rate that maximizes revenue is remarkably close to the one that maximizes infrastructure utilization. This suggests that profit-driven motives by providers can lead to socially optimal outcomes for the EV ecosystem.
Key results from the simulations, validated using real-world EV charging data from London, include:
- The Penalty Advantage: Implementing even a modest penalty is significantly better than having none. In simulations, a small penalty increased utilization from 26% to 30% and nearly doubled revenue.
- Revenue Optimization: The revenue-maximizing penalty achieved an 85% increase in revenue compared to a "no penalty" scenario.
- Rapid Convergence: The UCB-PC algorithm successfully identified near-optimal penalty rates within approximately 15 days of operation, demonstrating its practical utility for facility managers.
Limitations and Future Directions
While the framework provides a robust starting point, it assumes static user behavior distributions. In practice, these patterns likely shift based on seasonality or local events. Furthermore, the current model considers a single facility in isolation, without accounting for competition between different charging stations. Future research could extend this work to include game-theoretic interactions between competing facilities and more complex, non-linear models of human behavior.
Summary updated