Simple Heuristics and Local Search Procedures

International audienceSimple 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