# Large Scale Real-time Ridesharing with Service Guarantee on Road Networks

arXiv: https://arxiv.org/abs/1302.6666 · HTML: https://mlsanity.com/paper/1302.6666/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2013.

## Built on by (most cited first, 3 of 3)

- [Using Simple Incentives to Improve Two-Sided Fairness in Ridesharing Systems](https://mlsanity.com/paper/2303.14332/) (2023)
- [Conditional Expectation based Value Decomposition for Scalable On-Demand Ride Pooling](https://mlsanity.com/paper/2112.00579/) (2021)
- [Optimizing Ride-Pooling Operations with Extended Pickup and Drop-Off Flexibility](https://mlsanity.com/paper/2503.08472/) (2025)

## Abstract (arXiv)

The mean occupancy rates of personal vehicle trips in the United States is only 1.6 persons per vehicle mile. Urban traffic gridlock is a familiar scene. Ridesharing has the potential to solve many environmental, congestion, and energy problems. In this paper, we introduce the problem of large scale real-time ridesharing with service guarantee on road networks. Servers and trip requests are dynamically matched while waiting time and service time constraints of trips are satisfied. We first propose two basic algorithms: a branch-and-bound algorithm and an integer programing algorithm. However, these algorithm structures do not adapt well to the dynamic nature of the ridesharing problem. Thus, we then propose a kinetic tree algorithm capable of better scheduling dynamic requests and adjusting routes on-the-fly. We perform experiments on a large real taxi dataset from Shanghai. The results show that the kinetic tree algorithm is faster than other algorithms in response time.