Authors: Jens Lysgaard Adam N Letchford Richard W Eglese
Publish Date: 2003/11/21
Volume: 100, Issue: 2, Pages: 423-445
Abstract
We present a new branchandcut algorithm for the capacitated vehicle routing problem CVRP The algorithm uses a variety of cutting planes including capacity framed capacity generalized capacity strengthened comb multistar partial multistar extended hypotour inequalities and classical Gomory mixedinteger cutsFor each of these classes of inequalities we describe our separation algorithms in detail Also we describe the other important ingredients of our branchandcut algorithm such as the branching rules the node selection strategy and the cut pool management Computational results for a large number of instances show that the new algorithm is competitive In particular we solve three instances Bn50k8 Bn66k9 and Bn78k10 of Augerat to optimality for the first time
Keywords: