Logo image
Back
An Integer L-shaped Method for Dynamic Order Fulfillment in Autonomous Last-Mile Delivery with Demand Uncertainty
Preprint   Open access

An Integer L-shaped Method for Dynamic Order Fulfillment in Autonomous Last-Mile Delivery with Demand Uncertainty

Linxuan Shi, Zhengtian Xu, Miguel Lejeune and Qi Luo
ArXiv.org
Cornell University
06/10/2024
DOI: 10.48550/arxiv.2208.09067
url
https://doi.org/10.48550/arxiv.2208.09067View
Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

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.
 Mathematics - Optimization and Control

Details

Metrics

89 Record Views
Logo image