Optimizing Electric Vehicle Charging Station Locations: Exploring Grover’s Quantum Search Algorithm

Principal Investigator(s):

Alireza Talebpour, Assistant Professor of Civil and Environmental Engineering – The University of Illinois at Urbana-Champaign

Project Abstract:
Electric vehicles (EVs) have proven to be an effective solution to address the environmental concerns associated with the transportation sector. Moreover, within the smart charging framework, EVs play a dual role by supporting the stability of the renewable energy grid and providing power during grid stress through vehicle-to-grid (V2G) capabilities. Currently, in the United States, a very small portion of vehicles are electric. The slow market penetration of electric vehicles can be attributed to several factors, including their high price tag, long charging times, driving range, and lack of charging facilities (except for a particular brand that developed its own charging infrastructure). The last two factors, in particular, contribute to range anxiety among potential buyers. However, there are still some longer trips that cannot be completed on a single charge and necessitate the availability of public charging infrastructure. For long-haul freight, long-distance trips, drivers regard the time spent waiting for charging as “deadtime”, emphasizing the importance of installing fast chargers to address these particular users. Nevertheless, the installation and relocation of fast charging stations are costly. Therefore, the optimal locations of charging infrastructure should be identified carefully, considering the problem’s constraints and ensuring widespread access to EV owners and operators. The need for faster adoption of electric vehicles has led to an extensive body of literature on the charging station location problem (CSLP). Unlike facility location problems, in which the demand is expressed as weights on nodes of a network, in most charging station location models the demand is presented as a flow from an origin to a destination, and the charging stations should be placed so that the distance between consecutive stations is within the driving range of electric vehicles. Regardless of the modeling approach employed, solving CSLP in real-life situations poses significant challenges due to the numerous variables and constraints involved. Moreover, the objective function and constraints often exhibit non-linear behavior. As a result, finding exact solutions within a reasonable time frame becomes challenging, leading to the adoption of approximate or heuristic methods. In general, to reduce computational time, it is often necessary to make trade-offs in terms of solution quality. Fortunately, recent advances in quantum computing can provide a solution to address the required computational power and eliminate the need for heuristic methods. Quantum computers have been the subject of significant research and have shown potential for providing speedup in certain problems, like factoring and search problems. Although one of the greatest impediments to realizing this potential is the inherent noise in these systems, there is evidence of the utility of quantum computing even before the implementation of fault tolerant quantum circuits. Considering the aforementioned challenges related to solving the charging station placement problem and the promising speed-up offered by quantum computing, the main objective of this study is to propose a novel approach for optimizing the placement of charging stations, specifically for long-distance trips. The approach involves harnessing the power of Grover’s quantum search algorithm, which has demonstrated quadratic speedup in solving disordered data sequences. This study aims to demonstrate that Grover’s algorithm can efficiently solve the unstructured search problem in a dataset with N elements, achieving a complexity of O(√N), while the best classical algorithm requires O(N) time for the same task.

Institution(s): University of Illinois at Urbana-Champaign

Award Year: 2023

Research Focus: Mobility, Equity

Project Form(s):