Adaptive large neighborhood search for the commodity constrained split delivery VRP. (December 2019)

• Record Type: Journal Article
• Authors: Gu, Wenjuan; Cattaruzza, Diego; Ogier, Maxime; Semet, Frédéric
• Is Part Of: Computers & operations research. Volume 112(2019)
• Publication Date: 2019-12
• Subjects: Vehicle routing problem -- Multiple commodities -- Adaptive large neighborhood search -- Local search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.07.019
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Provide the first dedicated heuristic algorithm for the commodity constrained split delivery vehicle routing problem (C-SDVRP) based on an adaptive large neighborhood search framework. Adapt some classical local search moves taking into account the main feature of the C-SDVRP. A mathematical programming based operator to intensify the search and further improve the best solutions. High-quality solutions for medium and large size instances. Abstract: This paper addresses the commodity constrained split delivery vehicle routing problem (C-SDVRP) where customers require multiple commodities. This problem arises when customers accept to be delivered separately. All commodities can be mixed in a vehicle as long as the vehicle capacity is satisfied. Multiple visits to a customer are allowed, but a given commodity must be delivered in one delivery. In this paper, we propose a heuristic based on the adaptive large neighborhood search (ALNS) to solve the C-SDVRP, with the objective of efficiently tackling medium and large sized instances. We take into account the distinctive features of the C-SDVRP and adapt several local search moves to improve a solution. Moreover, a mathematical programming based operator (MPO) that reassigns commodities to routes is used to improve a new global best solution. Computational experiments have been performed on benchmark instances from the literature. The results assess the efficiency of the algorithm, which can provide a large number of new best-known solutions in short computational times.