IEEE Transactions on Intelligent Vehicles
Quantum-Accelerated Electric Vehicle Charging Scheduling with Graph Coloring
Thinh Q. Dinh, Thinh Nguyen, Tam Nguyen, Uman Khalid, Hyundong Shin
Abstract
Electric vehicles (EVs) have emerged as the transportation of the future due to their environmental benefits and fuel efficiency. However, as EVs adoption grows, efficiently managing charging schedules has become a critical challenge due to limited charging infrastructures. EV charging scheduling (EVCS) is a well-known problem within EV charging systems and is generally modeled as an NP-hard graph coloring problem. Recently, quantum computing has emerged as a novel technology that revolutionizes the conventional approach in solving complex optimization problems. However, current noisy intermediate-scale quantum (NISQ) computers lack sufficient hardware capacity to tackle large problem spaces. To address this insufficiency, we propose a hybrid quantum-classical (HQC) optimization pipeline mainly consisting of Hamiltonian reduction, quantum computation, and solution recovery. Theoretically, we demonstrate that optimal graph coloring and EVCS solutions can be recovered if the ground state is found for the reduced Hamiltonian. Numerically, using the Caltech ACN dataset (2018-2019 observations), our approach increases the number of executable EVCS instances on quantum simulators (IonQ, QASM, and Rigetti) from 1.30%- 2.28% to 54.23%-54.72%, thereby outperforming Roof Duality and FastHare (2.28%-6.68%). On the D-Wave Advantage, executable instances increase from 11.89% to 80.46%, compared to 13.52% and 19.87% with Roof Duality and FastHare. These results present promising opportunities for advancing quantum computing research on EVCS within intelligent transportation systems.