6.1 Introduction In recent years several metaheuristics have been proposed for the VRP. These are general solution procedures that explore the solution space to identify good solutions and often embed some of the standard route construction and improvement heuristics described in Chapter 5. In a major departure from classical approaches, metaheuristics allow deteriorating and even infeasible intermediary solutions in the course of the search process. The best known metaheuristics developed for the VRP typically identify better local optima than earlier heuristics, but they also tend to be more time consuming. We are aware of six main types of metaheuristic that have been applied to the VRP: Simulated Annealing (SA), Deterministic Annealing (DA), Tabu Search (TS), Genetic Algorithms (GA), Ant Systems (AS), and Neural Networks (NN). The first three algorithms start from an initial solution x1 and move at each iteration t from xt to a solution xt+1 in the neighborhood N (xt) of xt, until a stopping condition is satisfied. If ƒ (x) denotes the cost of x, then ƒ (xt+1) is not necessarily less than ƒ (xt). As a result, care must be taken to avoid cycling. GA examines at each step a population of solutions. Each population is derived from the preceding one by combining its best elements and discarding the worst. Ant systems is a constructive approach in which several new solutions are created at each iteration using some of the information gathered at previous iterations. As was noted by Taillard et al. [63], tabu search, genetic algorithms, and ant systems are methods that record, as the search proceeds, information on solutions encountered and use it to obtain improved solutions. Neural networks is a learning mechanism that gradually adjusts a set of weights until an acceptable solution is reached.