Skip to Content

How Smart Cities Must Plan for Electric Cars

In a smart city, every electric vehicle must have access to a charging station within its driving range. So how should these stations be located? The good news: computer scientists have solved the general version of this problem. The bad news: it’s NP-hard.

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: Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions

Keep Reading

Most Popular

Large language models can do jaw-dropping things. But nobody knows exactly why.

And that's a problem. Figuring it out is one of the biggest scientific puzzles of our time and a crucial step towards controlling more powerful future models.

The problem with plug-in hybrids? Their drivers.

Plug-in hybrids are often sold as a transition to EVs, but new data from Europe shows we’re still underestimating the emissions they produce.

Google DeepMind’s new generative model makes Super Mario–like games from scratch

Genie learns how to control games by watching hours and hours of video. It could help train next-gen robots too.

How scientists traced a mysterious covid case back to six toilets

When wastewater surveillance turns into a hunt for a single infected individual, the ethics get tricky.

Stay connected

Illustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at with a list of newsletters you’d like to receive.