Managing Electric-Vehicle (EV) Charging within a Smart-Grid
EV System Perspective:
EV problems are fun. Researchers in Hong Kong have investigated efficient online charging algorithms for EVs without future information, where EV charging is coordinated to minimize total energy cost. EVs arrive at the charging station randomly, with random charging demands that must be fulﬁlled before their departure time. Suppose that N EVs arrive during a time period T, indexed from 1 to N according to their arrival order. The optimal charging scheduling problem minimizes a total (convex) generation cost over time T, by determining the best charging rate for EV i at time t, x(i, t), subject to various constraints.
The difﬁculty of an efﬁcient charging control mainly comes from the uncertainty of each EV’s charging proﬁle. Prior approaches assume that the arrival time and charging demand of an EV is assumed to be known to the charging station prior to its arrival. However, the HK team have come up with an optimal online charging algorithm that schedules EV charging based only on the information of EVs that have already arrived at the charging station. They show that their approach results in less than 14% extra cost more an optimal ofﬂine algorithm, which can be potentially reduced even further.
EV User Perspective
Cool routing algorithms can also be developed from a user-perspective. One interesting work I came across takes a more holistic and rigorous view of the simple Tesla routing problem that I blogged out a while ago. Researchers in Europe look at a routing subproblem within the more general context of managing congestion at EV charging stations and minimizing the impact of EVs on grid performance. They employ an algorithm to compute the best charging points to visit to based on the estimated travel time (shortest-path, and reachability based on available battery power) to all charging points, and the point-specific charging cost. Input: O-D locations, initial battery level, desired charging level for the EV user, and the preferred time of departure. The optimal route, the subset of intermediate charging points, and the slot that the EV is going to charge at, are returned as output.
Revenue Management and supply chain analytics folks will be pretty familiar with this area. Smart-devices can be programmed to automatically (with human overrides) respond to price changes by reducing or rescheduling electricity usage. Couple of differences here from standard RM/SCM problems : i) unlike supply chains that process manufactured widgets through warehouses and distribution centers, it is quite difficult to efficiently store and "ship" electricity using batteries, although the technologies are getting better each day. Thus, the electricity we use is probably produced less than a second ago, and marginal costs can spike during peak periods ii) electricity tends to be incredibly inelastic, making it stubbornly resistant to pricing changes, unlike say, smart-phones.
We noticed that prior approaches that apply peak-hour "congestion" pricing tended to 'migrate' rather than mitigate peaks. By carefully combining peak and off-peak pricing with accurate short-term load forecasting, and jointly optimizing the entire price profile, it is possible to proactively flatten the overall predicted load profile by inducing customers to make small shifts in their usage. Even a small peak shift-reduction during high-load days can result in a lot of savings. In fact, our experiment using actual Smart-Grid data showed that even a half a percentage point peak reduction using optimization could potentially lead to more than a 25% reduction in cost, which can benefit both the customers, as well as the utility companies.
Among the variety of problems solved here, researchers are also looking at the security-constrained optimal power flow that aims to minimize the total cost of system operation while satisfying certain contingency constraints.This smart-grid formulation extends the standard optimal power flow (OPF) problem, which determines a cost-minimal generation schedule cost while satisfying hourly demands, as well as energy and environmental limits, and meeting network security goals. Optimization methods used here include Benders decomposition, as well as Lagrangian multiplier techniques. Some of the newer variations employ distributed algorithms that are designed to work on a massive scale.
These are just a few samples that caught my attention. There are a variety of other problem areas being addressed (e.g. batteries, renewable energy sources, micro-grids), all of which perform some type of an optimization.