  We study the problem of servicing a set of ride requests by dispatching a set
of shared vehicles, which is faced by ridesharing companies such as Uber and
Lyft. Solving this problem at a large scale might be crucial in the future for
effectively using large fleets of autonomous vehicles. Since finding a solution
for the entire set of requests that minimizes the total driving time is
NP-complete, most practical approaches process the requests one by one. Each
request is inserted into any vehicle's route such that the increase in driving
time is minimized. Although this variant is solvable in polynomial time, it
still takes considerable time in current implementations, even when inexact
filtering heuristics are used. In this work, we present a novel algorithm for
finding best insertions, based on (customizable) contraction hierarchies with
local buckets. Our algorithm finds provably exact solutions, is still 30 times
faster than a state-of-the-art algorithm currently used in industry and
academia, and scales much better. When used within iterative transport
simulations, our algorithm decreases the simulation time for largescale
scenarios with many requests from days to hours.
