Leveraging Knapsack QAOA Approach for Optimal Electric Vehicle Charging
Kimleang Kea, Chansreynich Huot, Youngsun Han
Abstract
The electric vehicle (EV) industry is currently afflicted with inefficient charging systems. Considering the growing adoption of EVs, optimization strategies for efficient charging, and overcoming constraints such as limited power supply and extended waiting times, are required. The knapsack algorithm, a classical technique that maximizes value and capacity, enables the efficient utilization of the limited available power supply while minimizing waiting times in EV charging scenarios. However, the knapsack problem is notoriously NP-hard, making it difficult to find efficient solutions classically. In this paper, we propose an approach that leverages the quantum approximation optimization algorithm (QAOA) to resolve the EV charging problem using a knapsack-based formulation. By incorporating a knapsack problem constraint into the QAOA, we overcome the limitations of the original QAOA method and provide a potential solution to the knapsack problem. We extensively evaluate and analyze the effectiveness of our approach in finding optimal EV charging solutions in both noise-free simulations and noisy real quantum devices. The proposed approach achieves impressive approximation ratios of up to 100% and 50% in noise-free and noisy environments, respectively. Even with small circuit sizes, we confirm that our approach can find optimal solutions effectively.