  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.
