The exponential multi-insertion neighborhood for the vehicle routing problem with unit demands

Autor(en): Buckow, Jan-Niklas
Graf, Benjamin
Knust, Sigrid 
Stichwörter: Computer Science; Computer Science, Interdisciplinary Applications; Engineering; Engineering, Industrial; Exponential neighborhood; LARGE-SCALE NEIGHBORHOODS; LOCAL SEARCH; Operations Research & Management Science; TRAVELING SALESMAN PROBLEM; Unit demands; Vehicle routing
Erscheinungsdatum: 2020
Herausgeber: PERGAMON-ELSEVIER SCIENCE LTD
Journal: COMPUTERS & OPERATIONS RESEARCH
Volumen: 120
Zusammenfassung: 
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. (C) 2020 Elsevier Ltd. All rights reserved.
ISSN: 03050548
DOI: 10.1016/j.cor.2020.104949

Show full item record

Page view(s)

1
Last Week
0
Last month
0
checked on Mar 2, 2024

Google ScholarTM

Check

Altmetric