Abstract

This paper considers the problem of routing and rebalancing a shared fleet of autonomous vehicles providing on-demand mobility within a capacitated transportation network, where congestion might disrupt throughput. We model the problem within a network flow framework and show that under relatively mild assumptions the rebalancing vehicles, if properly coordinated, do not lead to an increase in congestion. From an algorithmic standpoint, such theoretical insight suggests that the problem of routing customers and rebalancing vehicles can be decoupled, which leads to a computationally-efficient routing and rebalancing algorithm for the autonomous vehicles.

Citation

Rossi, Federico, Rick Zhang, Yousef Hindy, and Marco Pavone. 2018. “Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms.” Autonomous Robots 42: 1427-1442.

@article{Rossi2018,
author = {Federico Rossi and Rick Zhang and Yousef Hindy and Marco Pavone},
year = {2018},
title = {Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms},
journal = {Autonomous Robots},
volume = {42},
pages = {1427--1442},
doi = {10.1007/s10514-018-9750-5}}