Heuristic procedures for the capacitated vehicle routing problem

In this paper we present two new heuristic procedures for the Capacitated V ehicle Routing Problem (CVRP). The first one solves the problem from scratc h, while the second one uses the information provided by a strong linear re laxation of the original problem. This second algorithm is designed to be u sed in a branch and cut approach to solve to optimality CVRP instances. In both heuristics, the initial solution is improved using tabu search techniq ues. Computational results over a set of known instances, most of them with a proved optimal solution, are given.