A general maximum-stability dispatch policy for shared autonomous vehicle dispatch with an analytical characterization of the maximum throughput

Shared autonomous vehicles (SAVs) have been studied through analytical dispatch methods and simulation. A common question of interest is how many customers can be served per SAV, which necessarily depends on the network characteristics, travel demand, and dispatch policy. We identify equations that describe the maximum set of demands that could be served if an appropriate dispatch policy were chosen. We then provide a dispatch policy that achieves the predicted level of passenger throughput. This is achieved for a general class of SAV behaviors which may include ridesharing, electric SAV recharging, integration with public transit, or combinations thereof. We accomplish this by defining a Markov chain queueing model which admits general SAV behaviors. We say the network is stable if the head-of-line waiting times remain bounded, which is equivalent to serving all customers at the same rate at which they request service. We give equations characterizing the stable region Λ — the set of demands that could be served by any dispatch policy. We prove that any demand outside Λ cannot be completely served. We further prove that our dispatch policy stabilizes the network for any demand in the stable region using Lyapunov drift, establishing Λ as the maximum set of demand that can be served. Numerical results validate our calculations using simulation, and we present initial results on calculating Λ for a large city network.