Dimensioning On-Demand Vehicle Sharing Systems

We consider the problem of optimal fleet sizing in a vehicle sharing system. Vehicles are available for short-term rental and are accessible from multiple locations. A vehicle rented at one location can be returned to any other location. The size of the fleet must account not only for the nominal load and for the randomness in demand and rental duration but also for the randomness in the number of vehicles that are available at each location because of vehicle roaming (vehicles not returning to the same location from which they were picked up). We model the dynamics of the system using a closed queueing network and obtain explicit and closed form lower and upper bounds on the optimal number of vehicles (the minimum number of vehicles needed to meet a target service level). Specifically, we show that starting with any pair of lower and upper bounds, we can always obtain another pair of lower and upper bounds with gaps between the lower and upper bounds that are independent of demand and bounded by a function that depends only on the prescribed service level. We show that the generated bounds are asymptotically exact under several regimes. We use features of the bounds to construct a simple and closed form approximation that we show to be always within the generated lower and upper bounds and is exact under the asymptotic regimes considered. Extensive numerical experiments show that the approximate and exact values are nearly indistinguishable for a wide range of parameter values. The approximation is highly interpretable with buffer capacity expressed in terms of three explicit terms that can be interpreted as follows: (1) standard buffer capacity that is protection against randomness in demand and rental times, (2) buffer capacity that is protection against vehicle roaming, and (3) a correction term. Our analysis reveals important differences between the optimal sizing of standard queueing systems (where servers always return to the same queue upon service completion) and that of systems where servers, upon service completion, randomly join any one of the queues in the system. We show that the additional capacity needed to buffer against vehicle roaming can be substantial even in systems with vanishingly small demand.