Skip to Main content Skip to Navigation
Book sections

Metaheuristics Generating a Sequence of Solutions

Abstract : This chapter presents the main metaheuristics working on a sequence of solutions, and their applications on vehicle routing problems (VRP). Eight metaheuristics generating a sequence of solutions include simulated annealing (SA), greedy randomized adaptive search procedure (GRASP), Tabu search (TS), variable neighborhood search (VNS), iterated local search (ILS), guided local search (GLS), large neighborhood search (LNS), and evolutionary local search (ELS). Adaptive large neighborhood search (ALNS) is a relatively efficient framework to solve variants of the vehicle routing problems, especially the so-called Rich VRP in which various, possibly tight, constraints need to hold. Rather than using one large neighborhood as in LNS, it applies several removal and insertion operators, selected dynamically according to their past performance, to a given solution. The chapter also presents main features of the ALNS algorithm for the pickup and delivery problem with time windows (PDPTW).
Document type :
Book sections
Complete list of metadata

https://hal-utt.archives-ouvertes.fr/hal-03273300
Contributor : Jean-Baptiste Vu Van Connect in order to contact the contributor
Submitted on : Tuesday, June 29, 2021 - 10:20:10 AM
Last modification on : Friday, August 27, 2021 - 3:14:08 PM

Identifiers

Collections

UTT | CNRS

Citation

Nacima Labadie, Christian Prins, Caroline Prodhon. Metaheuristics Generating a Sequence of Solutions. Metaheuristics for Vehicle Routing Problems, John Wiley & Sons, Inc., pp.39-75, 2016, ⟨10.1002/9781119136767.ch3⟩. ⟨hal-03273300⟩

Share

Metrics

Record views

18