  Given their potential to significantly lower costs and enhance flexibility in
last-mile delivery, autonomous delivery solutions like sidewalk robots and
drones have garnered increased interest. This paper addresses the dynamic order
fulfillment problem faced by a retailer who operates a fleet of low-capacity
autonomous delivery vehicles, servicing requests arriving in a stochastic
manner. These delivery requests may vary in package profiles, delivery
locations, and urgency. We adopt a rolling-horizon framework for order
fulfillment and devise a two-stage stochastic program aimed at strategically
managing existing orders while considering incoming requests that are subject
to various uncertainties. A significant challenge in deploying the envisioned
two-stage model lies in its incorporation of vehicle routing constraints, on
which exact or brute-force methods are computationally inefficient and
unsuitable for real-time operational decisions. To address this, we propose an
accelerated L-shaped algorithm, which (i) reduces the branching tree size; (ii)
substitutes exact second-stage solutions with heuristic estimations; and (iii)
adapts an alternating strategy for adding optimality cuts. This heuristic
algorithm demonstrates remarkable performance superiority over the exact
method, boasting a more than 20-fold improvement in average running time while
maintaining an average optimality gap of less than 1%. It is then employed to
solve a wide range of instances to evaluate the advantages of adopting the
stochastic model. Our findings demonstrate long-term cost savings of up to 20%
when accounting for demand uncertainty in order fulfillment decisions.
Meanwhile, the derived savings could diminish as the uncertainty in order
arrivals increases.
