5.1 Introduction Several families of heuristics have been proposed for the VRP. These can be broadly classified into two main classes: classical heuristics, developed mostly between 1960 and 1990, and metaheuristics, whose growth has occurred in the last decade. Most standard construction and improvement procedures in use today belong to the first class. These methods perform a relatively limited exploration of the search space and typically produce good quality solutions within modest computing times. Moreover, most of them can be easily extended to account for the diversity of constraints encountered in real-life contexts. Therefore, they are still widely used in commercial packages. In metaheuristics, the emphasis is on performing a deep exploration of the most promising regions of the solution space. These methods typically combine sophisticated neighborhood search rules, memory structures, and recombinations of solutions. The quality of solutions produced by these methods is much higher than that obtained by classical heuristics, but the price to pay is increased computing time. Moreover, the procedures usually are context dependent and require finely tuned parameters, which may make their extension to other situations difficult. In a sense, metaheuristics are no more than sophisticated improvement procedures, and they can simply be viewed as natural enhancements of classical heuristics. However, because they make use of several new concepts not present in classical methods, they are covered separately, in Chapter 6. Classical VRP heuristics can be broadly classified into three categories. Constructive heuristics gradually build a feasible solution while keeping an eye on solution cost, but they do not contain an improvement phase per se.