A Quantum Optimization Algorithm for Optimal Electric Vehicle Charging Station Placement for Intercity Trips

Electric vehicles (EVs) play a significant role in enhancing the sustainability of transportation systems. However, their widespread adoption is hindered by inadequate public charging infrastructure for long-distance travel. Identifying optimal charging station locations in large transportation networks is an NP-hard combinatorial optimization problem. This paper applies Grover Adaptive Search (GAS) to improve the efficiency of solving the Charging Station Location Problem (CSLP). The proposed method achieves a quadratic improvement in computational complexity over classical exact methods, such as branch and bound. This paper develops a quantum subroutine that encodes the CSLP constraints by marking feasible solutions with objective value below a given threshold, and integrates this subroutine within the GAS procedure. The approach is demonstrated on a 7-node transportation network in central Illinois, with an analysis of success probability and sensitivity to algorithm parameters.