  Ride-sharing can reduce traffic congestion and thus reduce gas emissions and
save travel time. However, transportation system with ride-sharing is currently
inefficient due to low occupancy rate, high travel demand and some other
factors. Existing literature did not consider ride-sharing with multi-request
grouped in one trip. In our paper, we firstly proposed a graph-based algorithm
that can obtain an approximation solution in polynomial time and then proposed
an exact algorithm to solve this problem with maximizing the number of
passenegers served in $O(1.2312^{|\mathcal{E}|})$ time.
