New paper: Planning public charging networks is NP-hard

A group of researchers from Hong Kong Baptist University have released a paper that addresses the problems of planning the locations of public charging stations. In Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions, Albert Lam et al look at the issue from the standpoint of Hong Kong, which has ambitious plans to encourage the electrification of much of its vehicle fleet.

Lam and colleagues present several algorithms designed to find solutions for different scenarios, based on the idea that an EV must be able to travel to any part of the city without ever being out of range of a charging station. Alas, they concede that the problem is a tough nut to crack. In fact, it’s not just hard, it’s Non-deterministic Polynomial-time hard, or “NP-hard.” This is a term from computing theory which basically means that there’s no shortcut to a solution – the only way to solve the equation is to generate random network designs and test them to see if they meet the criteria.

The new paper is a valuable contribution to the ongoing research into charging network planning. However, an article in MIT Technology Review that states that the problem “can now be crossed off the list,” may be a little premature. The article also highlights a misconception about EVs, which is the idea that charging is like filling up at a gas station. It’s not, and any analysis that starts by assuming that every EV driver is going to plan on stopping for a fill-up at a public charging station every 100 miles may come to dubious conclusions.

Today’s EVs simply aren’t designed to make long journeys as ICE vehicles can (with the possible exception of Tesla’s Model S, with over 200 miles of range and a network of proprietary fast charging stations), and people who regularly need to make long journeys simply aren’t going to buy them. Pure EVs are being bought as second cars, or by drivers who have appropriate commutes.

Another factor that can’t be ignored is that the technology of batteries and charging is in its infancy, and researchers are working hard to improve it. The next generation of batteries already exists in the lab, and is sure to find its way into production vehicles within a few years. Advances in charging speed and wireless charging will also change the equation. Any analysis based on today’s vehicle ranges and charging times is bound to be dated within the decade.


Image: WSDOT/Flickr
Source: MIT Technology Review