Simple Heuristics and Local Search Procedures - Université de technologie de Troyes Accéder directement au contenu
Chapitre D'ouvrage Année : 2016

Simple Heuristics and Local Search Procedures

Résumé

Simple heuristics and local search procedures are important components of metaheuristics for vehicle routing problems (VRP). This chapter presents a few classical heuristics before explaining the principles of local search, taking the capacitated VRP (CVRP) as the main example. Many constructive methods for the CVRP are obtained by modifying a traveling salesman problem (TSP) heuristic to build several routes. Two fruitful techniques can improve solution quality of simple heuristics, before resorting to local search. The first one is the best of method. The second technique is randomization. This idea is to introduce some randomness into the decisions of the original deterministic heuristic. The chapter also gives the general structure of a local search, presents classical moves and discusses important issues such as feasibility tests, genericity, multiple neighborhoods, very constrained problems, complex moves and acceleration techniques.
Fichier non déposé

Dates et versions

hal-03273305 , version 1 (29-06-2021)

Identifiants

Citer

Nacima Labadie, Christian Prins, Caroline Prodhon. Simple Heuristics and Local Search Procedures. Metaheuristics for Vehicle Routing Problems, John Wiley & Sons, Inc., pp.15-37, 2016, ⟨10.1002/9781119136767.ch2⟩. ⟨hal-03273305⟩

Collections

CNRS UTT LOSI
12 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More