Multistage Contextual Optimization for Vehicle Repositioning

Jinyu Zhang, Di Huang, Zhiyuan Liu, Nikolas GeroliminisarXiv 2026 · arXiv

In the world of ride-hailing, having cars in the right place at the right time is the difference between a profitable platform and a frustrated user base. This paper, "Multistage Contextual Optimization for Vehicle Repositioning," introduces a sophisticated framework that doesn't just predict demand—it trains its prediction models to maximize actual business outcomes while accounting for the complex, stage-by-stage nature of urban traffic.

TL;DR

The authors develop a Multistage Contextual Optimization (MCO) framework for ride-hailing that trains demand predictors based on their impact on final decision performance rather than just forecast accuracy. By integrating congestion-aware traffic models and a novel parallel training algorithm, they achieve up to a 9.1% increase in business benefit over standard methods using real-world New York City data.

What Problem Does This Paper Address?

Ride-hailing platforms face a "repositioning" challenge: moving idle vehicles to high-demand areas before requests actually arrive. This is difficult for two main reasons:

  1. The Multistage Trap: Decisions made now (moving a car) affect the future state (where that car is in 15 minutes), which in turn affects future decisions. Most existing models treat these stages in isolation.
  2. The Prediction-Optimization Gap: Traditional "predict-then-optimize" pipelines train demand models to minimize forecast error (like Mean Squared Error). However, a small error in a high-traffic area might be much more costly to the business than a large error in a quiet suburb.
  3. Congestion Feedback: Moving thousands of empty cars to "rebalance" the fleet actually adds to city traffic, potentially slowing down the very trips the platform is trying to complete.

Methods

The authors propose a holistic approach that links prediction, traffic dynamics, and optimization:

  • MFD-Aware Optimization: They use a Macroscopic Fundamental Diagram (MFD) to model how vehicle accumulation in a region affects overall traffic speed. This ensures the repositioning strategy doesn't accidentally gridlock the city.
  • Contextual Learning: Instead of training the demand predictor on historical accuracy, they differentiate through the entire optimization process. The loss function is the actual "decision cost" (waiting times, lost requests, and travel costs).
  • Decision-Dependent Context: The model recognizes that the state left by earlier decisions (e.g., where cars ended up) serves as context for the next stage's demand forecast.
  • Parallel Block Evaluation: Training multistage models is notoriously slow because you usually have to solve optimization problems for every time step in sequence. The authors introduced an algorithm that solves "blocks" of time steps in parallel, significantly speeding up the training process without sacrificing the quality of the learned policy.
Figure 1: Vehicle movements and their effect on regional traffic. A service trip carries a passenger from origin region o to destination region j. A repositioning vehicle travels empty from o toward j and may pick up a passenger in the intermediate region i who is also headed to j. Above each region, the MFD relates production P to accumulation N. The arrows show how these movements shift the regional state: accumulation falls in the congested origin region, which raises its production, and rises in the regions the vehicles enter.

Datasets

The framework was evaluated using New York City ride-hailing trip data from the NYC Taxi and Limousine Commission (2026).

  • Scope: 8 regions, 64 OD pairs, and 180 decision stages per day (5-minute intervals).
  • Training/Testing: Data from March 2026 was used for training, with April 2026 used for testing.
  • Simulation: Results were validated in a high-fidelity agent-based simulation of individual vehicles and requests.

Key Insights and Ideas

  • "Helpful Biases": Surprisingly, the MCO-trained model outperformed an "oracle" with perfect demand knowledge. Why? Because the MCO model learned to produce "biased" forecasts (e.g., predicting 9% higher demand than reality) to compensate for the simplifications and linearizations in the optimization model itself.
  • State Matters for Prediction: The operational effect of a forecast error depends on the current state. Underpredicting demand is a minor issue if you have a surplus of cars, but a disaster if the fleet is already stretched thin.
  • Parallelism without Loss: The Parallel Block Evaluation proves that you can approximate the "serial trajectory" of a multistage problem in a few parallel passes, making it feasible to train these complex models on large-scale urban data.

Key Results

  • Business Impact: MCO yielded 7.7% to 9.1% more business benefit than a standard predictor trained on Mean Squared Error (MSE).
  • Superiority over Baselines: It outperformed all compared baselines, including Reinforcement Learning (RL) and traditional robust optimization.
  • Training Speed: With eight workers, the parallel block evaluation shortened training time by a factor of 1.86 compared to serial evaluation.
  • Efficiency: MCO-parallel achieved the lowest waiting times (1.36 min) and abandonment rates (10.38%) among all tested methods.

Limitations and Future Work

  • Exogenous Demand: The paper assumes demand is independent of the platform's performance. In reality, long wait times might cause users to switch to other modes of transport (endogenous demand).
  • Driver Autonomy: The model assumes vehicles follow platform instructions perfectly. Future work could incorporate incentives to align the behavior of independent human drivers with the platform's repositioning goals.
  • Joint Optimization: Integrating pricing and matching decisions directly into the multistage contextual learning loop remains an open challenge.

Summary updated

Abstract

Ride-hailing platforms reposition idle vehicles to improve spatial supply-demand balances. This problem is prediction-driven and multistage: at each stage, the platform forecasts future demand, executes current decisions, and uses the resulting state to initialize the next stage. We formulate a multistage linear program (LP) with a macroscopic fundamental diagram (MFD) linking accumulation to trip completion. We then develop a multistage contextual optimization approach that uses decision performance to train the prediction model. The learning problem combines multiple coupled stages, context that depends on earlier decisions, and predictions that affect the objective, the constraint matrix, and the right-hand side of the LP. We derive the exact gradient, which has three parts: parameters change forecasts and hence decisions; earlier decisions change the current decision through the inherited state; and this state also changes forecasts as context. An equivalent adjoint uses reverse vector-Jacobian products, avoiding full solution and state-parameter Jacobians. Finally, forward propagation solves many stage LPs one after another, which makes training slow. We propose a parallel block evaluation algorithm that solves blocks of consecutive stages in parallel and repeatedly feeds each block output to the next block. We prove that the algorithm recovers the serial trajectory within a finite number of passes and that its gradient error remains bounded when it stops early. On New York City ride-hailing data, multistage contextual optimization yields 7.7% to 9.1% more business benefit than the same predictor trained by mean squared error, outperforms all compared baselines from five paradigms, and even outperforms realized demand fed to the same policy. With eight workers, parallel block evaluation shortens training by a factor of 1.86 without loss of decision performance.
BibTeX
@misc{zhang2026multistage,
  author = {Jinyu Zhang and Di Huang and Zhiyuan Liu and Nikolas Geroliminis},
  title = {{Multistage Contextual Optimization for Vehicle Repositioning}},
  year = {2026},
  eprint = {2611.22330},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22330},
}
Figure