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

In this article, we present 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. In order to compute the ride-pooling assignment, which is the matching between two or more users so that they can be pooled together, we devise a polynomial-time knapsack-like algorithm that is optimal w.r.t. the minimum vehicle travel time with users on-board. Finally, we conduct two case studies of Sioux Falls and Manhattan, where we validate our models against state-of-the-art 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. Last, we show that allowing four people ride-pooling can significantly boost the performance of the system.