An Adaptive Large Neighborhood Search heuristic for last-mile deliveries under stochastic customer availability and multiple visits

Sami Serkan Özarık, Virginie Lurkin, Lucas P. Veelenturf, Tom Van Woensel, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

4 Citations (SciVal)


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.

Original languageEnglish
Pages (from-to)194-220
Number of pages27
JournalTransportation Research Part B: Methodological
Early online date3 Mar 2023
Publication statusPublished - 30 Apr 2023

Bibliographical note

Funding Information:
Gilbert Laporte was partially supported by the Canadian Natural Sciences and Engineering Research Council, Canada under grant 2015-06189 . This research was also funded by The Dutch Research Council (NWO), The Netherlands Data2Move project under grant 628.009.013 . This work was carried out on the Dutch national e-infrastructure with the support of the SURF Cooperative. These supports are greatly acknowledged. Thanks are due to the associate editor and to the referees for their valuable comments.


  • Adaptive Large Neighborhood Search
  • Attended home delivery
  • Customer availability profile
  • Last-mile delivery
  • Routing

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'An Adaptive Large Neighborhood Search heuristic for last-mile deliveries under stochastic customer availability and multiple visits'. Together they form a unique fingerprint.

Cite this