Abstract
This paper addresses the challenge of managing Electric Vehicle (EV) charging networks by proposing the Online Posted-Pricing Algorithm (OPA). OPA jointly optimizes pricing and scheduling decisions in real-time without knowledge of future arrivals. By utilizing an online primal-dual framework and a "water-filling" scheduling strategy, the algorithm achieves a theoretical competitive ratio that is order-optimal. Empirical evaluations using the Caltech ACN-Data demonstrate that OPA significantly outperforms existing benchmarks, providing a robust solution for maximizing social welfare in capacity-constrained charging environments.
Introduction
As cities transition to electric mobility, public charging stations face a dual challenge: limited physical capacity (transformers and ports) and fluctuating electricity costs. To manage this infrastructure effectively, operators must make two critical decisions every time an EV arrives: what price to offer the user and when to schedule the power delivery.
This decision-making process occurs "online," meaning the operator lacks information about future arrivals, their battery requirements, or their willingness to pay. While prior research often handles pricing or scheduling in isolation, or relies on "fractional" assumptions (e.g., admitting half an EV), this paper tackles the integral version of the problem—where an EV is either fully admitted or not—and optimizes for total social welfare.
Problem Formulation
The authors frame the challenge as an extension of the Online Knapsack Problem, where charging slots are treated as reusable resources. The objective is to maximize the total value provided to the community (social welfare) while respecting physical capacity constraints and minimizing electricity costs. This requires a mechanism that can filter arrivals based on their private valuations and schedule their energy intake efficiently across their stay.
The Online Posted-Pricing Algorithm (OPA)
The core contribution of this work is the Online Posted-Pricing Algorithm (OPA), which combines a dynamic pricing function with a strategic scheduling approach.
1. The Pricing Function
Instead of a static price, OPA employs a dynamic pricing function $\phi$ that scales based on the station's current utilization. This function is derived from an online primal-dual (OPD) framework and is structured into three distinct zones:
- Flat Base: When utilization is low, the price remains at a base level to encourage early arrivals.
- Exponential Curve: As the station nears capacity, the price grows exponentially to increase selectivity.
- Infinite Wall: A hard limit that prevents any schedule from violating physical capacity constraints.
2. Water-Filling Scheduling
When an EV arrives, the algorithm solves a "pseudo-cost" minimization problem. It utilizes a "water-filling" strategy, "pouring" the required energy into the time slots where current utilization (and thus the marginal price) is lowest. If the user's private willingness to pay exceeds the total calculated price for this optimal schedule, the EV is admitted; otherwise, it is rejected.
Theoretical and Empirical Results
Theoretical Order-Optimality
The authors provide a rigorous mathematical foundation for OPA, proving that the algorithm is $O(\ln \theta)$-competitive. This means that even in the worst-case scenario, the algorithm's performance is within a logarithmic factor of an "all-knowing" offline optimal solution. Furthermore, they establish a lower bound showing that no online algorithm can perform better than $\Omega(\ln \theta)$, making OPA theoretically as efficient as possible.
Empirical Performance
The researchers evaluated OPA using the Caltech ACN-Data, a public dataset containing over 50,000 real EV charging sessions. Simulations focused on various congestion levels (low, medium, and high) using a subset of 700 sessions across 90 days. Key findings include:
- Benchmark Superiority: OPA consistently outperformed major benchmarks, including UBOA/PBOA (first-come-first-served heuristics) and OMMP (a recent state-of-the-art online mechanism).
- Performance Stability: In 80% of the experiments, the empirical profit ratio (the gap between the offline optimal and OPA) was less than 2. This suggests that OPA performs exceptionally well on average real-world data, far exceeding its theoretical worst-case bounds.
Conclusion and Future Work
OPA bridges the gap between theoretical online optimization and the practical needs of EV charging networks. By handling the non-convexity of integral admission through a split analysis of capacity-free and capacity-limited instances, the authors provide a robust tool for station operators.
Future research directions include extending the algorithm to handle uncertainty in electricity price schedules (e.g., moving beyond known Time-of-Use rates) and expanding the scope from a single station to a multi-station network where the algorithm must also manage station assignment.
Summary updated