Skip to Main content Skip to Navigation
Book sections

Simple Heuristics and Local Search Procedures

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.
Document type :
Book sections
Complete list of metadata
Contributor : Jean-Baptiste VU VAN Connect in order to contact the contributor
Submitted on : Tuesday, June 29, 2021 - 10:23:45 AM
Last modification on : Sunday, June 26, 2022 - 1:41:56 AM





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⟩



Record views