Simple Heuristics and Local Search Procedures - Archive ouverte HAL Access content directly
Book Sections Year : 2016

Simple Heuristics and Local Search Procedures

(1) , (1) , (1)
1

Abstract

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.
Not file

Dates and versions

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

Identifiers

Cite

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
9 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More