Résumé
In this paper, we propose a Branch-Cut-and-price algorithm for the robust counterpart of the classical Capacitated Vehicle Routing Problem (CVRP). The deterministic version of this problem consists of finding a set of vehicle routes to serve a given set of customers with associated demands such that the sum of demands served by each vehicle does not exceed its capacity, and each customer is served exactly once. The total travel cost, given by the sum of distances traversed by all vehicles must be minimized. Here, only customer demands are assumed to be uncertain. We consider two types of uncertainty sets for the vector of customer demands: the classical budget polytope introduced by Bertsimas and Sim (2003), and a partitioned budget polytope, proposed by Gounaris et al (2013) for the CVRP with uncertain demands. The method proposed in this paper uses a set partitioning formulation to solve the problem, where each binary variable determines whether a given route is included or not in the solution. It considers only the routes that satisfy the capacity constraints for all possible demand vectors allowed by the uncertainty polytope. The linear relaxation for this formulation is solved by column generation, where the pricing subproblem is decomposed into a small number of deterministic subproblems with modified demand vectors. This reformulation allows the use of state-of-the-art techniques such as ng-routes, rank-1 cuts, specialized labeling algorithms, fixing by reduced costs and route enumeration. As a result, we were able to solve all 47 open instances proposed by Gounaris et al (2013), the largest one having 150 customers.