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

Kiril Solovey, Mauro Salazar, Marco Pavone

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

14 Citaten (Scopus)
37 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelRobotics
SubtitelScience and Systems XV
RedacteurenAntonio Bicchi, Hadas Kress-Gazit, Seth Hutchinson
Aantal pagina's22
DOI's
StatusGepubliceerd - jun. 2019
Extern gepubliceerdJa
EvenementRSS 2019 : Robotics: Science and Systems - Freiburg im Breisgau, Duitsland
Duur: 22 jun. 201926 jun. 2019
https://roboticsconference.org/

Congres

CongresRSS 2019 : Robotics: Science and Systems
Land/RegioDuitsland
StadFreiburg im Breisgau
Periode22/06/1926/06/19
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Scalable and congestion-aware routing for Autonomous Mobility-on-Demand via Frank-Wolfe optimization'. Samen vormen ze een unieke vingerafdruk.

Citeer dit