Combined Stochastic and Robust Optimization for Electric Autonomous Mobility-on-Demand with Nested Benders Decomposition

summary

Video file (mp4)

The gist

The gist: A combined stochastic and robust model predictive control framework for electric autonomous mobility-on-demand (EAMoD) systems jointly optimizes dispatch, rebalancing, charging, and V2G

In short

The research developed a combined stochastic and robust model predictive control framework for Electric Autonomous Mobility-on-Demand (EAMoD) fleets. It uses Bayesian neural network forecasts to predict travel demand and charger availability, then solves a large mixed-integer linear program using a tailored Nested Benders Decomposition to optimize dispatch, rebalancing, and charging decisions under uncertainty. Results show significant improvements in passenger waiting times, reduced rebalancing distance, and lower electricity costs compared to existing methods.

Key concepts

Bayesian Neural Networks (BNNs)
These are AI models used to create probabilistic forecasts for travel demand and charger availability. They are powerful because they don't just give one answer; they provide a range of likely outcomes, helping the system understand the uncertainty in future conditions across different locations and times.
Nested Benders Decomposition (NBD)
This is a specialized mathematical technique used to solve very large optimization problems efficiently. It breaks down the complex problem into smaller, manageable parts that are solved iteratively. This method is particularly effective for handling the specific structure of the scenario tree generated by the forecasting models.
Stochastic and Robust Optimization
This approach combines two methods: stochastic optimization anticipates uncertainty (like demand variability) using probability distributions, while robust optimization ensures solutions remain feasible even in the worst-case scenarios (like extreme travel times or energy consumption). This dual approach makes the control system reliable.
Scenario Tree and Reduction
A scenario tree maps out all possible future combinations of uncertain events (demand, chargers) over time. Since this tree can be too large, a clustering technique is used to reduce it to representative scenarios that capture the most important patterns of uncertainty without losing critical information.

Terminology used across episodes

This episode discusses

The paper

Combined Stochastic and Robust Optimization for Electric Autonomous Mobility-on-Demand with Nested Benders Decomposition · Read on arXiv

Sten Elling Tingstad Jacobsen, Balžs Kulcsır, Anders Lindman

Department of Electrical Engineering, Chalmers University of Technology · Volvo Cars

DOI: 10.1016/j.trc.2026.105903

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: We're looking at the paper: "Combined Stochastic and Robust Optimization for Electric Autonomous Mobility-on-Demand with Nested Benders Decomposition".

Dev: Here's the gist of the paper. The gist: A combined stochastic and robust model predictive control framework for electric autonomous mobility-on-demand (EAMoD) systems jointly optimizes dispatch, rebalancing, charging, and V2G decisions under multiple uncertainties.

Rosa: Framework Overview The proposed framework integrates spatio-temporal Bayesian neural network forecasts with a multi-stage stochastic optimization model formulated as a large-scale mixed-integer linear program The framework uses Bayesian Neural Networks (BNNs) to produce calibrated probabilistic forecasts of travel demand and charger availability, capturing both spatial and temporal correlations These forecasts are used to generate a multi-stage scenario tree, which is then reduced using a clustering-based technique that efficiently handles multiple sources of uncertainty The resulting large-scale Mixed-Integer Linear Program (MILP) is solved using a tailored Nested Benders Decomposition (NBD) algorithm that exploits the scenario tree structure and enables parallelized computation.

Dev: Uncertainty Modeling and Scenario Reduction The system addresses four sources of uncertainty: travel demand, charger availability, energy consumption, and travel time Travel demand and charger availability are modeled by a scenario tree that encodes multiple realizations of the random variables and their evolution over time The uncertainty in energy consumption and travel time is handled through chance-constrained parameterization of the model parameters, ensuring operational feasibility with high probability.

Rosa: To handle the complexity of scenario trees, a clustering-based technique is employed to reduce the number of scenarios, preserving key patterns of future uncertainty The method involves sampling future values conditionally using the predictive model and applying soft k-means clustering to obtain representative centroids for each time stage.

Paper summary: Dev: Basically, the authors tackle this challenge with a combined stochastic and robust model predictive control MPC framework. It integrates spatio-temporal Bayesian neural network forecasts with a multi-stage stochastic optimization model that's formulated as a large-scale mixed-integer linear program. Rosa That means they use these neural network forecasts to build a scenario tree, and then they use that tree to run the optimization. Dev And because it’s so big, they use a tailored Nested Benders Decomposition algorithm to make sure it can actually run in real time.

Taro: So the thesis is using these Bayesian neural networks for forecasts of travel demand and charger availability, while robust constraints on energy consumption and travel times keep things feasible under the worst-case realizations. Rosa That’s a lot of uncertainty they're trying to handle at once, right? Dev Right. The scenario modeling part is interesting because constructing reduced scenario trees that faithfully represent multivariate, temporally correlated uncertainties remains computationally demanding and most existing reduction techniques are limited to single sources of uncertainty or don't preserve the filtration structure of the stochastic process <ref:2508.19933#pg3>.

Taro: They address that by using a clustering-based technique to reduce those scenarios, which they say preserves key patterns of future uncertainty <ref:2508.19933#pg3>. Rosa And then the optimization itself is formulated as a sequence of nested two-stage subproblems with a master problem coordinating the solution process via Benders cuts <ref:2508.19933#pg2>. Dev That nested structure is what makes it computationally tractable for real-time operations, which they say is the major challenge when dealing with temporal dependencies in EAMoD applications <ref:2508.19933#pg3>.

Rosa: So the overall claim of this paper is that this combined approach offers a way to anticipate demand and infrastructure variability while ensuring operational feasibility under those worst-case scenarios <ref:2508.19933#pg2>. Dev And they test this using high-fidelity simulations in San Francisco and Chicago <ref:2508.19933#pg1>.

Conclusion: Rosa: So, looking at the full paper "Combined Stochastic and Robust Optimization for Electric Autonomous Mobility-on-Demand with Nested Benders Decomposition" by Jacobsen, Kulcsár, and Lindman, the main thing to grasp is how they combine predictive control with uncertainty modeling. Dev They show that this combined stochastic and robust approach reduces median passenger waiting times by up to thirty-six percent <ref:2508.19933#pg1> and 95th-percentile delays by nearly twenty percent <ref:2508.19933#pg1>.

Taro: Plus, they also lower rebalancing distance by twenty-seven percent <ref:2508.19933#pg1> and electricity costs by more than thirty-five percent <ref:2508.19933#pg1>. Rosa That’s a lot of tangible improvement over the deterministic, reactive, and robust baselines they compared it against <ref:2508.19933#pg1>. Dev And their sensitivity analysis on battery size and vehicle efficiency showed something specific about different vehicle types <ref:2508.19933#pg1>.

Dev: They found that for energy-efficient vehicles, like Vehicle one wait times stay stable even with small batteries <ref:2508.19933#pg1>. But for less efficient vehicles, Vehicle three they need larger batteries and more infrastructure support to keep delays down <ref:2508.19933#pg1>. Rosa So what this means for the world is that it emphasizes the importance of jointly optimizing predictive control, vehicle capabilities, and infrastructure planning for scalable operations <ref:2508.19933#pg1>. Taro It gives us a computationally tractable pathway to integrate predictive uncertainty modeling and energy-aware fleet control in next-generation autonomous mobility systems <ref:2508.19933#pg1>.

More episodes

← Home