  Ride-pooling, which accommodates multiple passenger requests in a single
trip, has the potential to significantly increase fleet utilization in shared
mobility platforms. The ride-pooling assignment problem finds optimal co-riders
to maximize the total utility or profit on a shareability graph, a hypergraph
representing the matching compatibility between available vehicles and pending
requests. With mixed fleets due to the introduction of automated or premium
vehicles, fleet sizing and relocation decisions should be made 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. The performance of
these algorithms is validated using a mixed autonomy on-demand mobility
simulator. These efficient algorithms serve as a stepping stone for a variety
of multimodal and multiclass on-demand mobility applications.

Optimization and Control;Discrete Mathematics