Events

We study an infinite-horizon, stochastic, dynamic optimization problem for an on-demand food-delivery platform, with a one-time capacity-investment decision on the number of capacitated drivers to employ at the beginning of the horizon, and real-time order-batching and driver-routing decisions for the spatial delivery of orders. The objective is to minimize the long-run average cost incurred per unit time, where the cost includes the wages of the drivers and the waiting costs of the orders. We first characterize the fundamental (spatial-temporal) trade-off between the spatial economies of scale and customers’ waiting times for spatial delivery through an inequality, and leverage this relationship to establish a lower bound on the cost under any policy for the platform. We then identify a simple region-partitioning algorithm that simultaneously ensures (a) a vanishing performance gap with respect to this lower bound, and (b) a vanishing excess delay (which measures the extra time an order spends in the system beyond the least time that this order has to spend in the system), in a meaningful asymptotic regime. Numerical results corroborate the near-optimal performance of our policy in practically relevant parameter regimes.
Together, our results establish the optimality of a safety-staffing rule with a safety level that is proportional to the nominal load to the power of 2/3, where the nominal load is the minimum number of drivers needed to avoid the system from exploding. This represents a fundamental departure from the square-root safety-staffing rule for capacity sizing in conventional service systems without the spatial feature. Our result echoes a similar finding for a spatial ride-hailing platform reported in Besbes et al. (2022), who establish mathematical results for a state-dependent queuing system that is a stylized approximation of the original spatial system, and regard these results as qualitative characterizations of the spatial system. By contrast, we directly study the food-delivery system and establish all our results for this spatial system under a setting that is significantly more general than that considered in the extant literature.