This article was originally published in Catalyst, May 2020.
Waymo and Uber have started trials of shared autonomous vehicle (SAV) service in several US cities. Without the expense of drivers, autonomous service could one day make the cost of a ride so low that people choose SAVs for their daily transportation needs instead of owning a vehicle.
As a result, the efficiency of SAV systems, particularly in terms of matching shared vehicles to customers, could become highly important. To shed light on the challenges and possibilities, University of Minnesota researchers developed a dispatch model that would provide optimal throughput for SAVs. The research was led by Michael Levin, an assistant professor in the Department of Civil, Environmental, and Geo- Engineering, and funded by the Center for Transportation Studies.
Previous studies have constructed simulations of SAV interactions with travelers on city networks. Those studies found that each SAV could replace between 3 and 11 personal vehicles.
“This range is because the results are highly dependent on the passenger-to-vehicle matching technique used and the network topology,” Levin says.
Most vehicle-routing problems are complex and involve large numbers of potential customers, Levin explains, so most of the studies used a modeling technique that requires less time and data to produce feasible—but not necessarily optimal—solutions.
In this project, the research team analyzed the SAV dispatch problem using the concept of stability. Traffic networks are considered stable when the number of vehicles in the network, on average, remains bounded (does not grow to infinity). Inefficient signal timings or higher demand prevent stability.
For a fleet of SAVs, the number of vehicles in the network is constant but the number of waiting travelers could grow large if the fleet is too small to serve them. Other factors influencing stability include the additional congestion caused by SAV route patterns and trips without passengers. “Ideally, the dispatch strategy for SAVs would maintain stability for the largest number of travelers possible,” Levin says.
The researchers began by constructing a queueing model that represents the SAV system. They then analytically derived the demands that could be stabilized for any SAV system. “This analysis can determine the relationship between fleet size and demand,” Levin says.
Next, they analytically developed a maximum-pressure dispatch policy for SAVs and proved it has maximum stability. “Our strategy is guaranteed to serve at least as much demand as any other dispatch strategy,” he says.
The team has also completed numerical comparisons of the dispatch strategy to supplement the analytical results from this project.
Crossroads 
One thought on “Shared Autonomous Vehicles: Dispatch Model Optimizes Service”