Groupe d’études et de recherche en analyse des décisions

Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem

Eduardo Uchoa

The best exact algorithms for the capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over \(q\)-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price algorithm can solve to optimality almost all instances from the literature with up to 100 vertices, nearly doubling the size of instances that can be consistently solved.