  We consider the problem of vehicle routing for Autonomous Mobility-on-Demand
(AMoD) systems, wherein a fleet of self-driving vehicles provides on-demand
mobility in a given environment. Specifically, the task it to compute routes
for the vehicles (both customer-carrying and empty travelling) so that travel
demand is fulfilled and operational cost is minimized. The routing process must
account for congestion effects affecting travel times, as modeled via a
volume-delay function (VDF). Route planning with VDF constraints is notoriously
challenging, as such constraints compound the combinatorial complexity of the
routing optimization process. Thus, current solutions for AMoD routing resort
to relaxations of the congestion constraints, thereby trading optimality with
computational efficiency. In this paper, we present the first
computationally-efficient approach for AMoD routing where VDF constraints are
explicitly accounted for. We demonstrate that our approach is faster by at
least one order of magnitude with respect to the state of the art, while
providing higher quality solutions. From a methodological standpoint, the key
technical insight is to establish a mathematical reduction of the AMoD routing
problem to the classical traffic assignment problem (a related vehicle-routing
problem where empty traveling vehicles are not present). Such a reduction
allows us to extend powerful algorithmic tools for traffic assignment, which
combine the classic Frank-Wolfe algorithm with modern techniques for
pathfinding, to the AMoD routing problem. We provide strong theoretical
guarantees for our approach in terms of near-optimality of the returned
solution.
