  Mobility systems featuring shared vehicles are often unable to serve all
potential customers, as the distribution of demand does not coincide with the
positions of vehicles at any given time. System operators often choose to
reposition these shared vehicles (such as bikes, cars, or scooters) actively
during the course of the day to improve service rate. They face a complex
dynamic optimization problem in which many integer-valued decisions must be
made, using real-time state and forecast information, and within the tight
computation time constraints inherent to real-time decision-making. We first
present a novel nested-flow formulation of the problem, and demonstrate that
its linear relaxation is significantly tighter than one from existing
literature. We then adapt a two-stage stochastic approximation scheme from the
generic SPAR algorithm due to Powell et al., in which rebalancing plans are
optimized against a value function representing the expected cost (in terms of
fulfilled and unfulfilled customer demand) of the future evolution of the
system. The true value function is approximated by a separable function of
contributions due to the rebalancing actions carried out at each station and
each time step of the planning horizon. The new algorithm requires surprisingly
few iterations to yield high-quality solutions, and is suited to real-time use
as it can be terminated early if required. We provide insight into this good
performance by examining the mathematical properties of our new flow
formulation, and perform rigorous tests on standardized benchmark networks to
explore the effect of system size. We then use data from Philadelphia's public
bike sharing scheme to demonstrate that the approach also yields performance
gains for real systems.
