Operations Research for the SmartGrid - 2: Optimization Problems

In this sequel to part-1,  an overview of a few, specific optimization models employed within three different Smart-Grid areas is provided. I found these samples to be interesting from a practitioner's perspective. INFORMS publishes a lot of good papers in these areas, and is an excellent source of references.

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 fulfilled 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 difficulty of an efficient charging control mainly comes from the uncertainty of each EV’s charging profile. 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 offline 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.

Demand Response and Pricing
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.

Smart-Grid Control
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.

Time-constrained Technical Talks

Just jotting down some thoughts while attending the IEEE SmartGridComm conference in Vancouver, Canada. The talk duration here is roughly the same as that at INFORMS, about 20 minutes. There were plenty of talks on EVs (electric vehicles) in terms of their impact on the grid, locating charging stations, charging strategies, etc. I blogged about the Tesla routing problem - a very simple treatment purely out of curiosity - Smart-grid researchers have taken a variety of such EV related optimization problems to much more sophisticated levels. The most interesting feature of this SGComm edition was the introduction of 'Lightning Talks' of five minutes duration at lunch time, buzzer controlled. Given my extremely limited background in power systems and electrical engineering, I attended these five-minute talks for the novelty factor, and betting that nobody would present anything too complicated in five minutes. Of the 8 talks, 2 finished 1-2 minutes ahead of time, 2 were buzzer-beaters (nice!), and 4 violated the time-limit.So 50% of the time, the knapsack constraint was satisfied (half of that, tightly).

INFORMS may consider adding this feature in their next edition. After all, 'the elevator pitch' is an important part of OR soft skills. The talks were quite informative and the talkers cut to the chase and spend their scarce resource (time) trying to convey the one or two key ideas rather than to walk through excruciating technical details. The best talk was by Naeem, a researcher originally from Tanzania (where 97% of the villages have no electricity), who, in five-ish minutes, talked about how he came up with a micro-grid solution for villages that used diesel generators to provide electricity for lighting, some Jugaad-type ideas, and using Sim-card based methods for managing payments. Quite brilliant. Here's a link, and be sure to google his work. My fifteen minutes is up.

Solve TRP, Drive Tesla

So the awesome and hyped Tesla Model S is beating Mercedes, BMW, and Audi in sales despite the $70K price tag. One problem is the current lack of charging stations required to recharge over long trips. CNNMoney reports:
"CNNMoney took a Tesla Model S on a test drive from Washington D.C. to Boston. The all-electric car drove 450 miles with two stops to recharge at Tesla's Supercharger stations in Delaware and Connecticut"



A second problem is that unlike conventional gasoline cars that can be refueled very quickly, charging can take a relatively long time, and adds significantly to your total travel time. In the near future, as the number of Teslas increase, the number of charging stations is likely to go up too. However, it will remain a sparse resource for some time. A future Tesla trip from New York to California will require many recharging stops, reminiscent of the old stagecoach problem during the Gold Rush era, which is used to illustrate the principles of Dynamic Programming.

Update: May30, 2013
Popular Mechanics reports:
"...the California-based EV automaker plans to expand its fast-charging "supercharger" network across the continental U.S. During today's announcement, Musk said New York to Los Angeles trips would be viable as soon as this winter. 

"When you get in a car you have the ability to go almost anywhere," Musk said. "That's what the supercharger network will do." 

The rollout will begin as soon as this summer, with the number of stations tripling to 27 nationwide by the end of June. In addition to increasing supercharger density along the already-established California and Mid-Atlantic coasts, Tesla will debut chargers in a handful of new metropolitan areas within the next few weeks, including Austin/Houston, Portland/Seattle, Boulder/Denver, and Chicago/Milwaukee. By the end of the year, Musk expects to to have "a couple hundred" superchargers spread across the U.S. and southern Canada, with as little as 80 to 90 miles between stations along the Altantic and Pacific coasts..."

Tesla Routing Problem
Given a road network G having a limited number of charging stations located at specific nodes, the Tesla Routing Problem (TRP) will have to:
Find the shortest feasible time path from origin O to Destination D in network G.

Feasibility requires the car to visit enough charging stations in a timely manner. Optimality requires that the sequence of visits be carefully selected such that the total time spent is kept to a minimum.

Total travel time = driving time + recharge time

This involves two decisions:
D1. Which recharging stations to visit en-route?
D2. How long to recharge at every pit stop?

Assumptions:
A1. The longer you recharge, the longer your available range (to a limit).
A2. All recharging stations are similar, and infinite capacity (no queuing!)
A3. Range is deterministic

Update on A2: The Tesla can charge on any outlet, but the time to recharge can vary depending on the source.

Clearly, optimally solving TRP involves the finding a solution to a Traveling Salesman Problem even in the special case of instantaneous recharge (Y=0).

(Updated September 2013: As mentioned in the comments, the general case is not a TSP in the network of charging stations. Here, the assumption is that stations are sparsely located and we visit each one along the way. The title is changed to reflect this distinction).

This is no different from the (milder) challenge faced by conventional car drivers in unfamiliar areas where gas stations may be hard to come by (see this old post). Charge cannot be carried in Jerry-cans. The  shortage of charging stations does make every long Tesla trip a non-trivial problem to manage. Tesla owners have to deal with a NP-Hard Optimization Problem (Heh) on every such trip, but in practice, it should not be difficult to find good quality, feasible TRP solutions.

The recharge time makes the TRP a bit more interesting. If two stations are close to each other, we don't have to recharge fully, and just need the minimum to reach the next stop - or perhaps we recharge fully, which allows us to reach a station that is further away but turns out to be more time-effective, overall. Clearly, these two decisions appear to be interlinked and may need to be jointly optimized. D1 is a binary decision variable X(i) - we either visit or don't visit a station at node X(i), whereas D2 is a semi-continuous variable Y(i) conditional on D1:

Y(i) ≤ U.X(i)
where U = maximum recharge time.

Another interesting and maybe even useful problem for Tesla-makers to solve is where to add new charging stations on the network G over time. What is the minimum number and location of stations required to guarantee feasible solutions to any TRP in the 48 states of continental US? How will stations deal with congestion in the future? and so on ...

I haven't driven a Tesla yet but I wouldn't mind relocating my office to inside one and telecommute.