In this paper we study the routing and rebalancing problem for a fleet of autonomous vehicles providing on-demand transportation within a congested urban road network (that is, a road network where traffic speed depends on vehicle density). We show that the congestion-free routing and rebalancing problem is NP-hard and provide a randomized algorithm which finds a low-congestion solution to the routing and rebalancing problem that approximately minimizes the number of vehicles on the road in polynomial time. We provide theoretical bounds on the probability of violating the congestion constraints; we also characterize the expected number of vehicles required by the solution with a commonly-used empirical congestion model and provide a bound on the approximation factor of the algorithm. Numerical experiments on a realistic road network with real-world customer demands show that our algorithm introduces very small amounts of congestion. The performance of our algorithm in terms of travel times and required number of vehicles is very close to (and sometimes better than) the optimal congestion-free solution.


    Access

    Download


    Export, share and cite



    Title :

    Congestion-Aware Randomized Routing in Autonomous Mobility-on-Demand Systems


    Contributors:

    Publication date :

    2016


    Remarks:

    This paper has been withdrawn by the authors due to an error in the proofs of Theorem 3.4 (bound on the probability of violating the congestion constraints) and Lemma 3.5 (approximation factor of the algorithm)


    Type of media :

    Preprint


    Type of material :

    Electronic Resource


    Language :

    English




    Congestion-aware Routing and Rebalancing of Autonomous Mobility-on-Demand Systems in Mixed Traffic

    Wollenstein-Betech, Salomon / Houshmand, Arian / Salazar, Mauro et al. | IEEE | 2020


    A Cross-Layer, Mobility, and Congestion-Aware Routing Protocol for UAV Networks

    Garg, Shivam / Ihler, Alexander / Bentley, Elizabeth Serena et al. | IEEE | 2023


    Routing and Rebalancing Intermodal Autonomous Mobility-on-Demand Systems in Mixed Traffic

    Wollenstein-Betech, Salomon / Salazar, Mauro / Houshmand, Arian et al. | IEEE | 2022


    A congestion-aware Tabu search heuristic to solve the shared autonomous vehicle routing problem

    Venkatraman, Prashanth / Levin, Michael W. | Taylor & Francis Verlag | 2021