Source-linked AI summary
Data-Driven Model Predictive Control of Autonomous Mobility-on-Demand Systems
Ramon Iglesias, Federico Rossi, Kevin Wang, David Hallac, Jure Leskovec, Marco Pavone
TL;DR
AMoD operators must address vehicle imbalance under changing, asymmetric demand, while most existing strategies do not use demand forecasts. The paper develops a time-expanded network-flow model and forecast-driven MPC controller, validating them with DiDi Chuxing data. The MPC approach scales to large systems and achieves 89.6% shorter mean customer wait times than the Reactive controller.
Problem
Vehicle imbalance reduces availability in some regions, while most existing AMoD control strategies do not leverage forecasts of customer demand.
Method
The paper combines a time-expanded network-flow model for optimal rebalancing and fleet sizing with an MPC algorithm using short-term predicted demand.
Results
89.6% shorter mean customer wait time was achieved by the MPC-LSTM controller than by the Reactive controller on DiDi Chuxing data.
Takeaways & Limitations
Incorporating forecasted demand into rebalancing can yield significant improvements in customer satisfaction while the MPC algorithm scales well to large systems.
Takeaways & Limitations
The MPC controller outperformed the Reactive controller in the presence of a forecast, leaving extensions to additional AMoD aspects as future work.
Abstract
from arXiv · showhide
The goal of this paper is to present an end-to-end, data-driven framework to control Autonomous Mobility-on-Demand systems (AMoD, i.e. fleets of self-driving vehicles). We first model the AMoD system using a time-expanded network, and present a formulation that computes the optimal rebalancing strategy (i.e., preemptive repositioning) and the minimum feasible fleet size for a given travel demand. Then, we adapt this formulation to devise a Model Predictive Control (MPC) algorithm that leverages short-term demand forecasts based on historical data to compute rebalancing strategies. We test the end-to-end performance of this controller with a state-of-the-art LSTM neural network to predict customer demand and real customer data from DiDi Chuxing: we show that this approach scales very well for large systems (indeed, the computational complexity of the MPC algorithm does not depend on the number of customers and of vehicles in the system) and outperforms state-of-the-art rebalancing strategies by reducing the mean customer wait time by up to to 89.6%.
I. INTRODUCTION
AMoD systems combine on-demand mobility services with self-driving fleets, creating an operational imbalance problem that existing reactive strategies handle poorly under rapidly changing demand. The paper proposes predictive, data-driven control using demand forecasts and validates it on real-world DiDi Chuxing data.
- AMoD combines Mobility-on-Demand services with self-driving vehicles to provide on-demand travel through autonomous fleets.
- Vehicle imbalance arises because asymmetric demand concentrates vehicles in some serviced areas, reducing availability elsewhere.
- Most existing operating strategies do not leverage forecasts of customer demand and are therefore predominantly reactive.
- Reactive strategies handle rapidly time-varying demand poorly, including changes associated with commuting cycles, events, or weather phenomena.
- The paper develops an end-to-end predictive control framework that anticipates demand imbalances and rebalances vehicles using predicted customer demand.
- The proposed approaches are validated with real-world DiDi Chuxing data and designed to address large-scale AMoD control.
II. MODEL DESCRIPTION AND PROBLEM FORMULATION
The paper formulates AMoD operations as a time-varying network-flow problem with perfect future-demand information, then uses optimization to determine routing, rebalancing, and fleet requirements. The formulation is feasible for any customer-demand set and efficiently solvable because of total unimodularity.
- II. MODEL DESCRIPTION AND PROBLEM FORMULATION: The model represents AMoD operations with a time-varying network-flow formulation that assumes perfect knowledge of future customer arrivals.
- II. MODEL DESCRIPTION AND PROBLEM FORMULATION: The urban environment is discretized into regions, with discrete time intervals and travel times that may vary by departure time.
- II. MODEL DESCRIPTION AND PROBLEM FORMULATION: Customer demand and passenger-carrying vehicle flows are represented by origin, destination, and departure-time variables.
- II. MODEL DESCRIPTION AND PROBLEM FORMULATION: Empty vehicles are recurrently rebalanced from regions with excess availability to regions with insufficient vehicles, with idling treated as a special rebalancing case.
- II. MODEL DESCRIPTION AND PROBLEM FORMULATION: The optimization may choose initial vehicle locations and the total fleet size needed to serve all customers.
- A. Optimal Rebalancing Strategy: Under perfect demand information and free starting positions, the optimization computes an optimal rebalancing strategy.
- A. Optimal Rebalancing Strategy: The formulation enforces vehicle-flow conservation, first-interval vehicle insertion, nonnegative integer decisions, and customer-service constraints.
- A. Optimal Rebalancing Strategy: Problem (1) is feasible for any customer-demand set, and total unimodularity allows its integer program to be solved efficiently as a linear program.
III. MODEL PREDICTIVE CONTROL
The paper adapts the offline optimal rebalancing problem into an MPC implementation that uses predictions of future demand. It presents the algorithm and then details its components.
- The MPC controller adapts the optimal rebalancing problem to use predictions of future demand for real-time AMoD operation.
- The section first outlines the overall algorithm and then examines the details of each subcomponent.
- The MPC implementation is explicitly based on the optimal rebalancing problem introduced earlier.
A. Algorithm
At each control step, the algorithm observes vehicle availability and outstanding demand, forecasts demand, solves an optimization problem, assigns rebalancing tasks, and repeats after one time interval.
- A. Algorithm: The controller distinguishes a planning horizon from a forecasting horizon, with the forecasting horizon no longer than the planning horizon.
- A. Algorithm: At time t0, the algorithm observes vehicle availabilities and outstanding customer demand before forecasting the next Tforward time steps.
- A. Algorithm: The predicted demand is used to solve a mixed-integer linear program that computes the rebalancing strategy.
- A. Algorithm: The resulting rebalancing tasks are assigned to available vehicles.
- A. Algorithm: The controller recomputes its rebalancing strategy after each period Δt throughout system operation.
B. State observation
The controller first captures current vehicle availability and outstanding passengers, then uses available features and a forecasting model to predict future demand.
- The current state records idling vehicles by region and vehicles still traveling.
- Outstanding travel requests are represented by origin-destination counts for passengers not previously serviced.
- The forecasting model uses features available at prediction time and a specified forward horizon to estimate future customer demand.
- The forecast contains expected demand for each origin-destination pair over the subsequent forecasting time steps.
D. Controller
The controller adapts the offline optimization problem for real-time operation by combining observed state, predicted demand, and outstanding passengers in a rebalancing optimization.
- The controller computes rebalancing routes over a planning horizon using observed system state and predicted customer demand.
- Slack variables allow some predicted customers to remain unserved when fixed vehicle positions make full service infeasible.
- Outstanding customers receive an optimization-based pickup time, with an associated cost proportional to their waiting time.
- The constraint for outstanding demand assigns each origin-destination request across pickup times.
- The objective accounts for rebalancing, waiting, and dropping costs, while continuity and service constraints govern feasible operations.
E. Discussion
The MPC formulation depends on operator-set costs and a sufficiently long planning horizon, and it must be solved as a mixed-integer linear program.
- The operator sets rebalancing, waiting, and dropping costs to reflect real-life costs.
- The relative waiting-versus-dropping costs determine whether the optimizer waits for or drops a customer.
- An excessively short planning horizon can prevent rebalancing vehicles from reaching customers in remote regions.
- The problem is not totally unimodular because of constraint (5d), so it must be solved as a mixed-integer linear program.
IV. NUMERICAL EXPERIMENTS
The experiments evaluate the controller with DiDi Chuxing data, simulated regional operations, and an LSTM model for short-term demand forecasting.
- The evaluation compares the proposed algorithm with an existing rebalancing heuristic using simulations based on DiDi Chuxing data.
- The dataset contains approximately eight million Hangzhou trips requested from January 1 through January 21, 2016.
- Trip travel times are estimated from prices because the dataset lacks geographic information and completed-trip durations.
- The simulated city uses dataset districts as regions and connects each region pair with travel time equal to its estimated average.
- Customer requests are replayed with their recorded start times, locations, and destinations, while unavailable vehicles create queues.
- The MPC algorithm runs every Δt = 5 minutes and assigns generated routes to idle vehicles in each region.
- The LSTM encoder-decoder forecasts each origin-destination demand series from the preceding Tback steps over the following Tforward steps.
D. Detailed results for a single day
The single-day evaluation compares four controllers on 330,000 trips, showing that forecast-based MPC substantially reduces waiting while enabling preemptive rebalancing. MPC-LSTM achieves the best causal performance, whereas Reactive issues many more, shorter rebalancing tasks.
- Wait-time results: 89.6% shorter mean wait time was achieved by MPC-LSTM than by the Reactive controller.MPC-Perfect had a 3.7-second mean wait and zero median wait; TV-Reactive had twice Reactive’s mean wait.
- Time-varying behavior: 8,892 waiting customers was Reactive’s afternoon peak, compared with 843 for MPC-LSTM during the morning rush.The difference is visible in the time series of waiting customers and is associated with forecast-enabled preemptive rebalancing.
- Time-varying behavior: MPC-Perfect and MPC-LSTM issued substantial rebalancing tasks around 6AM, before the morning rush, while Reactive began rebalancing after the rush started.The controllers were configured with a planning horizon T = 50 and a 24-interval forecasting horizon for the MPC scenarios.
- Rebalancing behavior: Reactive issued more than three times as many rebalancing tasks as MPC-LSTM but averaged only 37% more vehicles rebalancing.This implies shorter Reactive rebalancing trips, which can send vehicles to regions where they are not needed while seeking equal availability.
E. Comparison for different forecasting horizons
The forecasting-horizon study varies Tforward and Tback while keeping the planning horizon fixed. Longer forward forecasts initially improve performance but show diminishing returns, whereas the backward horizon has little effect.
- Experimental design: Tforward and Tback were varied from 3 to 48 time steps, while the planning horizon remained fixed at T = 50.A separate LSTM was trained for each forecasting-horizon combination.
- Forecasting-horizon sensitivity: Tback has little effect on mean wait times across the tested combinations.The paper attributes this pattern to the greater predictive power of time of day and demand at the previous time step than demand two or more steps earlier.
- Experimental design: Figure 2 reports mean wait times for each tested combination of Tforward and Tback.The comparison isolates the sensitivity of controller performance to forward and backward forecasting horizons.
- Forecasting-horizon sensitivity: Longer Tforward initially improves system performance significantly, then levels off with diminishing returns.The early gains are attributed to forecasting demand that requires long rebalancing travel times to serve.
F. Computational complexity
The MPC framework is computationally tractable for real-time AMoD control while scaling to large systems, but its strongest performance depends on forecast availability.
- 15.1s average solution time across 7175 MILP instances supports real-time control on commodity hardware.No instance required more than 61 seconds.
- The MPC algorithm’s complexity does not depend on the number of vehicles or customers, supporting control of large-scale AMoD systems.
- 89.6% shorter customer wait times were achieved by incorporating forecasted demand into rebalancing synthesis.
- Without a demand forecast, the MPC algorithm performs significantly worse than the reactive controller.The paper identifies risk-averse MPC as one possible way to address forecast uncertainty.