Call (+1) 650-212-1212

Blog

Electric Vehicle Charging Scheduling and Station Location via Operations Research

Sean Salleh 05 Nov 2013 Analytics and OR, Case studies and applications, Modeling methods

Like the rebirth of 90’s fashion in a Web 2.0 world, the electric vehicle is back and more beautiful, in the form of the Tesla Model S and the Chevy Volt, among others. Both supply and demand in this market are growing, and web technology companies are responding with charging station locators like PlugShare and CarStations. However, as of yet there is no city in which this supply and demand are harmonious on a large scale, and charging is still time-consuming. So, how can we practically manage rising consumer demand to charge vehicles given a limited supply of stations? This is largely a system design problem to be solved, and naturally, Operations Research leads the way.

Individual Service Optimization

Arriving at your favorite café after minutes of driving, you recall that your electric vehicle (EV) needs charging. A couple swipes later on your smartphone, you can select a station from several in your locale as shown from the PlugShare app below.

 

Original PlugShare image by Lumina

 

You might be wondering if there is an app that recommends the best station for you to go to based on your predicted total waiting time, which is the time for you to reach the station plus the time needed to charge your car. Maybe it’s too early for these apps to have such a feature, let alone consider the charge cost. But be bold with analytics, I say! Imagine the extra incentive for potential EV customers if cities can guarantee that EVs can be charged nearby with no line 90% of the time. You could then be confident that there is an open spot.

 

General Electric

 

Service Optimization in a System

With a city of EVs roaming about, our interest encompasses more than the individual experience. A decision engine should recommend the best station for each EV to go to that is both good for the individual and the system as a whole. This was addressed theoretically by computer scientists, Hua Qin and Wensheng Zhang, from Iowa State University in their 2011 paper. They assume a practical setting where stations communicate with each other, and each station communicates with nearby EVs via Wi-Fi. Several tools from Operations Research are then applied to find a good schedule for all EVs to be charged as they travel to their destinations. The conceptual problem is

 

Scheduling

The researchers used a network to model the stations and the possible paths of the EVs. In a prior blog, I showed a network model applied to workforce analysis. Back to EVs, Qin and Zhang used queuing concepts to model supply and demand and simulation to justify the goodness of their heuristic algorithms. Although the original problem assumes centralized decision-making, it’s interesting that the heuristic allows for distributed decisions, which is more practical.

Service and Location Optimization in a System

The previous problem assumed that station locations were given. It is more general, albeit more complicated, to solve the problem where the station locations are to be determined while providing good service to a changing number of EVs in a system. This is more realistic and was explored by European scientists in a 2012 paper. Unlike the 2011 research, the 2012 study sought to minimize the average waiting time per EV and considered numerous possible station locations. This renders formulating the problem as a nonlinear binary integer program; it is nonlinear partly because of the average waiting time function and binary because there is a yes/no decision to be made for each possible station location. This problem is very hard, and so the researchers applied a genetic programming approach to find good solutions to the problem.

Thoughts

Whether it be optimizing for charging service or inclusively finding optimal station locations, Operations Research methods and good modeling software ensure a path to good system design for EVs. Lumina Decision System’s Analytica platform meets these needs for various optimization and simulation. Within the EV market, what other data and analytics issues do you think should be addressed? Besides the EV market, what related system design problems do you think we should solve?

» Back

Sean Salleh

Sean Salleh is a data scientist with experience in guiding marketing strategy from building marketing mix models, forecasting models, scenario planning models, and algorithms. He is passionate about consumer technologies and resource management. He has master's degrees in Operations Research from University of California Irvine and Mathematics from Northeastern University.

Leave a Comment