Maximum Throughput Dispatch for Shared Autonomous Vehicles Including Vehicle Rebalancing

Shared autonomous vehicles (SAVs) provide on demand point-to-point transportation for passengers. This service has been extensively studied using dispatch heuristics and agent based simulations of large urban areas. However, these approaches make no mathematical guarantees of the passenger throughput for the SAV network. This study builds on the dynamic queuing model design of Kang and Levin which provides a maximum stability dispatch policy for SAVs. This model is extended to include rebalancing of empty vehicles to regions of high demand. The modified dispatch policy is proven to maximize throughput. Simulation results show that this dispatch policy reduces waiting times (between vehicle dispatch and passenger pickup) compared to the original formulation. However, vehicle time traveling empty increases in some scenarios. Simulation results also show that rebalancing often reduces passenger waiting times, but not when too many vehicles rebalance at once and are not available for dispatch.