Stronger K-tree relaxations for the vehicle routing problem

A Lagrangian based exact solution algorithm for the vehicle routing problem (VRP), defined on an undirected graph, is introduced in this paper. Lower bounds are obtained by allowing exponentially many inequalities as candidates to Lagrangian dualization. Three different families of strong valid inequalities (each one with exponentially many elements) are used within VRP formulations. For each of them, separation procedures are proposed for points that define incidence vectors of K-trees. Violated inequalities identified in this way are then dualized in a relax and cut framework. Upper bounds are generated through a Lagrangian Clarke and Wright heuristic. A variable fixation test based on (approximating) linear programming reduced costs is also implemented. Computational results are presented for the proposed algorithm.