Scalable and congestion-aware routing for Autonomous Mobility-on-Demand via Frank-Wolfe optimization

Kiril Solovey, Mauro Salazar, Marco Pavone

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)
28 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationRobotics
Subtitle of host publicationScience and Systems XV
EditorsAntonio Bicchi, Hadas Kress-Gazit, Seth Hutchinson
Number of pages22
DOIs
Publication statusPublished - Jun 2019
Externally publishedYes
EventRSS 2019 : Robotics: Science and Systems - Freiburg im Breisgau, Germany
Duration: 22 Jun 201926 Jun 2019
https://roboticsconference.org/

Conference

ConferenceRSS 2019 : Robotics: Science and Systems
Country/TerritoryGermany
CityFreiburg im Breisgau
Period22/06/1926/06/19
Internet address

Keywords

  • math.OC
  • cs.DS
  • cs.RO

Fingerprint

Dive into the research topics of 'Scalable and congestion-aware routing for Autonomous Mobility-on-Demand via Frank-Wolfe optimization'. Together they form a unique fingerprint.

Cite this