  Ride-sharing is an essential aspect of modern urban mobility. In this paper,
we consider a classical problem in ride-sharing - the Multi-Vehicle Dial-a-Ride
Problem (Multi-Vehicle DaRP). Given a fleet of vehicles with a fixed capacity
stationed at various locations and a set of ride requests specified by origins
and destinations, the goal is to serve all requests such that no vehicle is
assigned more passengers than its capacity at any point along its trip. We
propose an algorithm HRA, which is the first non-trivial approximation
algorithm for the Multi-Vehicle DaRP. The main technical contribution is to
reduce the Multi-Vehicle DaRP to a certain capacitated partitioning problem,
which we solve using a novel hierarchical grouping algorithm. Experimental
results show that the vehicle routes produced by our algorithm not only exhibit
less total travel distance compared to state-of-the-art baselines, but also
enjoy a small in-transit latency, which crucially relates to riders' traveling
times. This suggests that HRA enhances rider experience while being
energy-efficient.
