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

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.

In  Mathematical Programming

Publisher  Springer-Verlag
All copyrights reserved by Springer 2007.

Details

TypeArticle
URLhttp://dx.doi.org/10.1007/s10107-005-0644-x
Pages491–511
Volume106
Number3
> Publications > Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem