Source-linked AI summary
Optimal Charging of an Electric Vehicle using a Markov Decision Process
Emil B. Iversen, Juan M. Morales, Henrik Madsen
TL;DR
The paper addresses charging policies that overlook stochastic driving patterns and may not preserve vehicle readiness. It fits an inhomogeneous Markov model to vehicle-use data and embeds it in a stochastic dynamic-programming charging algorithm. The resulting strategy significantly reduces vehicle-running costs, can achieve net profit with vehicle-to-grid operation, and is adaptable to specific vehicles.
Problem
Existing charging models often use deterministic driving patterns or aggregate users, while stochastic driving behavior and its effect on charging remain insufficiently addressed.
Method
The paper fits transition probabilities from vehicle-use observations and uses an inhomogeneous Markov model within a recursively solved stochastic dynamic-programming charging algorithm.
Results
Vehicle-running costs decrease significantly with the proposed optimization, and vehicle-to-grid operation can enable a net profit.
Takeaways & Limitations
The versatile model can be adapted to specific vehicles to provide customized charging policies with little or no end-user inconvenience.
Takeaways & Limitations
The approach is constrained by limited observations available for estimating the model and by deterministic patterns’ inability to capture daily variation and readiness conflicts.
Abstract
from arXiv · showhide
The combination of electric vehicles (EVs) and renewable energy is taking shape as a potential driver for a future free of fossil fuels. However, the efficient management of the EV fleet is not exempt from challenges. It calls for the involvement of all actors directly or indirectly related to the energy and transportation sectors, ranging from governments, automakers and transmission system operators, to the ultimate beneficiary of the change: the end-user. An EV is primarily to be used to satisfy driving needs, and accordingly charging policies must be designed primarily for this purpose. The charging models presented in the technical literature, however, overlook the stochastic nature of driving patterns. Here we introduce an efficient stochastic dynamic programming model to optimally charge an EV while accounting for the uncertainty inherent to its use. With this aim in mind, driving patterns are described by an inhomogeneous Markov model that is fitted using data collected from the utilization of an EV. We show that the randomness intrinsic to driving needs has a substantial impact on the charging strategy to be implemented.
1. Introduction
EV charging must balance renewable-energy uncertainty with the need to keep vehicles ready for travel. Existing approaches often simplify or aggregate driving behavior, motivating a stochastic, vehicle-specific charging policy based on Markov decision processes.
- Motivation: Renewable generation is uncertain in time and quantity, while limited large-scale storage can leave renewable energy unused.This creates a charging-management challenge for EVs connected to renewable-heavy energy systems.
- Research gap: Existing literature commonly uses deterministic single-vehicle patterns or aggregates users into fleets, obscuring each vehicle’s dynamics.Aggregation loses vehicle-specific behavior, while deterministic patterns simplify individual use.
- Research gap: Stochastic driving models are needed to represent daily use variation and possible conflicts when the vehicle is not charged and ready.The paper notes that stochastic modeling has received limited attention and is important for real-world charging schemes.
- Motivation: EV batteries should primarily support driving needs, so charging must preserve enough energy for desired trips.The decision tool must determine when charging can be postponed and when immediate charging is necessary.
- Approach: The proposed algorithm combines an inhomogeneous Markov model fitted to vehicle-use data with recursively solved stochastic dynamic programming.The resulting decision-support tool addresses charging, V2G, vehicle availability, and operating costs, and is designed for practical implementation.
2. A Stochastic Model for Driving Patterns
The paper models EV driving patterns as an inhomogeneous Markov process whose time-varying transition probabilities are fitted from observed vehicle-use data. Hidden states and B-spline smoothing address limited observability, parameter growth, and irregular trip-duration patterns.
- Markov model: The simplest model uses two states—driving and not driving—while richer models can represent parking location, speed, or trip type.The number of states can therefore be expanded beyond the basic driving-status representation.
- Markov model: Driving use is represented with a finite-state Markov model whose transition probabilities vary with minute s in the daily cycle.Weekdays are assumed to share transition probabilities, an assumption the authors state can be relaxed.
- Parameter fitting: B-splines within a generalized linear model capture diurnal variation while reducing parameters and addressing undefined estimates.Transition counts are treated as binomial, with logistic regression using B-spline basis functions; knots are added where likelihood fit is poorest and retained while significantly improving fit.
- Hidden Markov models: Hidden Markov models add unobserved states so observable-state waiting times can match empirical durations more flexibly than exponential waiting times.This addresses the restriction that standard Markov models represent only observed states and may impose unrealistic waiting-time behavior.
- Observed driving patterns: Weekday trip starts show strong diurnal variation, with peaks around 06:00 and 16:00 and no observed starts between 00:00 and 05:00.The fitted hidden Markov model adequately captures the empirical trip-length distribution, although 10–20-minute trips are more prevalent in the observations.
3. A Stochastic Dynamic Programming Problem
The paper formulates EV charging as a stochastic dynamic programming problem that balances charging costs against the need to keep the vehicle available for driving. An inhomogeneous Markov driving model, battery-state dynamics, feasibility constraints, and recursive optimization together produce a policy conditioned on time, driving state, and battery state.
- Problem formulation: EV charging balances minimizing operating costs against keeping the vehicle charged and available for desired trips.Time-varying electricity prices can make postponing charging beneficial, while immediate charging maximizes availability.
- Problem formulation: The charging problem is formulated as a stochastic dynamic program with defined parameters, state transitions, and an objective function.The formulation includes charging-rate and storage limits, efficiency losses, electricity prices, and penalties for unserved driving needs.
- State and action modeling: The state at time t combines battery energy e_t with an exogenously evolving desired driving state x_t from an inhomogeneous Markov model.The actual driving state differs from the desired state when insufficient battery charge prevents the desired trip.
- State and action modeling: The actual charging variable is zero while the vehicle is driving and otherwise equals the desired charging action.This auxiliary variable enforces the restriction that the vehicle cannot charge while in use.
- State transition: The battery transition updates e_{t+1} using current stored energy, net charging or discharging, and energy consumed according to the random driving state.Equation (10) describes the energy dynamics, with the actual driving and charging variables determined by the state and action.
- Solution algorithm: The optimal policy is obtained by recursively solving the Markov decision process over feasible actions and states.The discretized policy specifies when and how much to charge as a function of time and the pair of driving and battery states.
4. Results and Discussion
The stochastic charging model is evaluated with realistic parameters, comparing optimal policies with rule-of-thumb strategies and examining charging-only, rolling-horizon, and V2G settings. Results show that policies respond to driving probabilities, electricity prices, battery charge, and penalty values, while V2G improves cost performance but can compromise driving readiness.
- Charging-only policies: At 5% charge, the policy almost always charges except when driving probability is low and electricity prices are particularly high.At higher charge levels, charging becomes increasingly selective: at 50% it occurs mainly at comparatively low prices, and at 95% only at expected price minima.
- Rolling-horizon implementation: Rolling-horizon and fixed-horizon policies differ little during the first day, but discrepancies increase near the end of the 48-hour horizon because of the terminal condition.Re-optimizing every hour in a rolling horizon can reduce, or potentially eliminate, this terminal-condition effect.
- Penalty effects: Higher penalties produce higher battery charge under the same driving realization, reflecting greater protection against insufficient charge.The penalty parameter therefore changes the resulting charge trajectory even when the driving pattern is held fixed.
- Vehicle-to-grid schemes: V2G policies use high-price periods for discharging and low-price periods for charging, exploiting battery capacity but sometimes depleting the battery below driving needs.The policy weighs the cost of running out of charge against gains from delaying charging or supplying power at high prices.
- Charging-only policies: Minute-level decisions exploit hourly price changes by switching briefly between charging and not charging when price movements are large.The model combines time-varying trip probabilities with electricity prices when selecting actions.
- Out-of-sample performance: V2G substantially reduced driving costs and could produce negative average costs, but unconstrained discharging caused multiple out-of-battery events.Adding a lower discharge bound removed those events while considerably increasing running costs, nearly doubling them.
5. Conclusion
The paper presents a stochastic dynamic programming model that uses an inhomogeneous Markov model to produce customized EV charging policies. The strategy significantly reduces vehicle-running costs with little or no inconvenience, and vehicle-to-grid operation may enable net profit.
- The model combines stochastic dynamic programming with a hidden Markov chain describing stochastic vehicle use to determine charging policies.
- Charging costs associated with running the vehicle decrease significantly under the proposed optimization model, with little or no inconvenience to the end-user.
- Permitting the vehicle to supply power to the grid can reduce costs further and may produce a net profit.
- The model is versatile and can be adapted to a specific vehicle, providing a customized charging policy.
- Future extensions include more Markov states, adaptively estimated transition probabilities, fleet modeling, and analysis of EV interactions with renewable energy.
- EVs could potentially shift excess renewable production to periods of high demand, possibly improving the economic competitiveness of renewables.