A large neighborhood search approach to the vehicle routing problem with delivery options

Dorian Dumez, Fabien Lehuédé and Olivier Péton

Transportation Research Part B: Methodological, 2021, vol. 144, issue C, 103-132

Abstract: To reduce delivery failures in last mile delivery, several types of delivery options have been proposed in the past twenty years. Still, customer satisfaction is a challenge because a single location is chosen independently of the time at which the customer’s order will be delivered. In addition, delivery at shared locations such as lockers and shops also experience failure due to capacity or opening-time issues at the moment of delivery. To address this issue and foster consolidation at shared delivery locations, we investigate the case where a customer can specify several delivery options together with preference levels and time windows. We define, in this article, the Vehicle Routing Problem with Delivery Options, which integrates several types of delivery locations. It consists of designing a set of routes for a fleet of vehicles that deliver to each customer at one of his/her options during the corresponding time window. These routes should respect capacities at shared locations such as lockers and minimum service level requirements, while minimizing the total routing costs. This problem is solved with a large neighborhood search in which a set partitioning problem is periodically used to reassemble routes. Specific ruin and recreate operators are proposed and combined with numerous operators from the literature. A thorough experimental study was carried out to determine a subset of efficient and complementary operators. The proposed method outperforms existing algorithms from the literature on particular cases of the problem under consideration, such as the vehicle routing problem with roaming delivery locations and the vehicle routing problem with home and roaming delivery locations. New instances are generated and used both to serve as a benchmark and to propose some managerial insight into the vehicle routing problem with alternative delivery options.

Keywords: City logistics; Vehicle routing; Matheuristic; Large neighborhood search (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261520304422
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:transb:v:144:y:2021:i:c:p:103-132

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2020.11.012

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().