| Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem (2003) | |||||||||||||||
Abstract | |||||||||||||||
| 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. | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||