# A Dynamic Tree Algorithm for Peer-to-Peer Ride-sharing Matching

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2021.

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

- [Promoting Two-sided Fairness in Dynamic Vehicle Routing Problem](https://mlsanity.com/paper/2405.19184/) (2024)

## Abstract (arXiv)

On-demand peer-to-peer ride-sharing services provide flexible mobility options, and are expected to alleviate congestion by sharing empty car seats. An efficient matching algorithm is essential to the success of a ride-sharing system. The matching problem is related to the well-known dial-a-ride problem, which also tries to find the optimal pickup and delivery sequence for a given set of passengers. In this paper, we propose an efficient dynamic tree algorithm to solve the on-demand peer-to-peer ride-sharing matching problem. The dynamic tree algorithm benefits from given ride-sharing driver schedules, and provides satisfactory runtime performances. In addition, an efficient pre-processing procedure to select candidate passenger requests is proposed, which further improves the algorithm performance. Numerical experiments conducted in a small network show that the dynamic tree algorithm reaches the same objective function values of the exact algorithm, but with shorter runtimes. Furthermore, the proposed method is applied to a larger size problem. Results show that the spatial distribution of ride-sharing participants influences the algorithm performance. Sensitivity analysis confirms that the most critical ride-sharing matching constraints are the excess travel times. The network analysis suggests that small vehicle capacities do not guarantee overall vehicle-kilometer travel savings.