Abstract: The demand for same-day delivery (SDD) has increased rapidly over the past few years and has become a popular delivery option for customers. In this paper, we propose the Autonomous Vehicle Assisted Delivery Problem with Dynamic Resupply (AVADDR) to address the challenge of high-frequency, time-sensitive stochastic requests in same-day delivery. Throughout the day, customers place requests for same-day delivery (SDD) services without prior knowledge of the exact timing or delivery locations. The dispatcher then dynamically allocates the courier with autonomous vehicle resupply to fulfill these requests. We assume that the autonomous vehicle performs multiple trips from the warehouse to replenish the courier at any required time while the courier delivers the orders. The AVADDR is decomposed into two stages: routing optimization and dynamic resupply. A mathematical programming model was developed for AVADDR to minimize the delivery time. An adaptive large neighborhood search algorithm (ALNS) is designed to solve the routing optimization problem, and myopic and adaptive resupply strategies are proposed to address the dynamic resupply issue. Comprehensive testing and analysis demonstrate the superior effectiveness of our approach compared to benchmarks. The approach can provide effective decision-making support for same-day delivery companies with high time-sensitivity requirements.

Key words: same-day delivery, dynamic replenishment with autonomous vehicles, vehicle routing optimization, two-stage algorithm