A Time-invariant Network Flow Model for Ride-pooling in Mobility-on-Demand Systems

This paper presents a framework to incorporate ride-pooling from a mesoscopic point of view, within time-invariant network flow models of Mobility-on-Demand systems. The resulting problem structure remains identical to a standard network flow model, a linear problem, which can be solved in polynomial time for a given ride-pooling request assignment. In order to compute such a ride-pooling assignment, we devise a polynomial-time knapsack-like algorithm that is optimal w.r.t. the minimum user travel time instance of the original problem. Finally, we conduct two case studies of Sioux Falls and Manhattan, where we validate our models against state-of-the-art time-varying results, and we quantitatively highlight the effects that maximum waiting time and maximum delay thresholds have on the vehicle hours traveled, overall pooled rides and actual delay experienced. We show that for a sufficient number of requests, with a maximum waiting time and delay of 5 minutes, it is possible to ride-pool more than 80% of the requests for both case studies. Last, allowing for four people ride-pooling can significantly boost the performance of the system.