Real-Time Vehicle Repositioning Through Fast Optimal Transport

Abstract

In urban mobility services such as ride-hailing and delivery logistics, vehicles must be strategically positioned during low-demand periods to serve sudden demand surges in specific geographic areas. To ensure that the demand is sufficiently met, there needs to be proactive as well as reactive planning. This paper proposes the formulation of dynamic vehicle routing problem(DVRP) with time-budget constraints where stochastic demand requires balancing reactive service of immediate requests with proactive positioning for anticipated future demand. The proposed approach is an adaptive repositioning framework that combines zone-level entropic optimal transport for vehicle-request assignment with online learning of spatial demand patterns. The Greenkhorn algorithm efficiently solves the regularized transport problem at each decision epoch, while exponential smoothing continuously updates zone preference weights that drive threshold-based repositioning of idle vehicles to anticipated high-demand areas. Further, the approach provides formal stability analysis under stationary stochastic demand, proving almost sure queue boundedness via Foster-Lyapunov drift conditions. Experiments on instances based on a real street network demonstrate effective proactive repositioning as compared to myopic, learning-based baselines without requiring offline training or explicit demand forecasting models.