The exponential multi-insertion neighborhood for the vehicle routing problem with unit demands. (August 2020)

• Record Type: Journal Article
• Authors: Buckow, Jan-Niklas; Graf, Benjamin; Knust, Sigrid
• Is Part Of: Computers & operations research. Volume 120(2020)
• Publication Date: 2020-08
• Subjects: Vehicle routing -- Exponential neighborhood -- Unit demands; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.104949
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Extended study of exponential multi-insertion neighborhood for VRP with unit demands. Connectivity, diameter, quality of local optima in this neighborhood. Proof that finding an optimal set of mobile nodes is NP-hard. Two-stage approach: first select mobile nodes heuristically, then reinsert optimally. Computational study: comparison to other heuristics known for VRP. Abstract: In this paper, we extend, analyze and evaluate the exponential multi-insertion neighborhood for the vehicle routing problem with unit demands, originally proposed by Angel et al. (2008). In this neighborhood, a neighbor solution is obtained by the removal of a set of mobile nodes from a solution and a subsequent best reinsertion. At first, we examine theoretical properties of the neighborhood, such as its connectivity and the question how many nodes may be chosen as mobile. Furthermore, we prove that finding a best set of mobile nodes is NP-hard. Then, we present a two-stage approach in which first mobile nodes are selected heuristically and reinserted in an optimal way afterwards. Finally, this approach is embedded into a simulated annealing procedure and compared to other heuristics known for the more general vehicle routing problem with arbitrary demands.