An Adaptive Large Neighborhood Search heuristic for last-mile deliveries under stochastic customer availability and multiple visits. (April 2023)

• Record Type: Journal Article
• Authors: Özarık, Sami Serkan; Lurkin, Virginie; Veelenturf, Lucas P.; Van Woensel, Tom; Laporte, Gilbert
• Is Part Of: Transportation research. Volume 170(2023)
• Page Start: 194
• Page End: 220
• Publication Date: 2023-04
• Subjects: Routing -- Attended home delivery -- Adaptive Large Neighborhood Search -- Customer availability profile -- Last-mile delivery; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2023.02.016
• Languages: English
• ISSNs: 0191-2615

Abstract

Abstract: Attended Home Delivery, where customer attendance at home is required, is an essential last-mile delivery challenge, e.g., for valuable, perishable, or oversized items. Logistics service providers are often faced no-show customers. In this paper, we consider the delivery problem in which customers can be revisited on the same day by a courier in the case of a failed first delivery attempt. Specifically, customer presence uncertainty is considered in a two-stage stochastic program, where penalties are introduced as recourse actions for failed deliveries. We build on the notion of a customer availability profile defined as a profile containing historical time-varying probability information of successful deliveries. We tackle this stochastic program by developing an efficient parallelized Adaptive Large Neighborhood Search algorithm. Our results show that by achieving a right balance between increasing the hit rate and reducing travel cost, logistics service providers can realize costs savings as high as 32% if they plan for second visits on the same day. Highlights: A stochastic vehicle routing and scheduling problem with multiple visit attempts Application of an efficient pALNS algorithm for the stochastic customer availability Results show that companies can reduce costs with second visits on the same day