The market for electric vehicles is booming. Take Tesla for example, which is making some 500 electric vehicles per week in California and has promised to deliver some 21,000 this year.

And other manufacturers are following suit—recent additions to the market include the Nissan Leaf, the BMW i3, the Ford Focus Electric and the Honda Fit EV to name just a few. If you aren’t already driving an electric vehicle, it can’t be for lack of choice.

There are plenty of reasons to hesitate, however. And one of them is the availability of charging stations where you can plug in and pick up some juice. In most cities, charging stations are few and far between. That means journeys have to be carefully planned to avoid the possibility of flat lining while out and about.

That’s entirely different to the experience that drivers of cars with internal combustion engines have. In almost every city in the world, these drivers are within a short drive of a gas station so the chances of running out before they get there are slim.

That raises an interesting question. How should charging stations be distributed within a city so there’s always one within reasonable driving range?

At first sight, the problem looks easy to solve: just put charging stations in every gas station.

Unfortunately, that doesn’t work because charging takes such a long time that gas stations, which have limited forecourt area, would quickly become full. What’s more electric cars generally have a lower range than gasoline-powered cars so there’s no guarantee that the existing network of stations would do the trick.

So charging stations will have to be distributed in a different way, usually in special parking spots on ordinary roads and in car parks. But how far apart should they be?

Today, we get an answer of sorts thanks to the work of Albert Lam and pals at Hong Kong Baptist University. These guys report some bad news. They show that the general problem of planning the optimal locations of charging stations is NP-hard, meaning that there’s no shortcut to finding good solutions other than sheer brute-force calculating.

Nevertheless, they have developed a number of algorithms that can find solutions for different scenarios.

Their first task is to formulate the problem in a way that makes it tractable. Lam and co start by considering a grid of charging stations and then define a number of conditions this grid must satisfy for it to be properly planned for electric vehicles.

The first condition is obvious: a fully charged electric vehicle at a given charging station must be able to reach another station. In other words, the distance between stations must be less than the range of the vehicle.

The second condition relates to the number of electric cars in the area around a charging station, which determines the local demand for charging. This demand has to be satisfied by the capacity of the local charging station and by a certain fraction of the capacity of other stations within range. This fraction represents drivers’ willingness to charge up at a station other than their local one. And the smaller this fraction, the higher the density of charging stations must be.

The last condition is that the charging stations must cover the entire city. So it must be possible to travel from every part of the city to every other part of the city by hopping from charging station to the next.

“The conditions all together guarantee that the serving areas of the charging stations cover every corner of the city for all possible EVs,” say Lam and co.

They go on to show that this problem is NP-hard and then develop a number of algorithms that can find solutions. Most of them start by randomly distributing charging stations around the city and testing to see if this network meets the criteria. When it does, and various other criteria are minimized, that’s a solution.

Clearly that’s a long winded and time consuming way of coming up with a solution. But that’s the nature of NP-hard problems—there’s no other way to tackle them other than with this kind of brute force.

Finally, Lam and co apply their methods to Hong Kong, where the government is planning a major investment in electric vehicle technologies to improve air quality, while reducing the reliance on fossil fuels. In future, Hong Kong’s buses, taxis and many other vehicles will all be electric. “The construction of charging stations is one of the crucial steps in the plan,” say Lam and co.

So they’ve produce a number of possible grids but they could produce other solutions as well if necessary and these could eventually be optimized for other factors such as the amount of traffic on the roads and so on.

That should certainly be useful for helping Hong Kong achieve its ambitious plans. And it’s quite possible that other cities will soon want to develop their transport infrastructure in the same way. All of these places undoubtedly face long inventories of problems that have to be tackled. Thanks to Lam and co, one of them can now be crossed off the list.

Ref: arxiv.org/abs/1310.6925: Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions