Researchers Mobina Nankali and Michael W. Levin, affiliated with the Massachusetts Institute of Technology, have developed a novel approach to optimize the placement of electric vehicle (EV) charging stations. Their work, published in the journal Operations Research, addresses a critical challenge for the energy and transportation sectors as the world shifts towards electrified mobility.
The team tackled the problem using a bi-level optimization model. At the upper level, planners aim to maximize net revenue by selecting charging station locations within budget constraints. Meanwhile, at the lower level, EV users choose routes and charging stations to minimize their travel and charging costs. To account for “range anxiety”—the fear of running out of power before reaching a destination—the researchers constructed a “battery-expanded network” and applied a shortest path algorithm with Frank-Wolfe traffic assignment.
The primary contribution of this research is the development of the first exact solution algorithm for large-scale EV charging station placement problems. The researchers propose a Branch-and-Price-and-Cut algorithm, enhanced with value function cuts and column generation. This method delivers globally optimal solutions with mathematical certainty and within a reasonable runtime. Existing research often relies on heuristic methods that lack optimality guarantees or exact algorithms that take prohibitively long to run. The new algorithm achieves optimality gaps below 1% across all tested instances and terminates within minutes, rather than hours, representing a computational speedup of over two orders of magnitude compared to existing methods.
The algorithm was tested on three real-world networks: Eastern Massachusetts (74 nodes, 248 links), Anaheim (416 nodes, 914 links), and Barcelona (110 zones, 1,020 nodes, and 2,512 links). It successfully handled problems with over 300,000 feasible combinations, transforming EV charging infrastructure planning from a computationally prohibitive task into a tractable optimization problem suitable for practical decision-making.
For the energy sector, this research offers a powerful tool for optimizing the placement of EV charging stations. By providing a method to determine the most cost-effective and user-friendly locations for charging infrastructure, the algorithm can help accelerate the adoption of electric vehicles and support the transition to a low-carbon transportation system. The practical applications of this research extend to urban planners, energy providers, and policymakers seeking to design efficient and sustainable charging networks.
The research was published in Operations Research, a leading journal in the field of operations research and management science.
This article is based on research available at arXiv.