Efficient Electric Vehicle Charging Allocation: A Two-Stage Optimization and Participation Analysis

1. Problem Statement

The rapid adoption of Electric Vehicles (EVs) has outpaced the expansion of charging infrastructure, leading to severe congestion at popular charging stations (CSs). Unlike gasoline refueling, EV charging involves long durations (tens of minutes), causing demand concentration to result in excessive queues and waiting times.

• Core Challenge: Uncoordinated charging decisions create congestion externalities, where an individual EV choosing a station increases delays for others, while underutilized stations remain idle.
• Secondary Challenge: Implementing a coordinated system requires user participation. Users may "free-ride" on the benefits of a coordinated network without joining, creating adoption thresholds and "cold-start" problems for platform operators.

2. Methodology

The authors propose a Two-Stage Optimization Framework coupled with a Reduced-Form Participation Model.

Stage 1: System-Level Congestion Control (Quota Allocation)

• Objective: Minimize the worst-case station delay (tail congestion) rather than just average performance.
• Mechanism: A central coordinator determines station-level admission quotas ($f_i$) for each time interval.
• Queueing Model:
  • Stations are modeled as $M/M/c_i$ queues.
  • To ensure tractability in dynamic optimization, the authors use a saturating outflow approximation (based on Gusrialdi et al., 2017) rather than inverting complex steady-state Erlang-C formulas. The departure rate is modeled as $\hat{g}_i(x) = c_i \mu_i \frac{x}{1+x}$.
  • Arrival rates ($\lambda_i$) are estimated using a moving average of historical flows to account for short-memory effects.
• Optimization: The problem is formulated as minimizing an auxiliary variable $z$ (representing the maximum delay $W_i$) subject to flow conservation and stability constraints ($\lambda_i < c_i \mu_i$).

Stage 2: User-Level Welfare Maximization (Assignment)

• Objective: Allocate specific EVs to stations within the quotas set in Stage 1 to maximize aggregate utility.
• Feasibility: An EV $n$ can only be assigned to station $i$ if it is reachable given its State of Charge (SoC) and distance ($d_{ni}$).
• Charging Amount Optimization:
  • To handle heterogeneous charging needs efficiently, the optimal charging amount ($E^*_{ni}$) for each EV-station pair is pre-computed in closed form.
  • This maximizes a quadratic benefit function $\phi(E)$ (balancing charging benefit against price and anxiety/curvature parameters) subject to battery capacity constraints.
• Assignment Problem: The allocation is formulated as a capacitated transportation/assignment problem (binary decision variables $x_{ni} \in \{0,1\}$).
  • Congestion Internalization: The model offers two modes:
    1. Hard Control ($\eta=0$): Congestion is controlled strictly via the quotas from Stage 1.
    2. Soft Adjustment ($\eta>0$): Congestion is explicitly priced into the utility function as a time-cost term, allowing for marginal shifts away from congested stations.

Participation Analysis (Reduced-Form Model)

• Framework: A game-theoretic adoption model analyzing the sustainability of the coordinated platform.
• Payoff Structure:
  • Joiners ($J$): Gain network benefits ($Am - Bm^2$) minus coordination costs ($c$).
  • Non-Joiners ($NJ$): Gain spillover benefits ($Gm$) from the coordinated group (free-riding) but pay no coordination cost.
• Result: The model identifies adoption thresholds. The platform is sustainable only for an intermediate range of participation rates ($m \in [m_1, m_2]$), highlighting the need for initial incentives to overcome the "cold-start" problem where early benefits are insufficient to cover joining costs.

3. Key Contributions

1. Unified Two-Stage Framework: Explicitly separates system-level congestion control (Stage 1) from user-level welfare maximization (Stage 2). This contrasts with existing literature that often focuses solely on queueing dynamics or pricing/routing without a hierarchical structure.
2. Tractable Assignment under Quotas: Unlike stable-matching mechanisms (e.g., Gale-Shapley) that allow stations to "reject" users, this approach uses a capacitated assignment model. It pre-computes optimal charging amounts in closed form, reducing the complex non-linear problem to a standard transportation problem solvable via min-cost flow or LP methods.
3. Welfare-Congestion Bridge: Provides a clear economic interpretation of congestion control via the parameter $\eta$. It demonstrates how congestion can be handled either as a hard operational constraint or a soft welfare penalty.
4. Participation Threshold Analysis: Moves beyond the assumption of full participation by modeling the free-rider problem and identifying the specific conditions (network benefits vs. coordination costs) under which a coordinated platform remains viable.

4. Numerical Results

Simulations were conducted comparing the proposed two-stage mechanism against:

• Free Choice: EVs select the nearest feasible station.
• Matching-Based Baseline: A Gale-Shapley style algorithm (Yoshihara et al., 2020).

Key Findings:

• Congestion Reduction: The two-stage mechanism achieves substantial reductions in worst-case congestion (maximum queue length and delay) compared to free choice.
• Utility Trade-off: In small networks, average utility remains close to the free-choice baseline due to limited station options. However, as the number of stations increases, the utility-maximizing assignment becomes significantly more effective, widening the gap in favor of the optimized allocation.
• Comparison with Matching: The proposed method outperforms matching-based baselines in utility and delay profiles because it avoids station-side rejections and strictly adheres to system-wide quotas.
• Scaling: The benefits of the optimized allocation scale positively with network size.

5. Significance and Implications

• Operational Feasibility: The framework is designed to be computationally efficient and implementable in real-time systems, avoiding the intractability of full dynamic queueing control.
• Policy Design: The participation model offers insights for platform operators and policymakers, suggesting that subsidies or incentives are necessary during the "cold start" phase to reach the critical mass of users required to make the coordinated system self-sustaining.
• Congestion Management: The study validates that controlling the tail of the congestion distribution (worst-case delays) via admission quotas is more effective for system stability than optimizing only for average performance.

6. Limitations and Future Work

• Approximations: The queue-control layer relies on a tractable outflow approximation and quasi-stationary assumptions within time epochs.
• Exogenous Parameters: The participation model uses reduced-form parameters ($A, G, B, c$) rather than deriving them endogenously from the Stage 1–2 optimization.
• Data: Future work aims to calibrate the model with real-world charging network data and introduce time-varying prices and reservation mechanisms.