Multistage Contextual Optimization for Vehicle Repositioning
Authors: Jinyu Zhang, Di Huang, Zhiyuan Liu, Nikolas Geroliminis
Organizations: School of Transportation, Southeast University, Nanjing, China · Urban Transport Systems Laboratory (LUTS), École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland · School of Statistics and Data Science, Southeast University, Nanjing, China
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.
Figures & tables
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.
Figure 2: Commitment–recourse policy at stage t . Peach boxes denote the pre- and post-realization LPs, white boxes denote inputs and outputs, and arrows show their dependencies. Both LPs start from the same state st . The pre LP uses horizon forecasts dt and the reference vector ntpre of stocks and accumulations to choose the current repositioning commitment gtexec . The post LP retains that commitment, replaces current-period forecast demand with realized demand dt , and uses the remaining future forecasts dtfut and post reference vector ntpost . Its solution, after cohort reallocation, provides the first-period executed vector zt , realized cost Jtexec , and next state st+1 .
Figure 3: Multistage commitment–recourse execution over T stages. Peach boxes denote LP solves, blue boxes denote reference-construction maps, and white boxes denote states, demand, decisions, and costs. Black arrows show their input–output dependencies. At stage zero, Refinit constructs the pre reference from s0 and d0 . At each stage t , the pre LP uses st , the horizon forecast dt , and its pre reference to choose the repositioning commitment. The pre optimum also supplies the allocation preferences for Reftpost , which constructs the post reference under realized current demand dt and future forecasts dtfut . The post LP retains the commitment and provides the next state st+1 and executed vector zt , whose cost Jtexec contributes to J . Each later pre reference uses the inherited state, updated forecasts, and preceding post plan.
Figure 4: Single-stage computation graph. Blue rectangles denote data, solutions, and loss, peach ellipses denote maps, and black arrows show their input–output dependencies. The predictor fθ maps xtexo and st to the forecast dt , using trainable parameters θ . Red and blue dash-dotted arrows trace pre- and post-reference construction, respectively. The maps Reftpre and Reftpost produce the reference vectors ntpre and ntpost . The pre solution utpre,⋆ supplies the repositioning commitment. Given that commitment and realized current demand dt , the post plan utpost,⋆ , obtained from the post solution by cohort reallocation, supplies executed quantities zt and the next state. The cost vector c gives Jtexec=c⊤zt . The forecast also determines the prediction loss ℓpred,t . The two loss outputs contribute Jtexec+αℓpred,t to the training objective.
Figure 5: Adjoint recursion at an interior stage of the multistage policy. Rounded rectangles contain the accumulated loss gradients with respect to the post plan, forecast, and state, denoted by λtu , λtd , and λts . Red paths combine the current cost gradient c with future contributions through the next state and the retained plan used for reference updating. Green paths combine the decision contribution with the prediction-error gradient weighted by α . Blue paths return the decision and prediction contributions to the inherited state. Gray paths show the same recursion at adjacent stages. Arrow labels denote forward Jacobians or selection matrices; backward propagation uses their transposes. The black downward arrow contributes (Jd,θ,tpred)⊤λtd to the parameter gradient. Summing these contributions over stages gives the trajectory gradient.
Figure 6: Parallel block evaluation for three consecutive blocks over two passes. Each inner rounded box Ft is a stage map. Black arrows inside a block pass each post plan to the next stage. Fill colors identify blocks. Each colored arrow has the color of the block it enters. Solid arrows carry candidate post plans from the previous evaluation of the same sample to the block entries in pass 1. Dashed arrows carry the last plan of each block in pass 1 to the entry of the next block in pass 2. Blocks in the same pass are solved in parallel.
Figure 7: Backward pass on the final records after pass K for three consecutive blocks. Each inner rounded box Ft is a stage map. Black arrows inside a block carry the adjoint from each stage to the preceding stage. A hatched box between two blocks states that the output of the left block equals the entry of the right block minus the fixed residual. Dashed arrows carry the adjoint from the first stage of the right block through this relation to the last stage of the left block. Fill colors identify blocks. Each hatched box and dashed arrow has the color of the block on its right.
Figure 8: Study area. (a) The eight regions of the planning model, shaded by their mean requests per day (thousands) on the 20 test days, 06:00–21:00. (b) Mean idle vehicles at 06:00 by region on the test days. (c) The taxi zones of simulation and every vehicle at 08:00 on April 7, just before that minute’s matching, colored by its status. (d) The requests waiting to be matched at the same moment, at their pickup points and shaded by the time they have waited.
Variant
Benefit (USD)
Waiting time (min)
Abandonment (%)
Completions (%)
HA
Planning LP
2.554
1.54
12.09
86.41
Fixed-fraction LP
2.522 (−1.27%)
1.60
12.22
86.27
No repositioning
2.244 (−12.16%)
1.66
14.26
84.26
No pickup
2.390 (−6.44%)
1.60
13.20
85.31
Oracle
Table 1: Closed-Loop Performance of the Planning LP and Its Variants
Method
RMSE
Benefit (USD)
Days better
Waiting time (min)
Abandonment (%)
Completions (%)
Predict-then-optimize
MSE
10.21
2.608
–
1.49
11.83
86.67
HA
15.48
2.554 (−2.06%)
9/20
1.54
12.09
86.41
STID
8.88
2.624 (+0.60%)
14/20
1.49
11.76
86.75
ST-SSDL
10.07
2.617 (+0.33%)
9/20
1.49
11.80
86.71
MAGE
8.64
2.611 (+0.10%)
11/20
1.50
11.85
86.66
Table 2: Test Performance of the Compared Methods in the Simulation
In large-scale ride-hailing, hold control is a critical mechanism for improving passenger-driver experience. By selectively delaying certain driver-order pairs, the system waits for better opportunities, reduces cancellations, and mitigates wasted driver effort. However, existing industrial hold strategies often rely on heuristic thresholding over multiple predictive models, which can be brittle under non-stationary traffic and hard to optimize for multi-objective experience signals. We propose EXHOLD, a deployable two-stage framework decoupling experience-aware pair assessment from hold-time execution. In Stage I, we learn a decision model assigning each driver-order pair to discrete, interpretable experience tiers by optimizing a unified objective that aggregates satisfaction signals across the matching funnel. In Stage II, we solve for a monotone hold-time schedule via constrained optimization over empirical quantiles. This explicitly enforces service guardrails bounding the unnecessary holding of promising matches while maximizing overall experience improvement. We evaluate EXHOLD through randomized A/B experiments in DiDi's production system in Brazil. Results show consistent gains in marketplace efficiency and experience: EXHOLD increases trip completion and driver income, significantly reduces passenger cancellations, and improves funnel efficiency. Ablations and behavioral analyses confirm both stages are essential and that the policy makes calibrated decisions under spatiotemporal heterogeneity. EXHOLD is currently deployed, serving production traffic in Brazil.
Decision-making problems often feature uncertainty stemming from heterogeneous and context-dependent human preferences. To address this, we propose a sequential learning-and-optimization pipeline to learn preference distributions and leverage them to solve downstream problems, for example risk-averse formulations. We focus on human choice settings that can be formulated as (integer) linear programs. In such settings, existing inverse optimization and choice modelling methods infer preferences from observed choices but typically produce point estimates or fail to capture contextual shifts, making them unsuitable for risk-averse decision-making. Using a bounded-variance score function gradient estimator, we train a predictive model mapping contextual features to a rich class of parameterizable distributions. This approach yields a maximum likelihood estimate. The model generates scenarios for unseen contexts in the subsequent optimization phase. In a synthetic ridesharing environment, our approach reduces average post-decision surprise by up to 114× compared to a risk-neutral approach with perfect predictions and up to 25× compared to leading risk-averse baselines.
Benjamin Hudson, Laurent Charlin, Emma Frejinger
Mila – Quebec Artificial Intelligence Institute, Montreal, Quebec, Canada · Département d’informatique et de recherche opérationnelle (DIRO), Université de Montréal, Montreal, Quebec, Canada · HEC Montréal, Montreal, Quebec, Canada
Ride-hailing and autonomous mobility-on-demand operators reposition idle supply before future demand is fully observed. We study a retrieval-calibrated predict-then-optimize approach for this problem: historical demand regimes are matched to the current query block, combined into a calibrated demand prior, and passed to a fleet-balancing controller. The paper makes three contributions. First, we train a leakage-safe similarity gate whose objective penalizes demand error, pickup spatial mismatch, and queue shortage risk rather than retrieval rank alone. Second, we develop a spatial queue-regret decomposition for a stable queueing surrogate, linking demand-field error to wait through queueing sensitivity, allocator sensitivity, and Wasserstein pickup mismatch. Third, we evaluate learned retrieval and external-style rebalancing baselines in a common simulator. In the calibrated-demand gate experiment, across eight New York City scenarios and ten seeds, the spatial gate reduces mean wait to 82.3s, compared with 85.3s for hand-tuned similarity and 85.8s for a distributional-only baseline. In a separate replay-demand controller comparison, a scenario chance-MPC analog and a share-target transportation LP improve on Wen-style rebalancing (92.2s/92.2s vs. 100.1s), a reduced GPR chance-MPC comparator is intermediate at 94.4s, and an oracle MPC diagnostic is 91.3s.