Personal tools
You are here: Home CG seminar 2019 Scalable and Congestion-aware Routing for Autonomous Mobility-On-Demand via Frank-Wolfe Optimization
« August 2019 »
August
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
25262728293031
Log in


Forgot your password?
 

Scalable and Congestion-aware Routing for Autonomous Mobility-On-Demand via Frank-Wolfe Optimization

Wednesday, July 3rd, 2019, 16:10

Schreiber 309

underline

Scalable and Congestion-aware Routing for Autonomous Mobility-On-Demand via Frank-Wolfe Optimization

Kiril Solovey, Stanford

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. 

This is joint work with Mauro Salazar and Marco Pavone. To appear in Robotics: Science and Systems 2019. 
Document Actions