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.
Highlights We study the same-day delivery problem. Stochastic customers request urgent deliveries within restricted time windows. We propose a novel branch-and-regret algorithm. Sampled scenarios are used to anticipate future events. Computational experiments prove the outstanding performance of the branch-and-regret.
A branch-and-regret algorithm for the same-day delivery problem
2023-07-13
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch