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

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.

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.

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. 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.

Optimization and Decomposition

The multi-stage SMPC problem is formulated as a sequence of nested two-stage subproblems, with a master problem (MP) coordinating the solution process by integrating Benders cuts derived from the duals of the subproblems The NBD procedure is executed in a forward–backward iterative scheme, commonly referred to as fastforward–fast-back sequencing The master problem inherits all structural constraints from the SMPC formulation, including flow conservation, imbalance dynamics, charger capacity, and non-anticipativity. The problem is nearly totally unimodular (TU), but two constraints break TU, necessitating explicit integrality on variables like x p i j b t.

Performance and Results

Simulation results in San Francisco and Chicago demonstrate significant improvements over deterministic, reactive, and robust baselines Compared with baseline methods, the combined stochastic and robust approach reduces median passenger waiting times by up to 36% and 95th-percentile delays by nearly 20%, while also lowering rebalancing distance by 27% and electricity costs by more than 35%. The Bayesian Neural Field forecasting model was shown to outperform established baselines in both point accuracy and calibrated uncertainty quantification For instance, in Chicago, the SMPC achieves the lowest passenger delays compared to DMP (Deterministic Mean Prediction Optimization).

Sensitivity Analysis Insights

A sensitivity analysis of battery size and vehicle energy efficiency reveals that for energy-efficient vehicles like Vehicle 1, wait times remain nearly constant across all battery sizes, indicating that Vehicle 1’s service quality is not constrained by battery size. Conversely, less efficient vehicles (Vehicle 3) are highly sensitive to battery capacity, with a larger battery significantly mitigating severe delays and reducing the number of trips exceeding 600 s. The analysis also shows that for V2G services, Vehicle 1 is the most attractive option because its lower consumption leaves more capacity for grid interaction.

This paper provides a scalable and computationally tractable pathway for integrating predictive uncertainty modeling and energy-aware fleet control in next-generation autonomous mobility systems. The framework's key methodological contribution is the tailored Nested Benders Decomposition algorithm, which exploits the scenario tree structure to solve large-scale multi-stage mixed-integer problems with temporally correlated uncertainties. Future research may explore scenario tree construction based on the nested distance [30] and alternative approaches to the terminal cost formulation. The proposed framework provides a scalable and computationally tractable pathway for integrating predictive uncertainty modeling and energy-aware fleet control in next-generation autonomous mobility systems.

--- Page 1 ---

Highlights

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

Sten Elling Tingstad Jacobsen, Balázs Kulcsár, Anders Lindman

• Stochastic and robust control model manages demand, energy, time, and charging uncertainties

• Bayesian neural networks generate multivariate travel and charging demand scenarios

• Scenario reduction via soft clustering preserves key patterns of future uncertainty

• Tailored Nested Benders decomposition efficiently solves the large-scale MILP model

• Simulation results show reduced costs and improved reliability over baseline methods

--- Page 2 ---

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

Decomposition

Sten Elling Tingstad Jacobsena,b,∗,1, Balázs Kulcsára and Anders Lindmanb aDepartment of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden bVolvo Cars, Gothenburg, Sweden A R T I C L E I N F O Keywords: Nested Benders decomposition electric autonomous mobility-on-demand Bayesian neural networks scenario tree scenario reduction charging scheduling connected and autonomous vehicles A B S T R A C T The electrification and automation of mobility are reshaping how cities operate on-demand transport systems. Managing Electric Autonomous Mobility-on-Demand (EAMoD) fleets effectively requires coordinating dispatch, rebalancing, and charging decisions under multiple uncertainties, including travel demand, travel time, energy consumption, and charger availability We address this challenge with a combined stochastic and robust model predictive control (MPC) framework The framework integrates spatio-temporal Bayesian neural network forecasts with a multi-stage stochastic optimization model, formulated as a large-scale mixed-integer linear program To ensure real-time applicability, we develop a tailored Nested Benders Decomposition that exploits the scenario tree structure and enables efficient parallelized solution Stochastic optimization is employed to anticipate demand and infrastructure variability, while robust constraints on energy consumption and travel times safeguard feasibility under worst-case realizations We evaluate the framework using high-fidelity simulations of San Francisco and Chicago Compared with deterministic, reactive, and robust baselines, the combined stochastic and robust approach reduces median passenger waiting times by up to 36% and 95th-percentile delays by nearly 20%, while also lowering rebalancing distance by 27% and electricity costs by more than 35% We also conduct a sensitivity analysis of battery size and vehicle efficiency, finding that energy-efficient vehicles maintain stable performance even with small batteries, whereas less efficient vehicles require larger batteries and greater infrastructure support

--- Page 3 ---

Stochastic and Robust Optimization for EAMoD vehicle allocation without considering the complexities introduced by electric vehicles, such as limited battery range and charging infrastructure constraints [7] Those that incorporate charging often treat it separately from dispatch and rebalancing, or rely on deterministic forecasts that fail to account for the full range of future uncertainty [8, 9].

1. Begin optimizing Electric Autonomous Mobility-on-Demand (EAMoD) fleets by jointly optimizing dispatch, rebalancing, charging, and vehicle-to-grid (V2G) operations under four uncertainties: travel demand, charger availability, energy consumption, and travel time. This unified formulation ensures that decisions are made considering both predictive control and worst-case feasibility guarantees.

2. Implement a Bayesian Neural Network (BNN) based probabilistic forecasting pipeline to generate calibrated distributions for travel demand and charger availability, capturing both spatial and temporal correlations in the data. These forecasts form the basis for a scenario tree, which is then reduced using soft k-means clustering to maintain computational tractability while preserving key uncertainty patterns.

3. Employ a tailored Nested Benders Decomposition (NBD) algorithm that exploits the scenario tree structure to efficiently solve large-scale mixed-integer linear programs (MILPs) in real time. This decomposition enables parallelized solution of subproblems, making the optimization applicable for dynamic, receding horizon control in EAMoD systems.

4. Integrate robust chance constraints on energy consumption and travel time into the model parameters to safeguard feasibility under worst-case realizations. This ensures that operational constraints are met with high probability (e.g., 1 - epsilon t), providing a level of reliability beyond purely deterministic models.

5. Use adaptive terminal cost parameterization based on day-ahead electricity prices to dynamically adjust the terminal cost during receding horizon iterations. This allows the system to coordinate charging schedules over daily time scales by incentivizing immediate charging when future electricity prices are expected to rise and deferring charging when they are expected to fall.

6. Develop an energy consumption estimation module within the simulation environment that uses detailed speed profiles to estimate energy usage, which is then used in the flow conservation constraints. This ensures the model accurately reflects real-world driving conditions and operational costs during high-fidelity simulations like San Francisco and Chicago case studies.

7. Incorporate a sensitivity analysis framework investigating battery size and vehicle efficiency to guide fleet design. This analysis reveals that energy-efficient vehicles can maintain stable performance with smaller batteries, while less efficient vehicles require larger batteries to achieve acceptable service quality, informing both vehicle selection and infrastructure planning.