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

doi:10.1016/j.trb.2023.02.016

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 journal › Article › peer-review

16 Citations (SciVal)

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.

Original language	English
Pages (from-to)	194-220
Number of pages	27
Journal	Transportation Research Part B: Methodological
Volume	170
Early online date	3 Mar 2023
DOIs	https://doi.org/10.1016/j.trb.2023.02.016
Publication status	Published - 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.

Funding

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. 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.

Keywords

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

ASJC Scopus subject areas

Civil and Structural Engineering
Transportation

Access to Document

10.1016/j.trb.2023.02.016Licence: CC BY

Cite this

@article{09f4123179504b6da6945c1ed9ae2e83,

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

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.",

keywords = "Adaptive Large Neighborhood Search, Attended home delivery, Customer availability profile, Last-mile delivery, Routing",

author = "{\"O}zarık, {Sami Serkan} and Virginie Lurkin and Veelenturf, {Lucas P.} and {Van Woensel}, Tom and Gilbert Laporte",

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. ",

year = "2023",

month = apr,

day = "30",

doi = "10.1016/j.trb.2023.02.016",

language = "English",

volume = "170",

pages = "194--220",

journal = "Transportation Research Part B: Methodological",

issn = "0191-2615",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Özarık, Sami Serkan

AU - Lurkin, Virginie

AU - Veelenturf, Lucas P.

AU - Van Woensel, Tom

AU - Laporte, Gilbert

N1 - 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.

PY - 2023/4/30

Y1 - 2023/4/30

N2 - 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.

AB - 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.

KW - Adaptive Large Neighborhood Search

KW - Attended home delivery

KW - Customer availability profile

KW - Last-mile delivery

KW - Routing

UR - http://www.scopus.com/inward/record.url?scp=85149364756&partnerID=8YFLogxK

U2 - 10.1016/j.trb.2023.02.016

DO - 10.1016/j.trb.2023.02.016

M3 - Article

AN - SCOPUS:85149364756

SN - 0191-2615

VL - 170

SP - 194

EP - 220

JO - Transportation Research Part B: Methodological

JF - Transportation Research Part B: Methodological

ER -

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

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this