  Innovative shared mobility services provide on-demand flexible mobility
options and have the potential to alleviate traffic congestion. These
attractive services are challenging from different perspectives. One major
challenge in such systems is to find suitable ride-sharing matchings between
drivers and passengers with respect to the system objective and constraints,
and to provide optimal pickup and drop-off sequence to the drivers. In this
paper, we develop an efficient dynamic tree algorithm to find the optimal
pickup and drop-off sequence. The algorithm finds an initial solution to the
problem, keeps track of previously explored feasible solutions, and reduces the
solution search space when considering new requests. In addition, an efficient
pre-processing procedure to select candidate passenger requests is proposed,
which further improves the algorithm performance. Numerical experiments are
conducted on a real size network to illustrate the efficiency of our algorithm.
Sensitivity analysis suggests that small vehicle capacities and loose excess
travel time constraints do not guarantee overall savings in vehicle kilometer
traveled.
