What's the best way to charge millions of electric vehicles at once?

(Phys.org)—About 350,000 plug-in electric vehicles (EVs) have been sold in the US from 2008—when they first entered the market—to mid-2015. Although EVs still represent a small fraction of the country's 250 million total vehicles, the continual increase in sales suggests that EVs will become even more popular over the next few decades. This raises the question of how millions of EVs may be charged at once on a grid that was not originally intended to supply such large amounts of power.

The main problem, as researchers Rui Carvalho and coauthors from the UK and Slovakia explain in a recent paper published in the New Journal of Physics, is congestion—not road traffic congestion, but charging traffic congestion. In their paper, they show that when the number of EVs being plugged into the network reaches a critical point, the system undergoes a phase transition from a "freeflow" state (where all vehicles can be fully charged within the expected time period, say 4 hours) to a congested state. In the congested state, some vehicles have to wait for increasingly long times to fully charge, resulting in queues of vehicles rapidly building up that will then face even longer charging times.

"With high penetration of electric vehicles, charging at home will increase the stress on the 'last mile' of local distribution networks," Carvalho, a researcher at Durham University in the UK, told Phys.org. "The conventional solution would be to lay copper under the road, so as to increase network capacity. The cost of upgrading the last mile of the network, however, would be prohibitive, and we present an alternative, much cheaper approach that could be implemented with minimal hardware requirements: a software layer and controllers at the point of charge."

As the researchers explain, the congestion problem can be avoided, at least to an extent, by managing how the power is allocated throughout the charging network. A good management strategy can increase the critical number of vehicles that pushes the system over the threshold into its congested state, thereby allowing more vehicles to be charged in their normal charge time.

Distributing charge quickly and fairly

In their paper, the researchers compared two charging strategies ("max-flow" and "proportional fairness") with the aim to guide network designers in deciding which algorithms to implement in the real world. Both algorithms investigated here rely on recent advances that combine tools from optimization and critical phenomena. As vehicles randomly plug in to the network, the network must continually solve the congestion control problem and allocate each vehicle an instantaneous power using the algorithm. The researchers compared the outcomes of both algorithms using simulations that are only possible due to techniques developed since 2012.

As the researchers explained, a good algorithm will have two features: it charges more vehicles at once, and it does so fairly, meaning all vehicles' charging times are roughly equal. As an example of unfairness, the "max-flow" algorithm charges vehicles closer to the main power source faster than those further away, which the researchers expect will not be socially acceptable. Fairness can be quantified by the Gini coefficient, which is traditionally used to measure income inequality. For comparison, the researchers note that Sweden has a Gini of 0.26, the US has a Gini of 0.41, and the Seychelles has the highest Gini of 0.66. The researchers explain that these values might provide a useful benchmark for identifying socially acceptable values for EV charging algorithms.

"The proportional fairness algorithm reaches a maximum Gini of 0.45, which is comparable with the level of inequality in the US society, and thus may be judged sociable acceptable," they write. "The max-flow algorithm, however, reaches a Gini of 0.91, which measures a level of inequality considerably higher than present in any contemporary society."

Fairness beats greed

The proportional fairness algorithm not only scores better on fairness, but it also allows more vehicles to be charged compared to the max-flow algorithm before reaching the critical threshold. The researchers say that they were surprised by the superiority of the proportional fairness algorithm, since the max-flow algorithm maximizes the total instantaneous power, which would seem to lead to a maximization of the number of charged vehicles, but this is not the case. The researchers explain that the downfall of the max-flow algorithm is its "greediness"—its focus on total instantaneous power makes it sub-optimal compared to proportional fairness, which instead focuses on a fair allocation of instantaneous power, and as a result achieves a higher optimum.

"Intuitively, network designers and operators might be led to the conclusion that there will be a price to pay for being fair to users on these local distribution networks, and disregard fair allocations," Carvalho said. "We show that it is possible to 'have your cake and eat it' in the free-flow state: network operators can charge a higher number of vehicles with fair algorithms than with the greedy max-flow, before the system is congested."

Overall, the analysis shows that the most obvious choice isn't always the best, and that careful examination of different algorithms before they're implemented could provide large cost and time savings down the road.

"We see EV charging as a theoretical problem of allocation of scarce (network) resources to a population of heterogeneous and mobile agents," Carvalho said. "From this point of view, we think our paper only scratches the surface of this potentially rich field (for example, our agents are homogeneous). Some questions that come to mind: What would be the effect of heterogeneous agents? How to implement such a congestion control mechanism with a pricing scheme on the links? How to prevent users from cheating on the network?

"Consider the last question. One simple way of cheating would be for an EV to pretend to be not one single vehicle, but many cloned vehicles. Such a 'super car' would then be able to get a much higher allocation than the rest, because the network would see it as many vehicles. This is the mechanism explored in peer-to-peer networks: users get very high bandwidth by breaking down a file to be transferred into file segments, and then sending these segments in parallel over several network connections. How can we design network controllers to prevent this?"

© 2015 Phys.org