Two-stage stochastic fleet and battery sizing with routing optimization for sidewalk delivery robots

The rapidly growing online food delivery (OFD) market presents substantial logistical challenges for last-mile delivery operations. Sidewalk delivery robots (SDRs) have emerged as a promising alternative to on-demand workers, as these compact, box-sized robots efficiently deliver food or groceries over short distances via sidewalks. We propose a two-stage stochastic optimization model for a single-depot SDR system with integrated battery-swapping operations. In the first stage, a continuous approximation (CA) method determines the optimal fleet size and the required number of additional swappable batteries. The second-stage solutions are critical to facilitate the first-stage method. These involve solving a routing problem that incorporates battery-swapping decisions and penalties for late arrivals. To address this, we develop a customized heuristic based on adaptive large neighborhood search (ALNS) to generate high-quality solutions for the second stage. The fitted CA model integrates key factors, including time windows, battery swapping, and pickup-delivery orders. Numerical examples highlight the proposed approach's efficiency in reducing computational time while maintaining solution accuracy. A case study and sensitivity analysis conducted on Purdue University's campus illustrate the practical impacts of fleet size and the number of swappable batteries.