2019/03/08 by Kiril Solovey, Solovey, Kiril, Mauro Salazar +3 · 1 citation
Engineering · Social Sciences · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Robotics (cs.RO) #Transportation Planning and Optimization #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1903.03697
openalex publication_date 2019/03/08 · openalex created_date 2022/09/28 · openalex updated_date 2026/07/28
We consider the problem of vehicle routing for Autonomous Mobility-on-Demand\n(AMoD) systems, wherein a fleet of self-driving vehicles provides on-demand\nmobility in a given environment. Specifically, the task it to compute routes\nfor the vehicles (both customer-carrying and empty travelling) so that travel\ndemand is fulfilled and operational cost is minimized. The routing process must\naccount for congestion effects affecting travel times, as modeled via a\nvolume-delay function (VDF). Route planning with VDF constraints is notoriously\nchallenging, as such constraints compound the combinatorial complexity of the\nrouting optimization process. Thus, current solutions for AMoD routing resort\nto relaxations of the congestion constraints, thereby trading optimality with\ncomputational efficiency. In this paper, we present the first\ncomputationally-efficient approach for AMoD routing where VDF constraints are\nexplicitly accounted for. We demonstrate that our approach is faster by at\nleast one order of magnitude with respect to the state of the art, while\nproviding higher quality solutions. From a methodological standpoint, the key\ntechnical insight is to establish a mathematical reduction of the AMoD routing\nproblem to the classical traffic assignment problem (a related vehicle-routing\nproblem where empty traveling vehicles are not present). Such a reduction\nallows us to extend powerful algorithmic tools for traffic assignment, which\ncombine the classic Frank-Wolfe algorithm with modern techniques for\npathfinding, to the AMoD routing problem. We provide strong theoretical\nguarantees for our approach in terms of near-optimality of the returned\nsolution.\n