In this paper we present a queuing 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 (AMoD) systems. We first cast an AMoD system into a closed, multi-class Baskett–Chandy–Muntz–Palacios (BCMP) queuing network model capable of capturing the passenger arrival process, traffic, the state-of-charge of electric vehicles, and the availability of vehicles at the stations. Second, we propose a scalable method for the synthesis of routing and charging policies, with performance guarantees in the limit of large fleet sizes. Third, we explore the applicability of our theoretical results on a case study of Manhattan. Collectively, this paper provides a unifying framework for the analysis and control of AMoD systems, which provides a large set of modeling options (e.g. the inclusion of road capacities and charging constraints), and subsumes earlier Jackson and network flow models.
AcquavivaFDi PaolaDRizzoA (2014) A novel formulation for the distributed solution of load balancing problems in mobility on-demand systems. In: 2014 International Conference on Connected Vehicles and Expo (ICCVE), pp. 906–911.
2.
BalmerMRieserMMeisterKCharyparDLefebvreNNagelK (2009) MATSim-t: Architecture and simulation times. In: Multi-Agent Systems for Traffic and Transportation Engineering.
3.
BanerjeeSJohariRRiquelmeC (2015) Pricing in ride-sharing platforms: A queueing-theoretic approach. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation. New York: ACM Press, pp. 639–639.
4.
BaskettFChandyKMMuntzRRPalaciosFG (1975) Open, closed, and mixed networks of queues with different classes of customers. Journal of the Association for Computing Machinery22(2): 248–260.
5.
BoyacıBZografosKGGeroliminisN (2015) An optimization framework for the development of efficient one-way car-sharing systems. European Journal of Operational Research240(3): 718–733.
6.
Bureau of Public Roads (1964) Traffic assignment manual. Technical report, US Department of Commerce, Urban Planning Division, Washington, DC.
7.
ChemlaDMeunierFCalvoRW (2013) Bike sharing systems: Solving the static rebalancing problem. Discrete Optimization10(2): 120–146.
8.
ChenTDKockelmanKMHannaJP (2016) Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle & charging infrastructure decisions. Transportation Research Part A: Policy and Practice94: 243–254.
9.
ChiuYCBottomJMahutMet al. (2011) Dynamic traffic assignment: A primer. Transportation Research E-Circular E-C153.
FagnantDJKockelmanKM (2014) The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios. Transportation Research Part C: Emerging Technologies40: 1–13.
12.
FagnantDJKockelmanKMBansalP (2015) Operations of shared autonomous vehicle fleet for Austin, Texas, market. Transportation Research Record: Journal of the Transportation Research Board2536: 98–106.
13.
FordLRFulkersonDR (1962) Flows in Networks. Princeton, NJ: Princeton University Press.
14.
GelenbeEPujolleGNelsonJ (1998) Introduction to queueing networks, vol. 2. Chichester: John Wiley & Sons, Inc.
15.
GeorgeDK (2012) Stochastic Modeling and Decentralized Control Policies for Large-Scale Vehicle Sharing Systems via Closed Queueing Networks. PhD Thesis, The Ohio State University.
16.
GoldbergAVOldhamJDPlotkinSSteinC (1998) An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow. In: BixbyRBoydERos-MercadoR (eds.) Integer Programming and Combinatorial Optimization (Lecture Notes in Computer Science, vol. 1412). Berlin: Springer, pp. 338–352.
17.
IglesiasRRossiFZhangRPavoneM (2016) A BCMP network approach to modeling and controlling Autonomous Mobility-on-Demand systems. In: Workshop on Algorithmic Foundations of Robotics.
18.
KantKSrinivasanM (1992) Introduction to computer system performance evaluation. New York: McGraw-Hill.
19.
KobayashiHGerlaM (1983) Optimal routing in closed queueing networks. In: ACM SIGCOMM Computer Communication Review13: 26.
20.
LevinMWLiTBoylesSDKockelmanKM (2016) A general framework for modeling shared autonomous vehicles. In: 95th Annual Meeting of the Transportation Research Board.
NeilD (2015) Could self-driving cars spell the end of ownership? Available at: http://www.wsj.com.
23.
NourinejadMZhuSBahramiSRoordaMJ (2015) Vehicle relocation and staff rebalancing in one-way carsharing systems. Transportation Research Part E: Logistics and Transportation Review81: 98–113.
24.
PatrikssonM (2015) The traffic assignment problem: models and methods. New York: Dover Publications.
25.
PavoneMSmithSLFrazzoliERusD (2012) Robotic load balancing for mobility-on-demand systems. The International Journal of Robotics Research31(7): 839–854.
26.
RossiFZhangRHindyYPavoneM (2018) Routing autonomous vehicles in congested transportation networks: Structural properties and coordination algorithms. Autonomous Robots, in Press.
27.
SpieserKTreleavenKZhangRFrazzoliEMortonDPavoneM (2014) Toward a systematic approach to the design and evaluation of automated mobility-on-demand systems: A case study in Singapore. In: Lecture Notes in Mobility. New York: Springer, pp. 229–245.
ZhangRPavoneM (2016) Control of robotic mobility-on-demand systems: A queueing-theoretical perspective. The International Journal of Robotics Research35(1–3): 186–203.
30.
ZhangRRossiFPavoneM (2016) Model predictive control of autonomous mobility-on-demand systems. In: Proceedings IEEE Conference on Robotics and Automation. Stockholm, Sweden, pp. 1382–1389.
