2021/08/19 by Qi Luo, Luo, Qi, Viswanath Nagarajan +9
Business, Management and Accounting · Engineering · Social Sciences · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Sharing Economy and Platforms #Transportation Planning and Optimization #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.2108.08651
openalex publication_date 2021/08/19 · openalex created_date 2021/08/30 · openalex updated_date 2026/07/28
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 \frac1p2 and (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.