Leveraging Knapsack QAOA Approach for Optimal Electric Vehicle Charging

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 a limited power supply and extended waiting times, are required. The knapsack algorithm, a classical technique that maximizes value and capacity, enables 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 method achieves impressive approximation ratios of up to 100% and 50% in noise-free and noisy environments, respectively. Even with a small circuit size, we confirm that our approach can find optimal solutions effectively.

Keywords

• Charging problem
• electric vehicle
• knapsack problem
• limited power supply
• QAOA
• quantum computing