A BCMP Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems
Provides a unifying framework for analyzing and controlling AMoD systems, subsuming earlier models and enabling richer modeling options, but is incremental in extending existing queueing network theory to a specific application.
This paper presents a BCMP queueing network model for autonomous mobility-on-demand (AMoD) systems, enabling analysis of performance metrics and synthesis of routing policies with guarantees for large fleets, validated on a New York City case study.
In this paper we present a queueing network approach to the problem of routing and rebalancing a fleet of self-driving vehicles providing on-demand mobility within a capacitated road network. We refer to such systems as autonomous mobility-on-demand systems, or AMoD. We first cast an AMoD system into a closed, multi-class BCMP queueing network model. Second, we present analysis tools that allow the characterization of performance metrics for a given routing policy, in terms, e.g., of vehicle availabilities, and first and second order moments of vehicle throughput. Third, we propose a scalable method for the synthesis of routing policies, with performance guarantees in the limit of large fleet sizes. Finally, we validate our theoretical results on a case study of New York City. Collectively, this paper provides a unifying framework for the analysis and control of AMoD systems, which subsumes earlier Jackson and network flow models, provides a quite large set of modeling options (e.g., the inclusion of road capacities and general travel time distributions), and allows the analysis of second and higher-order moments for the performance metrics.