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

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.


    • English


    • Status: Active
    • Funding: $142834
    • Contract Numbers:


    • Sponsor Organizations:

      Office of the Assistant Secretary for Research and Technology

      University Transportation Centers Program
      Department of Transportation
      Washington, DC  United States  20590
    • Managing Organizations:

      University of Michigan Transportation Research Institute

      2901 Baxter Road
      Ann Arbor, Michigan  United States  48109
    • Project Managers:

      Stearns, Amy

    • Performing Organizations:

      University of Illinois, Urbana-Champaign

      Illinois Center for Transportation
      1611 Titan Drive
      Rantoul, IL  United States  61866
    • Principal Investigators:

      Talebpour, Alireza

    • Start Date: 20230601
    • Expected Completion Date: 20240531
    • Actual Completion Date: 0
    • USDOT Program: University Transportation Centers

    Subject/Index Terms

    Filing Info

    • Accession Number: 01906160
    • Record Type: Research project
    • Source Agency: Center for Connected and Automated Transportation
    • Contract Numbers: 69A3552348305
    • Files: UTC, RIP
    • Created Date: Jan 28 2024 12:48PM