Leveraging quantum methods for optimizing EV charging infrastructure
The Need For EV Charging Network Expansion
The adoption of electric vehicles (EVs) is now widespread. Compared to 2019 where EVs only accounted for 1.6% of vehicles, in 2020 they grabbed 6.6% of the total global vehicle market. But according to a report made in October 2020, while EV sales have grown over 110%, the number of public charging points have only grown 58%. This is quite a problem — in other words the increase in the number of EVs as more people are adopting it will lead to an unmanageable increase in the demand for power generation if we don’t expand our charging networks.
Expanded charging infrastructure will especially assist for those who
- Live in apartments where their parking garages aren’t necessarily equipped with charging infrastructure
- Make long-distance trips that require multiple stops for charging especially in areas where there is low availability of charging stations
EV infrastructure stability is affected as a result of energy demands to support an exponential expansion in EV charging networks. In serving the volume in the number of EVs, the number of charging stations will have to increase. Most of them are placed in convenient, high-density areas which will lead to increased energy demand and utility congestion. In this case the sites’ internal structure and constraints need to be considered.
This means that we need to focus on 2 main areas in order to successfully maximize utilization and minimize cost during the expansion of EV charging infrastructure. These include 1) optimizing for network size including the number of electric vehicles charging as well as the number of charging sites that need to be powered and 2) accounting for individual and cumulative driver data in terms of when/where they will be charging, for how long, states of charge using, etc.
Lots of people will be involved during the process of expansion. A few stakeholders within optimal charging siting include:
- Drivers — optimal charging experience in terms of convenience and time as well as lower charging costs
- Charge point operators or EV infrastructure providers — increased and more predictable utilization of assets and lower grid connection costs, are able to optimize planned EV rollout
- Distribution system operators —have foresight on charging infrastructure deployment and resulting load which will lead to an optimized investment in the grid
- Utilities/aggregators —an increase in plugged vehicles will allow them to offer more valuable services to the grid and their customers
Data regarding electric grid activities needs to be collected from utilities and be combined with the site and usage data from current EV charging infrastructure in order to determine long-term energy use design and optimal energy production. This all comes under the main goal for a more reliable network with optimized energy consumption adjusted to increasing EV adoption.
Current Methods & Monte Carlo
How do we go about with doing this? In completing the data collection process, we also have to consider these set of factors:
- As previously mentioned — Efficient scheduling for EV charging (given the current sparse charging infrastructure and long charging times) which is dependent on the constraints and demands of the customer and electricity distribution network as well as the availability of charging stations.
- Employing the use of the Vehicle-to-Grid (V2G) mode of operation where the EV batteries can be used as storage devices, which can in turn increase the storage capacity of the network
- Acknowledging other emerging modes of transportation and the features / benefits they enable such as autonomous vehicles and mobility-on-demand. Energy efficient routing needs to exploit these abilities.
Given all the sets of parameters that we need to consider, this will automatically fit under as an optimization problem. In other words, it’s the question of what is the optimal solution whether that be with charging scheduling, energy efficient routing or EV and smart grid renewable energy utilization based on the set of given constraints and parameters?
The current popular methods organizations exploit for optimization problems are AI and ML techniques including heuristic and meta-heuristic algorithms and multi-agent systems.
Monte Carlo
For example, Monte Carlo simulations are a common mathematical technique to approximately solve stochastic optimization problems. The Monte Carlo method is able to output a range of all possible outcomes, assessing the impacts of risk and the probabilities that will occur for any choice of action.
By using repeated random sampling, this method is able to make numerical estimations from unknown parameters and in turn allow the modeling of different complex situations that have many variables involved while being able to assess the impact of risk.
It in turn allows for better decision-making by displaying the extreme possibilities, with all the different outcomes outlined under certainty.
What does the Monte Carlo method actually do? Monte Carlo performs a risk analysis by providing a probability distribution (substituting a range of values to build the model of possible results) in order to make the models for possible results.
It then repeatedly calculates the results, using a different set of random values from the probability function with each round, which typically involves thousands of recalculations before it produces the final distributions of all possible outcome values.
This process carries a set of benefits including:
- All combinations of input parameters are tested and the values for each parameter cover the full range for more sufficient analysis
- Tens of thousands of different scenarios are able to be run, then automatically collects and summarizes the results with all the details
The results after the processing is finished include:
- Probabilistic Results — the likeliness of each outcome
- Sensitivity Analysis — which inputs had the greatest effect on the results
- Scenario Analysis — shows the combinations of values and different inputs to create certain outcomes
- Correlations — models interdependent relationships between input variables
Time & Computational Power
This all sounds great, but why aren’t they being widely used today? The reason is because of time and computational power. With a few input parameters, the values of the parameters can cover a wide range, which in turn creates a huge number of different scenarios. This would be extremely difficult to process on today’s computers.
For example, say we have 10 different inputs and 10 different values in terms of parameters when creating EV charging infrastructure design. There would be 10¹⁰ (10 billion) different scenarios to output.
How are we supposed to model billions of different scenarios? That would probably take months, assuming that your computer doesn’t break down in the process.
But it’s not just with the Monte Carlo method. Classical optimization algorithms in machine learning when applied to a multidimensional problem like this one take a long time to compute because they require an intensive amount of resources in terms of the amount of CPU and GPU.
In general, classical algorithms do not do well when dealing with this high dimensional problem space in trying to complete the optimization. Optimization problems within machine learning often reach NP-hard in their complexity and will be extremely difficult to handle in our current classical computers.
What if we could speed up this process while not having to worry about the amount of computational power? This is where quantum computing and quantum optimization methods comes in.
Why quantum computing?
In regular machine learning when solving an optimization problem, the complexity increases with the size and dimensionality of the input data. So in that case large datasets with different parameters and constraints will have huge complexity.
With quantum computers, they are designed to handle problems involving complex, high-dimensional spaces because they are able to handle tensor and dot products well, which in turn will help speed up the learning process. Feature selection within a complex data set involves in an exhaustive search, where the complexity reaches exponential, which is often considered impractical. Heuristic methods will have to then be employed to undertake this effort.
On the other hand, quantum computers are able to complete the optimization problem within polynomial time, without a need for heuristic optimization methods.
In quantum mechanics, the basic units include qubits, which encode classical bits 0 and 1 into “quantum” bits of |0⟩ and |1⟩. Qubits can also be in a superposition of states with both |0⟩ and |1⟩, simultaneously being in all of the system’s states.
You can compare this to spinning a dime (as seen above) as opposed to flipping a coin. When you flip a coin, the outcome will turn out to be either heads or tails, 1 or 0. But when you spin a coin, it appears to be both heads and tails at the same time, 01 or 10.
In other words, the superposition property allows for the quantum computer to run multiple problems all at the same time. A computer with n qubits will allow for 2^n solutions to be run simultaneously. 10 qubits = 1024 solutions.
This property allows quantum computers to perform parallel computations on a massive scale. With this, they have the potential to greatly reduce the time and cost to execute the long and complex calculations used in the methods for optimizing EV charging infrastructure. With the addition of every qubit to a quantum computer, the performance doubles which creates an exponential boost.
QAOA for optimizing charging infrastructure
Optimizing EV charging infrastructure as mentioned before includes determining optimal locations in order to minimize impact on the grid and provide enhanced driver experience. A few other influencing factors with the transition to EVs include charging convenience in terms of location, speed of charging and vehicle range.
Optimizing charging infrastructure = maximizing utilization + minimizing cost
A large number of questions will arise as we’re trying to optimize current EV charging infrastructure which will be used to determine the specific parameters and constraints.
Questions and factors to consider with 1) optimum locations for utilization:
- When/where will EVs be bought?
- Where will the EVs travel? Where would it be convenient to charge?
- What speed of charging will be needed?
- Where are EVs most likely to reach a specific state of charge on a longer journey?
- How will this change over time with developments including increased battery capacity, faster charging, longer range vehicles?
Other questions and factors to consider with 2) optimum locations to minimize costs with grid connection
- What is the available capacity on the networks?
- What other load is on the system?
- What are the power requirements for the chargers? When will this power be needed?
With all of these factors to be considered, this would be classified under a large-sized combinatorial optimization problem, taking the form as a “scheduling” or “operational research problem” which makes it NP hard.
With this type of optimization problem, it is best suited to use the Quantum Approximate Optimization Algorithm or QAOA.
Combinatorial optimization refers to searching for an optimal solution in a finite set of potential solutions. An optimal solution is defined with respect to a criteria or cost function, which can be either minimized or maximized. In this case since we are considering factors such as utility, efficiency, output and capacity, this would fit under maximization.
For example, we can be presented with the problem: what is the best way to arrange EV charging stations to maximize the distance to existing and new charging stations? A few factors are presented including existing charging locations, target point locations, and quantity of locations. Ideally in this case new charging locations should be placed near target point locations (ex. city centers). New charging locations should also be placed away from existing and other new charging locations in order to 1) minimize overlap and 2) maximize coverage. There are 4 independent constraints.
In addition to this, we can break the situation further into 2 independent problems with factors including individual charging jobs, time and loads:
Problem 1: given a set of n charging jobs for a number of EVs to be scheduled on a set of k charging points, there is an integer weight associated with each job, j, that measures its importance (prioritize the charge of a specific vehicle, say if it is an emergency vehicle). The time at which a load for a job ends is referred to as the completion time. We need to minimize the weighted total time of completion of the charges. → This is a classical scheduling problem known to be NP-hard.
Problem 2: given a set of load tasks represented as intervals on a timeline where each of them belongs to a specific classifying group, ex. distinct vehicles in a company, select a subset of the loads which 1) maximizes the number of non-overlapping tasks and 2) at most one load within each group is completed. We need to minimize the completion time of the selected loads and guarantee no single group is over-represented in the scheduling. → This is an interval scheduling problem.
QAOA
How do we apply QAOA to all of this? With QAOA, some interactions between the different points will call for more attention than others. For example, say that charging points 1 and 2 are very close to each other and we need to separate them in order to maximize the distance between the charging stations. In this case, the edge between 1 and 2 would be assigned a larger weight.
Going back to our original optimization problem, the equivalent expression would be how can we assign the EV charging stations in order to cut the maximum total edge weight?
As seen below, the variable xi is assigned to each charging station i where xi = 1 represents target point locations and xi = 0 represents other (not ideal) locations. For any edge, the algorithm is cutting the edge wi,j if xi(1-xj)=1. The cost function to be optimized in this case is the sum of the weights in the edges connecting points in the subsets that were created during a cut of the original set. The cost function will then be maximized, which is referred to as a weighted MAXCUT.
The following steps are then completed:
- An n number of qubits is used to represent the variables xi. As an example, if the first charging station were assigned 0 and all the other ones 1, it would look like this: |011111111>. This is defined as one possible outcome.
- A uniform superposition of all possible solutions is completed by applying a Hadamard operator to each qubit so that all of the different outcomes have an equal probability of happening.
- A quantum phase rotation is applied that is proportional to the cost of the solution so that the best solutions (ideal locations) progress farther than the other solutions in a unit circle representation.
- The best solutions are “moved out” from the unit circle while the worse solutions are moved into the unit circle. These filter the solutions so that the best solutions are more likely to be measured at the end.
- More iterations are performed where the best solutions move out and the worse ones move in.
- The state of the qubits are measured to output the most likely or optimal solution. This will ideally represent the placing for EV charging locations.
Compared to classical optimization algorithms, QAOA gives a quadratic speedup when finding the optimal placement.
Check out a sample implementation using Dwave’s hardware on github: https://github.com/aliceliu7/Quantum-EV-Charging-Optimization
What’s next?
Other quantum applications- batteries and grid
In addition to quantum algorithms being used for the optimization in EV charging infrastructure, they can also be deployed in applications including the development of more efficient solid-state metal batteries for EVs and optimizing for electric power grids.
Today lithium-ion batteries are used in the EV industry. Quantum computers can help accelerate the development of even more efficient batteries with increased battery performance, charge capacity, battery life, while having decreased costs.
As of today, we don’t really know what is happening inside the battery at a molecular level and there currently is no classical computer that is able to accurately simulate what’s happening within the complex ecosystem of a battery.
Even for simple molecules, the number of quantum states in a molecule (number of electrons interacting the system) is tremendous. Creating a simulation for a single molecule can greatly overwhelm the memory and calculating power of a classical computer. In order to simulate this at a molecular level, we need to account for many different interactions within electrons. Accurately simulating the interactions of these complex molecules takes many days, not to mention simulating the reactions inside a battery.
Designing batteries as of today is a process of trial and error that takes many decades. Quantum computing will give the opportunity to simulate the chemical reactions in batteries more accurately and efficiently than our current classical computers, which will allow for the exploration of new materials to create more efficient batteries.
Because quantum computers leverage the superposition of qubits where they can represent states of 0, 1, or 0 and 1 at the same time, we can leverage this for an exponential boost with increased performance. Qubits, like the molecules that are simulated, function according to the laws of quantum mechanics.
Optimization methods including quantum annealing can then be used to find a compound’s ground state during molecular simulation. These optimization methods can be carried even further when we’re dealing with another important aspect within EV charging infrastructure: electric power grids.
As EV loads continue to increase, new transformations will have to be made to these electric power grids. Advanced computation, specifically with quantum computation, will be needed to solve network power flow problems as we’re considering new classes of complexity that may pose challenges for applications like system forecasting. Quantum optimization can then be used to address the computational needs of the grid including dealing with uncertainty, quantification and controlling resilience and reliability.
As we’re moving on to the quantum era, there will be an endless amount of opportunity and applications to further improve the speedup and optimization in our current methods of computing.
Optimization methods for electric vehicle applications is one crucial and exciting aspect as we’re advancing to era. Quantum right now is just like the Internet from the 70s- lots of potential but still a lot of developments to be made before it can be deployed wide-scale. Now it’s a matter of working towards this as we’re reaching to the new age.
