FMS-dispatch: a fast maximum stability dispatch policy for shared autonomous vehicles including exiting passengers under stochastic travel demand

Shared autonomous vehicles (SAVs) are a fleet of autonomous taxis that provide point-to-point transportation services for travellers, and have the potential to reshape the nature of the transportation market in terms of operational costs, environmental outcomes, increased tolling efficiency, etc. However, the number of waiting passengers could become arbitrarily large when the fleet size is too small for travel demand, which could cause an unstable network. An unstable network will make passengers impatient and some people will choose some other alternative travel modes, such as metro or bus. To achieve stable and reliable SAV services, this study designs a dynamic queueing model for waiting passengers and provides a fast maximum stability dispatch policy for SAVs when the average number of waiting for passengers is bounded in expectation, which is analytically proven by the Lyapunov drift techniques. After that, we expand the stability proof to a more realistic scenario accounting for the existence of exiting passengers. Unlike previous work, this study considers exiting passengers in stability analyses for the first time. Moreover, the maximum stability of the network doesn't require a planning horizon based on the proposed dispatch policy. The simulation results show that the proposed dispatch policy can ensure the waiting queues and the number of exiting passengers remain bound in several experimental settings.