Chapter 3: New Exact Algorithms for the Capacitated Vehicle Routing Problem

3.1 ▪ Introduction Since the seminal work by Desrosiers, Soumis, and Desrochers [15], column generation has been the dominant approach for building exact algorithms for the Vehicle Routing Problem with Time Windows (VRPTW). This technique performed very well on tightly constrained instances (those with narrow time windows). As the Capacitated Vehicle Routing Problem (CVRP) can be regarded as the particular case of VRPTW where time windows are arbitrarily large, column generation was viewed as a non-promising approach for the problem. In fact, in the early 2000's, the best performing algorithms for the CVRP were Branch-and-Cut algorithms that separated quite complex families of cuts identified by polyhedral investigation (see Naddef and Rinaldi [31] and Chapter 2). In spite of their sophistication, some instances from the literature with only 50 customers could not be solved to optimality. At that moment, the Branch-and-Cut-and-Price algorithm (BCP) by Fukasawa et al. [19] showed that the combination of cut and column generation could be much more effective than each of those techniques taken alone. Since then, the most performing exact algorithms proposed for the CVRP are based on that combination.