Managing Resources for Shared Micromobility: Approximate Optimality in Large-Scale Systems

We consider the problem of managing resources in shared micromobility systems (bike sharing and scooter sharing). An important task in managing such systems is periodic repositioning/recharging/sourcing of units to avoid stockouts or excess inventory at nodes with unbalanced flows. We consider a discrete-time model; each period begins with an initial inventory at each node in the network, and then, customers (demand) materialize at the nodes. Each customer picks up a unit at the origin node and drops it off at a randomly sampled destination node with an origin-specific probability distribution. We model the above network inventory management problem as an infinite horizon discrete-time discounted Markov decision process (MDP) and prove the asymptotic optimality of a novel mean-field approximation to the original MDP as the number of stations becomes large. To compute an approximately optimal policy for the mean-field dynamics, we provide an algorithm with a running time that is logarithmic in the desired optimality gap. Lastly, we compare the performance of our mean field-based policy with state-of-the-art heuristics via numerical experiments, including experiments using Austin scooter-sharing data.