  In this paper we study the routing and rebalancing problem for a fleet of
autonomous vehicles providing on-demand transportation within a congested urban
road network (that is, a road network where traffic speed depends on vehicle
density). We show that the congestion-free routing and rebalancing problem is
NP-hard and provide a randomized algorithm which finds a low-congestion
solution to the routing and rebalancing problem that approximately minimizes
the number of vehicles on the road in polynomial time. We provide theoretical
bounds on the probability of violating the congestion constraints; we also
characterize the expected number of vehicles required by the solution with a
commonly-used empirical congestion model and provide a bound on the
approximation factor of the algorithm. Numerical experiments on a realistic
road network with real-world customer demands show that our algorithm
introduces very small amounts of congestion. The performance of our algorithm
in terms of travel times and required number of vehicles is very close to (and
sometimes better than) the optimal congestion-free solution.
