Separating capacity constraints in the CVRP using tabu search

Branch and Cut methods have shown to be very successful in the resolution of some hard combinatorial optimization problems. The success has been remarkable for the Symmetric Traveling Salesman Problem (TSP). The crucial part in the method is the cutting plane algorithm: the algorithm that looks for valid inequalities that cut off the current non-feasible linear program (LP) solution. In turn this part relies on a good knowledge of the corresponding polyhedron and our ability to design algorithms that can identify violated valid inequalities. This paper deals with the separation of the capacity constraints for the Capacitated Vehicle Routing Problem (CVRP). Three algorithms are presented: a constructive algorithm, a randomized greedy algorithm and a very simple tabu search procedure. As far as we know this is the first time a metaheuristic is used in a separation procedure. The aim of this paper is to present this application. No advanced tabu technique is used. We report computational results with these heuristics on difficult instances taken from the literature as well as on some randomly generated instances. These algorithms were used in a Branch and Cut procedure that successfully solved to optimality large CVRP instances. (C) 1998 Elsevier Science B.V. All rights reserved.