Leveraging Knapsack QAOA Approach for Optimal Electric Vehicle Charging
Open Access
- 29 September 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 11, 109964-109973
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.Keywords
Funding Information
- Quantum Computing based on Quantum Advantage challenge research (RS-2023-00257994)
- National Research Foundation of Korea
- Korean government (Ministry of Science and ICT
This publication has 28 references indexed in Scilit:
- On-off scheduling schemes for power-constrained electric vehicle charging4OR, 2016
- A Mean Field Game Theoretic Approach to Electric Vehicles ChargingIEEE Access, 2016
- Smart Charging for Electric Vehicles: A Survey From the Algorithmic PerspectiveIEEE Communications Surveys & Tutorials, 2016
- Electric Vehicle Charging on Residential Distribution Systems: Impacts and MitigationsIEEE Access, 2015
- A review of energy sources and energy management system in electric vehiclesRenewable and Sustainable Energy Reviews, 2013
- Optimal Scheduling for Charging and Discharging of Electric VehiclesIEEE Transactions on Smart Grid, 2012
- Exact solution of a class of nonlinear knapsack problemsOperations Research Letters, 2005
- The multidimensional 0–1 knapsack problem: An overviewEuropean Journal of Operational Research, 2004
- Knapsack Problems2004
- Dynamic Programming and Strong Bounds for the 0-1 Knapsack ProblemManagement Science, 1999