Robust branch-and-cut-and-price for the Capacitated Vehicle Routing Problem, with R. Fukasawa, H. Longo, J. Lysgaard, M. Poggi de Aragão, M. Reis, and E. Uchoa. Mathematical Programming, volume 106, number 3, pp. 491-511, 2006.

Abstract: The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangen relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a tradicional Langrangean 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 constranints that can elad to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price algorithm can solve to optimality all instances from the literature with up to 135 vertices. This more than doubles the size of the instances that can be consistently solved.

Note: An earlier version of this paper is also available.