We study a natural clustering problem arising in ride-sharing. Given certain transportation demands, we formulate an optimization problem that minimizes the number of trips required to fulfill all demands while respecting all constraints. We analyze the theoretical complexity and show NP-completeness of the problem. Based on the dimension or capacities of the vehicles, we identify special cases that are solvable to optimality in polynomial time. For the general problem, we provide an approximation algorithm, a fast non-polynomial time algorithm with provable performance guarantee, and an exact formulation as an integer program. We conclude with a simulation that quantifies the behavior of our algorithms on real-world New York taxi data and identifies the possible savings achieved through ride-sharing. We show that, within seconds, we obtain a solution in a very limited time that reduces the trips by roughly 28% and saves about 18% of CO2 emissions.