  We consider several variants of a car-sharing problem. Given are a number of
requests each consisting of a pick-up location and a drop-off location, a
number of cars, and nonnegative, symmetric travel times that satisfy the
triangle inequality. Each request needs to be served by a car, which means that
a car must first visit the pick-up location of the request, and then visit the
drop-off location of the request. Each car can serve two requests. One problem
is to serve all requests with the minimum total travel time (called
$\CS_{sum}$), and the other problem is to serve all requests with the minimum
total latency (called $\CS_{lat}$). We also study the special case where the
pick-up and drop-off location of a request coincide. We propose two basic
algorithms, called the match and assign algorithm and the transportation
algorithm. We show that the best of the resulting two solutions is a $
2$-approximation for $\CS_{sum}$ (and a $7/5$-approximation for its special
case), and a $5/3 $-approximation for $\CS_{lat}$ (and a $3/2$-approximation
for its special case); these ratios are better than the ratios of the
individual algorithms. Finally, we indicate how our algorithms can be applied
to more general settings where each car can serve more than two requests, or
where cars have distinct speeds.
