A branch-and-regret algorithm for the same-day delivery problem

Jean-François Côté, Thiago Alves de Queiroz, Francesco Gallesi and Manuel Iori

Transportation Research Part E: Logistics and Transportation Review, 2023, vol. 177, issue C

Abstract: We study a dynamic vehicle routing problem where stochastic customers request urgent deliveries characterized by restricted time windows. The aim is to use a fleet of vehicles to maximize the number of served requests and minimize the traveled distance. The problem is known in the literature as the same-day delivery problem, and it is of high importance because it models a number of real-world applications, including the delivery of online purchases. We solve the same-day delivery problem by proposing a novel branch-and-regret algorithm in which sampled scenarios are used to anticipate future events and an adaptive large neighborhood search is iteratively invoked to optimize routing plans. The branch-and-regret is equipped with four innovation elements: a new way to model the subproblem, a new policy to generate scenarios, new consensus functions, and a new branching scheme Extensive computational experiments on a large variety of instances prove the outstanding performance of the branch-and-regret, also in comparison with recent literature, in terms of served requests, traveled distance, and computational effort.

Keywords: Same-day delivery; Dynamic pickup and delivery; Branch-and-regret; Preemptive depot return (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554523002144
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:177:y:2023:i:c:s1366554523002144

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2023.103226

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().