Efficient Algorithms for Stochastic Ridepooling Assignment with Mixed Fleets

Ridepooling plays a pivotal role in improving fleet utilization in shared mobility platforms by serving multiple passenger requests simultaneously. The ridepooling assignment problem is solved repeatedly on a shareability graph, a hypergraph representing the matching compatibility between available vehicles and pending requests, to find optimal co-riders. With a mixed fleet of two or more types of vehicles, fleet sizing is predetermined before the requests are revealed. Due to the immense size of the underlying shareability graph and demand uncertainty, it is impractical to use exact methods to calculate the optimal trip assignments. Two approximation algorithms for mid-capacity and high-capacity vehicles are proposed in this paper; The respective approximation ratios are $\frac1{p^2}$ and $\frac{e-1}{(2e+o(1)) p \ln p}$, where $p$ is the maximum vehicle capacity plus one. A data-driven shared mobility simulator with mixed autonomy traffic validates the performance of these algorithms. These efficient algorithms serve as a stepping stone for a variety of multimodal and multiclass on-demand mobility applications.