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

Abstract: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.

Quantum Physics (quant-ph); Optimization and Control (math.OC)

arXiv:2410.16231 [quant-ph]

(or arXiv:2410.16231v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2410.16231 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.