SMART-CHARGE: Stable Matching Algorithm for Electric Vehicle Charging in Subscription-based Models
National Science Foundation, Grant OAC-2104078
Abstract
The transition from internal combustion engine (ICE) to electric vehicles (EVs) introduces several challenges, including limited charging infrastructure, unpredictable charging wait times, and inefficient selection of charging points (CPs). To address these issues, we propose SMART-CHARGE, a framework that efficiently assigns EVs to CPs through an edge-level coordination mechanism within each service region, enforced by roadside units (RSUs). Operating under a novel subscription-based charging model, SMART-CHARGE enforces predefined charging time limits via service-level agreements (SLAs). The EV-CP assignment problem is formulated as a one-to-many matching game that captures EV user preferences. To construct bounded yet efficient EV coalitions at each CP, we introduce three strategies: Preferred Coalition Greedy (PCG) for computational efficiency, Preferred Coalition Dynamic (PCD) for globally optimal coalition formation, and Preferred Coalition Local (PCL), a local search-based method designed to handle arbitrary EV arrival sequences. The resulting assignment is formulated as an optimization problem that incorporates CP capacity, battery constraints, SLAs, and spatially varying charging costs. We establish stability guarantees, analyze computational intractability, and derive asymptotic bounds for the proposed solution. Extensive evaluations using real-world charging datasets compare coalition strategies under variable pricing and SLA constraints. Results show that SMART-CHARGE achieves a polynomial-time solution that improves resource allocation and bounds EV waiting times, delivering at least a 39% improvement over state-of-the-art methods in the overall objective that jointly optimizes charging cost and detour distance.
