Maximum-stability dispatch policy for shared autonomous vehicles. (June 2021) - Kang, Di; Levin, Michael W.
Highlights: This paper builds the shared autonomous vehicles (SAVs) dispatch problem as a Markov decision process and proposes a max-pressure dispatch policy. The set of stochastic demand that could be stabilized for any SAV systems (under the assumptions made) is analytically characterized. The proposed max-pressure dispatch policy for any SAV systems is proven to serve all demand whenever possible using Lyapunov drift techniques. Linear programs for finding the minimum fleet size and replacement ratio are developed. Abstract: Shared autonomous vehicles (SAVs) have been widely studied in the recent literature. Agent-based simulations and theoretical models have extensively explored the effects on travel service, fleet size, and congestion using heuristic dispatching strategies to match SAVs with on-demand passengers. A major question that simulations have sought to address is the service rate or replacement rate: the number of passengers each SAV can serve. Thus far, the service rate has mostly been estimated through simulation. This paper investigates an analytical max-pressure dispatch policy, which aims to maximize passenger throughput under any stochastic demand pattern, which takes the form of a model predictive control algorithm. An analytical proof using Lyapunov drift techniques is presented to show that the dispatch policy achieves maximum stability. The service rate and minimum fleet sizes are derived analytically in this paper and can be achieved with the proposed dispatch policy. Simulation results show that the maximum stable demand is linearly related to the fleet size given. Also, it demonstrates how asymmetric demand necessitates rebalancing trips that affect service rates. Even though decreasing average waiting time is not the primary goal of this paper, stability ensures bounded waiting times, which is demonstrated in simulation.